Question

Name: Hash Tables CS 2020 Hw 14 edefine MAX CAPACITY 11 #define R struct HashTable f int hashtable[MAX CAPACITY]: 1/ table to store values int countj // count of values currently stored int hash1(int value) ( return (value % MAX CAPACITY); int hash2(int value) ( return (R- (value % R)); 1) Use hash1 function and linear probing as a collision resolution strategy, insert the following elements into the correct index of the hash table: 1, 5, 4, 11, 21, 15, 22, 23. set i to e while collision is detected index . ( hashi (elen) + 1++ ) % MAX-CAPACITY; hashtable[ index]-elem Elem Index 2) How many collisions were detected when inserting: a) 15 b) 21 c) 22 d) 23 3) Use hash1 and hash2 function (double hashing) and linear probing as a collision resolution strategy, insert the following elements into the correct index of the hash table: 1,5, 4, 11, 21, 15, 22, 23. set i to e while collision is detected index- ( hash1(elen) + (1++ . hash2(elem) ) % MAX CAPACITY; hashtable[index] - elem Elem Index 10 4) How many collisions were detected when inserting: a) 15 b) 21 c) 22 d) 23

Answer 1

1 hash 1 function use and linear probing

Element	index (Element % 11)	Linear probing
1	1
5	5
4	4
11	0
21	10
15	4 (collision occurred)	4+1 =5(collision occurred) 5+1=6 15 will be stored at 6th location
22	0(collision occurred)	0+1=1 (collision occurred) 1+1=2 22 will be stored at 2nd location
23	1(collision occurred)	1+1=2(collision occurred) 2+1=3 23 will be stored at 3rd location

Elem	11	1	22	23	4	5	15				21
index	0	1	2	3	4	5	6	7	8	9	10

2)

• There are 2 collisions for inserting 15.
• There are 2 collisions for inserting 22.
• There are 2 collisions for inserting 23.

============================================================================================

3) hash 1 function, hash 2 function use and linear probing

primary hash function: hash1

secondary hash function: hash2

Element	index (Element % 11)	hash2 function and Linear probing
1	1
5	5
4	4
11	0
21	10
15	4 (collision occurred)	hash2(15)=5 i=1 4+5 =9 15 will be stored at 9th location
22	0(collision occurred)	hash2(22)=3 i=1 0+3=3 22 will be stored at a 3rd location
23	1(collision occurred)	hash2(23)=2 i=1 1+2 =3 (collision occurred) i=2 1+2*2= 5(collision occurred) i=3 1+3*2 =7 23 will be stored at 7th location

Elem	11	1		22	4	5		23		15	21
index	0	1	2	3	4	5	6	7	8	9	10

4)

• There is 1 collision for inserting 15.
• There is 1 collision for inserting 22.
• There are 3 collisions for inserting 23.