[DS2] Hash Table

1. Hash Table

1.1 Components

The Hash table data structure stores elements in the key-value pairs where

• Key : unique integer that is used for indexing the values
• Value : data that are associated with keys

1.2 Hashing

In a hash table, a new index is processed using the keys. And the element corresponding to that key is stored in the index. This process is called hashing. Let k be a key and h(x) be a hash function. Here, h(k) will give us a new index to store element linked with k.

 

1.3 Hash Collision

When the hash function generates the same index for multiple keys, thhere will be a conflict. This is called a hash collision. The solutions for hash collision are same as below :

• Collision resolution by chaining
• Open Addressing : Linear/Quadratic Probing and Double Hashing

Chaining

In chaining, if a hash function produces the same index for multiple elements, these elements are stored in the same index by using a doubly-linked list.

Open Addressing

In linear probing, collision is resolved by checking the next slot. $$h(k, i) = (h'(k) + i) % m$$

If a collision occurs at h(k, 0), then h(k, 1) is checked.

 

In quadratic probing, it works similar to linear probing but the spacing between the slots is increased.

$$h(k, i) = (h'(k) + c_1 i + c_2 i^2 ) % m $$

 

In double hashing, another hash funciton is calculated for finding the next slot.

$$h(k, i) = (h_1(k) + ih_2(k)) % m$$

 

1.3 Good Hash function

1. Division Method : If k is a key and m is the size of the hash table, the hash function h(k) is calculated as h % k.
2. Multiplication Method : \(h(k) = [m(kA \% 1)]\)
3. Universal Hashing : hash function is chosen at random independent of keys.

 

2. Source of the contents

https://www.programiz.com/dsa/hash-table

Hash Table Data Structure