--- title: "Hash table with chaining, m = 13" subject: "Data Structure and Algorithm" chapter: 8 key: "semester_4/data_structure_and_algorithm:hash-chaining-m13" source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/hash-chaining-m13 site: BCT Engineering --- # Hash table with chaining, m = 13 Data Structure and Algorithm · Chapter 8: Searching - Asked in: 2071 Magh, 6 marks - Video: [Chained hashing with example | Q.9a | vtu model question paper 2024 solution | DSA | BCS304](https://www.youtube.com/watch?v=WkUejS_oe6U) — CSE Guru - 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/hash-chaining-m13 - Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-8 ## Question Insert the following data elements into hash table using hash function h(k) = k mod m, take m = 13, assume collisions are handled by chaining. Keys for hashing are: 5, 28, 19, 25, 20, 43, 22, 27, and 30. ## Short answer With h(k)=k mod 13 and chaining, the hash table lists are: 1→27, 2→28, 4→43→30, 5→5, 6→19, 7→20, 9→22, 12→25; other slots empty. ## Answer h(k) = k mod 13, collisions handled by chaining (new key added at the end of the list). | Key | k mod 13 | Slot | |---|---|---| | 5 | 5 | 5 | | 28 | 28 − 26 = 2 | 2 | | 19 | 19 − 13 = 6 | 6 | | 25 | 25 − 13 = 12 | 12 | | 20 | 20 − 13 = 7 | 7 | | 43 | 43 − 39 = 4 | 4 | | 22 | 22 − 13 = 9 | 9 | | 27 | 27 − 26 = 1 | 1 | | 30 | 30 − 26 = 4 | 4 (collision with 43) | **Hash table** ```text 0 -> NULL 1 -> 27 -> NULL 2 -> 28 -> NULL 3 -> NULL 4 -> 43 -> 30 -> NULL 5 -> 5 -> NULL 6 -> 19 -> NULL 7 -> 20 -> NULL 8 -> NULL 9 -> 22 -> NULL 10 -> NULL 11 -> NULL 12 -> 25 -> NULL ``` Only one collision occurs (30 with 43 at slot 4). ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. With m = 13, which slot does key 43 hash to? A. 3 B. 30 C. 43 D. 4 Answer: D. 43 = 3*13 + 4, so 43 mod 13 = 4. (Key point: Hash computation) 2. Which key collides with 43? A. 30 B. 28 C. 5 D. 22 Answer: A. 30 mod 13 = 4, the same slot as 43. (Key point: Collision identification) 3. How is 30 stored in the table? A. Placed in slot 5 B. Appended to the list at slot 4 after 43 C. Replaces 43 D. Placed in slot 17 Answer: B. Chaining adds the colliding key to the list at that slot: 4 -> 43 -> 30. (Key point: Chaining insertion) 4. How many collisions occur when inserting all nine keys? A. None B. Two C. One D. Four Answer: C. Only 30 shares a slot with an earlier key (43). (Key point: Number of collisions) ## 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 - [Hashing and different hash functions](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Ahashing-hash-functions) — Data Structure and Algorithm, chapter 8 - [Linear probing insertion into size-10 table](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Ahash-linear-probing-62-37) — Data Structure and Algorithm, chapter 8 - [AVL tree for 10 20 30 50 45 40 8 5 3](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-10-20-30) — Data Structure and Algorithm, chapter 6 - [AVL tree for 10, 20, 30, 35, 50, ...](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aavl-build-10-20-30-35) — Data Structure and Algorithm, chapter 6 - [Collision resolution techniques in hashing](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Acollision-resolution-methods) — Data Structure and Algorithm, chapter 8, asked 3× ## Related in other subjects - [Subnet 202.77.19.0/24 for 30, 24, 25, 20](https://www.bctengineer.com/question.md?key=semester_7%2Fcomputer_networks_and_security%3Asubnetting-202-77-19) — Computer Networks and Security, chapter 4 - [Settling tank 30 m x 3 m, 0.03 mm at 25°C; 0.025 mm at 20°C](https://www.bctengineer.com/question.md?key=semester_5%2Fwater_supply_engineering%3Ased-k72) — Water Supply Engineering, chapter 6, asked 3× - [Irrigation interval: FC 28%, PWP 13%](https://www.bctengineer.com/question.md?key=semester_6%2Firrigation_and_drainage_engineering%3Ainterval-fc28-pwp13-root70) — Irrigation and Drainage Engineering, chapter 2, asked 2× - [Standard error; population 12,19,13,16](https://www.bctengineer.com/question.md?key=semester_5%2Fprobability_and_statistics%3Astandard-error-population-12-19-13) — Probability and Statistics, chapter 4