ds_lab/hashing_comparison.c at master · sstein98/ds_lab · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <stdio.h>
#include <string.h>

int hashIndex(int key)
{
	return (key%29);
}


int main(int argc, char const *argv[])
{
	int i, j, n, k, ch, spaceFlagL, spaceFlagQ, inp[100], hashTableL[30], hashTableQ[30], index, counterL=1, counterQ=1;	//L for linear and Q for quadratic
	//Input
	printf("Enter no. of elements: ");
	scanf("%d", &n);
	printf("Enter elements: ");
	for (i = 0; i < n; i++)
		scanf("%d", &inp[i]);

	//HashTable prep
	for(i=0;i<30;i++)
	{	hashTableL[i]=0;
		hashTableQ[i]=0;
	}

	//Spaceflag prep
	if(n>=30)
	{
		spaceFlagL = 0;
		spaceFlagQ = 0;
		printf("Error n > size of table.");
	}
	else
	{
		spaceFlagL = 1;
		spaceFlagQ = 1;
	}

	//Linear hasing
	for(i=0;i<n && spaceFlagL;i++)
	{
		index = hashIndex(inp[i]);
		while(hashTableL[index])
		{
			index = (index + 1)%30;
		}
		hashTableL[index] = inp[i];
		spaceFlagL = 0;
		for(j=0;j<30;j++)
			if(!hashTableL[j])
				spaceFlagL = 1;

	}

	//Quadratic hashing
	for(i=0;i<n;i++)
	{
		int k = hashIndex(inp[i]), h = 1;
		index = k;
		while(hashTableQ[index])
		{
			index = (k + (h*h))%30;
			h++;
		}
		hashTableQ[index] = inp[i];
		spaceFlagQ = 0;
		for(j=0;j<30;j++)
			if(!hashTableQ[j])
				spaceFlagQ = 1;
	}


	//Printing
	printf("Linear Hashing: \nIndex\t\tValue\n");
	for (i = 0; i < 29; ++i)
		printf("%d\t\t%d\n",i,hashTableL[i]);
	printf("Quadratic Hashing:\nIndex\t\tValue\n");
	for(i=0;i<29;i++)
		printf("%d\t\t%d\n",i,hashTableQ[i]);

	//Comparison

	printf("Choose an element for comparison: \n");
	for(i=0;i<n;i++)
		printf("%d. %d\n", i+1, inp[i]);
	scanf("%d", &ch);
	ch--;
	i=hashIndex(inp[ch]);
	while(hashTableL[i]!=inp[ch])
	{	i = (i+1)%29;
		counterL++;
	}
	i=hashIndex(inp[ch]);
	j=1;
	while(hashTableQ[i]!=inp[ch])
	{
		i = (i + (j*j))%29;
		counterQ++;
		j++;
	}
	printf("Linear Hashing found element after %d comparisons.\nQuadratic hashing found element after %d comparisons\n", counterL, counterQ);
	return 0;
}