Collisions are bound to occur no matter how good a hash function is. Hence, to maintain the performance of a hash table, it is important to minimise collisions through various collision resolution techniques. There are majorly 2 methods for handling collisions:
table_size
as number of slots in hash table and n
as number of keys to be saved in the table. Then:
We have Load factor α = n/table_size
Time complexity to search/delete = O(1 + α)
Time complexity for insert = O(1)
Hence, overall time complexity of search, insert and delete operation will be O(1) if α is O(1)
O(1)
time complexity as linked lists allows insertion in constant time.O(n)
.key
into that slot. key
in the hash table, we keep probing until slot’s value doesn’t become equal to key
or until an empty slot is found.key
, then the search operation for that key might fail. Hence, deleted key’s slots are marked as “deleted” so that we get the status of the key when searched.Linear Probing:
hash(key)
be the slot index computed using hash function and table_size
represent the hash table size. Suppose hash(key)
index has a value occupied already, then:
We check if (hash(key) + 1) % table_size is free
If ((hash(key) + 1) % table_size) is also not free, then we check for ((hash(key) + 2) % table_size)
If ((hash(key) + 2) % table_size) is again not free, then we try ((hash(key) + 3) % table_size),
:
:
:
and so on until we find the next available free slot
Quadratic Probing:
hash(key)
be the slot index required to place key computed using hash function and table_size
is the size of hash table available, then: If slot (hash(key) % table_size) is not free, then we check for availability of ((hash(key) + 1*1) % table_size)
If ((hash(key) + 1*1) % table_size) is again full, then we check for ((hash(key) + 2*2) % table_size)
If ((hash(key) + 2*2) % table_size) is not empty, then we check for the status of ((hash(key) + 3*3) % table_size)
:
:
:
and so on until we find the next available empty slot.
Double Hashing:
(hash1(key) + c * hash2(key)) % Table_Size , where c keeps incremented by 1 upon every collision to find the next free slot.
hash1()
is the first hash function and hash2()
is the second hash function applied in case of collision and Table_Size
is the size of hash table.hash1(key) = key % Table_Size
. Second hash function is popularly like hash2(key) = prime_no – (key % PRIME)
where prime_no
is a prime number smaller than Table_Size
.table_size
as total number of slots in the hash table, n
as number of keys to be inserted into the table, then:
* Load factor, α = n/table_size ( α < 1 )
* Expected time taken to search/insert/delete operation < (1/(1 - α))
* Hence, search/insert/delete operations take at max (1/(1 - α)) time
Log In using