written 6.1 years ago by |
Situation of collision occurs when more than one keys (hash functions) map to the same location of hashes. In this situation, two or more data elements qualify to be mapped to the same location in hash table.
Collision resolution can be done using two techniques:
1. Open Addressing
2. Chaining
Open Addressing: In this technique a hash table with per-identified size is considered. All items are stored in the hash table itself. In addition to the data, each hash bucket also maintains the three states: EMPTY, OCCUPIED, DELETED. While inserting, if a collision occurs, alternative cells are tried until an empty bucket is found. For which one of the following technique is adopted.
1.Liner Probing(this is prone to clustering of data + Some other constrains)
2.Quadratic probing
3.Double hashing(in short in case of collision another hashing function is used with the key value as an input to identify where in the open addressing scheme the data should actually be stored.)
Chaining: Open Hashing, is a technique in which the data is not directly stored at the hash key index (k) of the Hash table. Rather the data at the key index (k) in the hash table is a pointer to the head of the data structure where the data is actually stored. In the most simple and common implementations the data structure adopted for storing the element is a linked-list.