What is Collision in Hashing?

In hashing, collisions occur when two or more keys yield the same hash value or hash code. Collisions are unavoidable because hash algorithms transfer a theoretically unlimited collection of keys to a finite range of hash results.

We have certain collision strategies that we can use to resolve these problems.

The collision techniques are as follows:

1. Open Addressing
2. Closed addressing( or Chaining)

Open addressing:

When a collision occurs in open addressing, a new slot within the hash table is found to store the item. There are various methods for doing this, including linear probing, quadratic probing, and double hashing.

• Linear Probing: If a collision occurs in linear probing, the method searches for the next available slot in the hash table, beginning at the collision site and progressing sequentially to the next slot until an empty slot is discovered. The formula for linear probing is:

h(k, i) = (h'(k) + i) % m

• where:
  • h(k, i) is the hash value for key k after i probes
  • h'(k) is the initial hash value for key k
  • i is the number of probes made
  • m is the size of the hash table

Example:

Suppose we have a hash table of size 7 and want to insert the following keys:

18

14

21

44

Our Hash Functo would be:

h(k) = k % 7
i.e,
h(18) = 4
h(14) = 0
h(21) = 0
h(44) = 2

As we can see to insert 21, we encounter a collision at slot 0, so we use linear probing to find the next available slot, which is slot 1.

Output:

Slot	Keys
0	14
1	21
2	44
3
4	18
5
6
7

• Quadratic Probing: Quadratic probing is similar to linear probing in that it searches for an empty slot using a quadratic function rather than sequentially. The formula for quadratic probing is:

h(k, i) = (h'(k) + c1 * i + c2 * i^2) % m

• where:
  • h(k, i) is the hash value for key k after i probes
  • h'(k) is the initial hash value for key k
  • c1 and c2 are constants used to control the probe sequence
  • i is the number of probes made
  • m is the size of the hash table

Example:

Considering the above example-

When we try to insert 41, we encounter a collision at slot 6, so we use quadratic probing to find the next available slot. The next probe is at slot (6 + 11 + 31^2) % 7 = 3. However, slot 3 is not empty, so we continue probing with i = 2, which gives us slot (6 + 12 + 32^2) % 7 = 5. The final hash table will look like this:

Slot	Key
0	41
1	22
2	44
3
4

• Double Hashing: To find the next slot to place the item in, double hashing employs two hash functions. If there is a collision, the method utilises the second hash function to determine how many slots to skip before attempting to store the item. The formula for double hashing is:

h(k, i) = (h1(k) + i * h2(k)) % m

• where:
  • h(k, i) is the hash value for key k after i probes
  • h1(k) is the first hash function for key k
  • h2(k) is the second hash function for key k
  • i is the number of probes made
  • m is the size of the hash table

Chaining:

In chaining, each hash table slot holds a linked list of items with the same hash code. When there is a collision, the new item is added to the linked list in the slot that corresponds to its hash code.

Working:

Here’s how chaining works in more detail:

1. Initialize an empty hash table with n slots.
2. Using a hash function, compute the hash value of each key and map it to a space in the hash table. If there is a collision (two keys hash to the same slot), add the new key to the linked list in the corresponding slot.
3. To find a key, calculate its hash value and traverse the linked list in the relevant slot until the key is discovered or the list is filled.
4. To add a new key, compute its hash value and enter it into the linked list in the appropriate slot.
5. To delete a key, compute its hash value and remove it from the linked list in the corresponding slot.

Example:

Suppose we have a hash table of size 5, and we want to insert the following keys-

10

22

37

45

52

The the Hash Function would be:

h(k) = k % 5
i.e,
h(10) = 0 
h(22) = 2 
h(37) = 2 
h(45) = 0 
h(52) = 2

Since keys 10 and 45 hash to the same slot, we create a linked list containing both keys in slot 0. Keys 22, 37, and 52 all hash to slot 2, so we create a linked list in that slot containing those keys.

Output: final hash table

Slot	Keys
0	10, 45
1
2	22, 37, 52
3
4

Note: also read about DSA: Collision in Hashing

Follow Me

If you like my post please follow me to read my latest post on programming and technology.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py