How do HashTables deal with collisions?

Hash tables deal with collisions in one of two ways.

Option 1: By having each bucket contain a linked list of elements that are hashed to that bucket. This is why a bad hash function can make lookups in hash tables very slow.

Option 2: If the hash table entries are all full then the hash table can increase the number of buckets that it has and then redistribute all the elements in the table. The hash function returns an integer and the hash table has to take the result of the hash function and mod it against the size of the table that way it can be sure it will get to bucket. So by increasing the size, it will rehash and run the modulo calculations which if you are lucky might send the objects to different buckets.

Java uses both option 1 and 2 in its hash table implementations.

When you talked about "Hash Table will place a new entry into the 'next available' bucket if the new Key entry collides with another.", you are talking about the Open addressing strategy of Collision resolution of hash table.

There are several strategies for hash table to resolve collision.

First kind of big method require that the keys (or pointers to them) be stored in the table, together with the associated values, which further includes:

• Separate chaining

• Open addressing

• Coalesced hashing
• Cuckoo hashing
• Robin Hood hashing
• 2-choice hashing
• Hopscotch hashing

Another important method to handle collision is by Dynamic resizing, which further has several ways:

• Resizing by copying all entries
• Incremental resizing
• Monotonic keys

EDIT: the above are borrowed from wiki_hash_table, where you should go to have a look to get more info.

There are multiple techniques available to handle collision. I will explain some of them

Chaining: In chaining we use array indexes to store the values. If hash code of second value also points to the same index then we replace that index value with an linked list and all values pointing to that index are stored in the linked list and actual array index points to the head of the the linked list. But if there is only one hash code pointing to an index of array then the value is directly stored in that index. Same logic is applied while retrieving the values. This is used in Java HashMap/Hashtable to avoid collisions.

Linear probing: This technique is used when we have more index in the table than the values to be stored. Linear probing technique works on the concept of keep incrementing until you find an empty slot. The pseudo code looks like this:

index = h(k) 

while( val(index) is occupied) 

index = (index+1) mod n

Double hashing technique: In this technique we use two hashing functions h1(k) and h2(k). If the slot at h1(k) is occupied then the second hashing function h2(k) used to increment the index. The pseudo-code looks like this:

index = h1(k)

while( val(index) is occupied)

index = (index + h2(k)) mod n

Linear probing and double hashing techniques are part of open addressing technique and it can only be used if available slots are more than the number of items to be added. It takes less memory than chaining because there is no extra structure used here but its slow because of lot of movement happen until we find an empty slot. Also in open addressing technique when an item is removed from a slot we put an tombstone to indicate that the item is removed from here that is why its empty.

For more information see this site.