---
title: "Hashing and different hash functions"
subject: "Data Structure and Algorithm"
chapter: 8
key: "semester_4/data_structure_and_algorithm:hashing-hash-functions"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/hashing-hash-functions
site: BCT Engineering
---

# Hashing and different hash functions

Data Structure and Algorithm · Chapter 8: Searching

- Asked in: 2068 Bhadra, 5 marks
- Video: [Hash function and types of functions || Hash  Function || Data Structures](https://www.youtube.com/watch?v=XjuubzPPjyE) — Lab Mug
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/hashing-hash-functions
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-8

## Question

Define hashing and demonstrate different hash functions.

## Short answer

Hashing maps a key to a table address via a hash function, enabling O(1) average operations. Common hash functions include the division method (k mod m), mid-square (middle digits of k²), folding (split key into parts and add), digit extraction, and the multiplication method (floor(m*(k*A mod 1))).

## Answer

**Hashing** is a technique of storing and retrieving records directly by computing their address from the key with a **hash function** h(k). The records are kept in a **hash table** of size *m*, so insert, search and delete take O(1) time on average. When h(k1) = h(k2) for different keys, a collision occurs and must be resolved.

A good hash function is easy to compute and spreads keys uniformly over 0 to m−1.

#### Common hash functions
1. **Division method:** h(k) = k mod m. Choose m as a prime not close to a power of 2. Example: k = 1234, m = 11: h = 1234 mod 11 = 2.
2. **Mid-square method:** square the key and take the middle digits. Example: k = 4567, k² = 20857489; the middle two digits are 57, so h(k) = 57.
3. **Folding method:** divide the key into equal parts and add them, ignoring the final carry if required. Example: k = 123456789 gives 123 + 456 + 789 = 1368; keeping the last three digits h(k) = 368. (Boundary folding reverses alternate parts before adding.)
4. **Digit extraction:** pick selected digits of the key. Example: take 1st, 3rd and 5th digits of 98765432: 9, 7, 5, giving h(k) = 975.
5. **Multiplication method:** h(k) = ⌊m·(k·A mod 1)⌋ with 0 < A < 1 (for example A ≈ 0.618).

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does hashing do?
   A. Computes a record's address directly from its key using a hash function
   B. Sorts records by key
   C. Searches each record one by one
   D. Stores records in a linked list
   Answer: A. A hash function maps the key to a table index, giving O(1) average access. (Key point: Hashing idea)

2. 1234 mod 11 using the division method gives what?
   A. 1
   B. 2
   C. 3
   D. 11
   Answer: B. 1234 = 112*11 + 2, so h = 2. (Key point: Division method)

3. Key 4567 has square 20857489. Which two middle digits give the hash by mid-square?
   A. 20
   B. 89
   C. 57
   D. 85
   Answer: C. Taking the middle digits of 20857489 gives 57. (Key point: Mid-square)

4. What is a good choice of m in the division method?
   A. A power of 2
   B. Any even number
   C. A multiple of 10
   D. A prime not close to a power of 2
   Answer: D. A prime away from powers of 2 spreads keys more uniformly. (Key point: Division method choice of m)

## Related in Data Structure and Algorithm

- [Double hashing table with m = 11](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adouble-hashing-table-m11) — Data Structure and Algorithm, chapter 8
- [Hash table with chaining, m = 13](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Ahash-chaining-m13) — Data Structure and Algorithm, chapter 8
- [Binary search for 89; hash functions](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Abinary-search-89-hashing) — Data Structure and Algorithm, chapter 8