Hashtables and dealing with collisions

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 incr开发者_开发问答eased 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?

You might want to mention what type of hash you are using. I assume from your description that it is cuckoo hashing. If this is the case you are fine up until the last insertion. Before 234 is inserted you have:

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.

I'm not sure what this problem wants you to do if there is still a collision after the secondary hash key is checked, but I think it goes like this:

• 111: 1 mod 7 = 1
• 222: 2 mod 7 = 2
• 737: 3 mod 7 = 3
• 323: 2 mod 7 = 2 => Collision: 3 mod 4 + 1 = 3 + 1 = 4
• 234: 3 mod 7 = 3 => Collision: 4 mod 4 + 1 = 0 + 1 = 1 => Collision

If you advance by one after the second collision, the result would be

• 0 -
• 1 - 111
• 2 - 222
• 3 - 737
• 4 - 323
• 5 - 234
• 6 -
• 7 -