Hash Functions

 

Types of Hash Functions

Hash functions play a key role in determining how efficiently a hash table works. Below are some classic hashing techniques used to compute hash values.

---

1. 🟦 Division Method

Formula:

h(k) = k % m

Where:

• k is the key

• m is the size of the hash table (preferably a prime number)

✅ Advantages:

• Simple and fast

• Easy to implement

❌ Disadvantage:

• Poor distribution if m is not chosen wisely (e.g., if m is a power of 2)

🧪 Example:

k = 1234, m = 11
h(1234) = 1234 % 11 = 2

---

2. 🟩 Mid-Square Method

Steps:

1. Square the key.

2. Extract the middle digits of the result.

3. Use those digits as the hash value or apply % m.

🧪 Example:

k = 123

1. Square it: 123² = 15129
2. Extract middle 2 digits (depends on size of table): '51'
3. h(123) = 51 or 51 % m

✅ Advantages:

• Works well for small keys.

• Middle digits are often more "randomized".

❌ Disadvantage:

• Squaring is slower than modulo operation.

---

3. 🟨 Folding Method

This method divides the key into parts (usually of equal length), then adds the parts together to compute the hash.

Techniques:

• Simple Folding: Split into parts and add.

• Folding by Shifting: Reverse alternate parts before adding.

🧪 Example (Simple Folding):

k = 12345678
Split into parts: 1234, 5678
Add: 1234 + 5678 = 6912
Then: h(k) = 6912 % m

🧪 Example (Folding by Shifting):

Parts: 1234, 8765 (reverse second part)
Add: 1234 + 8765 = 9999
Then: h(k) = 9999 % m

✅ Advantages:

• Good for long numeric keys

• Adds variability

❌ Disadvantage:

• Some patterns may still result in collisions.

---

4. 🟥 Digit Analysis Method

This method analyzes specific digits of the key (e.g., only use certain positions like the 2nd and 4th digits).

Use case:

• When we know the dataset characteristics beforehand (e.g., employee IDs).

🧪 Example:

k = 738291
Take 2nd and 4th digits: 3 and 2 → combine → 32
Then: h(k) = 32 or 32 % m

✅ Advantages:

• Can be efficient for structured keys

❌ Disadvantage:

• Can lead to clustering if digits chosen are not well-distributed.

---

📌 Summary Table

Method	Idea	Pros	Cons
Division	k % m	Simple, fast	Needs good m, may cluster
Mid-Square	Square key, take middle digits	Random distribution	Slower due to squaring
Folding	Break into parts, add them	Handles large keys	Needs careful part selection
Digit Analysis	Use selected digits	Fast for structured keys	Not generic; risks clustering

Learn More on Hash Functions