Create a data set with 100 integer values. Use the division method of hashing to
ID: 3824817 • Letter: C
Question
Create a data set with 100 integer values. Use the division method of hashing to store the data values into hash tables with the initial table sizes of 7, 51, and 151. (if it is necessary, you may need to double the table size.) Use the linear probing method of collision resolution. Print out the tables after the data values have been stored. Search for 10 different values in each of the three hash tables, counting the number of comparisons necessary. Print out the number of comparisons necessary in each case, in tabular form. Deliverables A design and the CRC cards for all classes A listing of the program including all files A listing of the output requestedExplanation / Answer
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include<stdio.h>
#include<stdlib.h>
#define LIMIT 30
enum record_status {EMPTY, DELETED, OCCUPIED};
struct Employee
{
int employee_id, employee_age;
char employee_name[30];
};
struct Record
{
struct Employee info;
enum record_status status;
};
int hash_function(int key)
{
return (key % LIMIT);
}
int search_records(int key, struct Record hash_table[])
{
int count, temp, position;
temp = hash_function(key);
position = temp;
for(count = 1; count != LIMIT - 1; count++)
{
if(hash_table[position].status == EMPTY)
{
return -1;
}
if( hash_table[position].info.employee_id == key)
{
return position;
}
position = (temp + count) % LIMIT;
}
return -1;
}
void insert_records(struct Employee emprec, struct Record hash_table[])
{
int count, position, temp;
int key = emprec.employee_id;
temp = hash_function(key);
position = temp;
for(count = 1; count != LIMIT - 1; count++)
{
if(hash_table[position].status == EMPTY || hash_table[position].status == DELETED)
{
hash_table[position].info = emprec;
hash_table[position].status = OCCUPIED;
printf(" Record Inserted into Hash Table ");
return;
}
if(hash_table[position].info.employee_id == key)
{
printf(" Duplicate Record cannot be Inserted ");
return;
}
position = (temp + count) % LIMIT;
}
printf(" Hash Table Limit Exceeded ");
}
void display_records(struct Record hash_table[])
{
int count;
printf(" Hash Table ");
for(count = 0; count < LIMIT; count++)
{
printf("[%d]: ", count);
if(hash_table[count].status == OCCUPIED)
{
printf("Occupied - ID: %d Name: %s Age: %d",hash_table[count].info.employee_id, hash_table[count].info.employee_name, hash_table[count].info.employee_age);
}
else if(hash_table[count].status == DELETED)
{
printf(" Record is Deleted ");
}
else
{
printf(" Hash Table is Empty ");
}
}
}
void delete_records(int key, struct Record hash_table[])
{
int position = search_records(key, hash_table);
if(position == -1)
{
printf(" Key Not Found ");
}
else
{
hash_table[position].status = DELETED;
}
}
int main()
{
int count, key, option;
struct Record hash_table[LIMIT];
struct Employee emprec;
for(count = 0; count <= LIMIT - 1; count++)
{
hash_table[count].status = EMPTY;
}
while(1)
{
printf("1. Insert a Record ");
printf("2. Delete a Record ");
printf("3. Search a Record ");
printf("4. Display All Records ");
printf("5. Exit ");
printf("Enter Your Option: ");
scanf("%d", &option);
switch(option)
{
case 1: printf(" Enter Employee ID: ");
scanf("%d", &emprec.employee_id);
printf("Enter Employee Name: ");
scanf("%s", emprec.employee_name);
printf("Enter Employee Age: ");
scanf("%d", &emprec.employee_age);
insert_records(emprec, hash_table);
break;
case 2: printf(" Enter the Key to Delete: ");
scanf("%d", &key);
delete_records(key, hash_table);
break;
case 3: printf(" Enter the Key to Search: ");
scanf("%d", &key);
count = search_records(key, hash_table);
if(count == -1)
{
printf(" Record Not Found ");
}
else
{
printf(" Record Found at Index Position: %d ", count);
}
break;
case 4: display_records(hash_table);
break;
case 5: exit(1);
}
}
return 0;
}
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include<stdio.h>
#include<stdlib.h>
#define LIMIT 30
enum record_status {EMPTY, DELETED, OCCUPIED};
struct Employee
{
int employee_id, employee_age;
char employee_name[30];
};
struct Record
{
struct Employee info;
enum record_status status;
};
int hash_function(int key)
{
return (key % LIMIT);
}
int search_records(int key, struct Record hash_table[])
{
int count, temp, position;
temp = hash_function(key);
position = temp;
for(count = 1; count != LIMIT - 1; count++)
{
if(hash_table[position].status == EMPTY)
{
return -1;
}
if( hash_table[position].info.employee_id == key)
{
return position;
}
position = (temp + count) % LIMIT;
}
return -1;
}
void insert_records(struct Employee emprec, struct Record hash_table[])
{
int count, position, temp;
int key = emprec.employee_id;
temp = hash_function(key);
position = temp;
for(count = 1; count != LIMIT - 1; count++)
{
if(hash_table[position].status == EMPTY || hash_table[position].status == DELETED)
{
hash_table[position].info = emprec;
hash_table[position].status = OCCUPIED;
printf(" Record Inserted into Hash Table ");
return;
}
if(hash_table[position].info.employee_id == key)
{
printf(" Duplicate Record cannot be Inserted ");
return;
}
position = (temp + count) % LIMIT;
}
printf(" Hash Table Limit Exceeded ");
}
void display_records(struct Record hash_table[])
{
int count;
printf(" Hash Table ");
for(count = 0; count < LIMIT; count++)
{
printf("[%d]: ", count);
if(hash_table[count].status == OCCUPIED)
{
printf("Occupied - ID: %d Name: %s Age: %d",hash_table[count].info.employee_id, hash_table[count].info.employee_name, hash_table[count].info.employee_age);
}
else if(hash_table[count].status == DELETED)
{
printf(" Record is Deleted ");
}
else
{
printf(" Hash Table is Empty ");
}
}
}
void delete_records(int key, struct Record hash_table[])
{
int position = search_records(key, hash_table);
if(position == -1)
{
printf(" Key Not Found ");
}
else
{
hash_table[position].status = DELETED;
}
}
int main()
{
int count, key, option;
struct Record hash_table[LIMIT];
struct Employee emprec;
for(count = 0; count <= LIMIT - 1; count++)
{
hash_table[count].status = EMPTY;
}
while(1)
{
printf("1. Insert a Record ");
printf("2. Delete a Record ");
printf("3. Search a Record ");
printf("4. Display All Records ");
printf("5. Exit ");
printf("Enter Your Option: ");
scanf("%d", &option);
switch(option)
{
case 1: printf(" Enter Employee ID: ");
scanf("%d", &emprec.employee_id);
printf("Enter Employee Name: ");
scanf("%s", emprec.employee_name);
printf("Enter Employee Age: ");
scanf("%d", &emprec.employee_age);
insert_records(emprec, hash_table);
break;
case 2: printf(" Enter the Key to Delete: ");
scanf("%d", &key);
delete_records(key, hash_table);
break;
case 3: printf(" Enter the Key to Search: ");
scanf("%d", &key);
count = search_records(key, hash_table);
if(count == -1)
{
printf(" Record Not Found ");
}
else
{
printf(" Record Found at Index Position: %d ", count);
}
break;
case 4: display_records(hash_table);
break;
case 5: exit(1);
}
}
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.