Questions
Assume a hashtable is represented as an array of size 7. We want to store strings consisting of three digits. The primary hash key is the numerical value of the second digit modulo 7. The secondary hash key is the numerical value of the third digit modulo 4 increased by one. Insert the following strings into the initially empty hashtable: "111", "222", "737", "323" and "234".
My response:
- 0 - 234
- 1 - 111
- 2 - 222
- 3 - 737
- 4 - 323
- 5 -
- 6 -
- 111; 1 mod 7 = 1
- 222; 2 mod 7 = 2
- 737; 3 mod 7 = 3
- 323; 3 mod 4 + 1 = 4
- 234; 4 mod 4 + 1 = 4 (0)
is that correct?
Answers
http://en.wikipedia.org/wiki/Cuckoo_hashing
http://en.wikipedia.org/wiki/Cuckoo_hashing
0:
1: 111
2: 222
3: 737
4: 323
5:
6:
Trying to insert 234 with h1 gives a key of 3 mod 7 = 3, but 3 already contains 373. Moving on to h2 we get 4 mod 4 + 1 = 1 but 1 already contains 111. At this point there are no more hash functions, so we insert 234 at 1 and rehash 111.
0:
1: 234
2: 222
3: 737
4: 323
5:
6:
Hashing 111 with h1 gives 1 again, h2 gives 1 mod 4 + 1 = 2, but 2 already contains 222, so we store 111 at 2 and rehash 222, etc. In this case, eventually you will find all the keys fit. In the case where they entries don t all fit (i.e. the reinsertion enters an infinite cycle) the table needs to be resized and rehashed with new hash functions.
Source
License : cc by-sa 3.0
http://stackoverflow.com/questions/6096268/hashtables-and-dealing-with-collisions
Related
