The keys 5, 28, 19, 15, 26, 33, 12, 17, 10 are inserted into a hash table using the hash function $h(k) = k \mod 9$. The collisions are resolved by chaining. After all the keys are inserted, the length of the longest chain is ________. (answer in integer)
Show Hint
Solution and Explanation
Step 1: Understanding the Concept:
Chaining involves storing multiple keys that map to the same hash index in a linked list (chain). The length of the chain is the number of keys at that index.
Step 2: Key Formula or Approach:
Calculate the index for each key using \( index = key \mod 9 \).
Step 3: Detailed Explanation:
Let's compute the indices:
- \( 5 \mod 9 = 5 \)
- \( 28 \mod 9 = 1 \)
- \( 19 \mod 9 = 1 \)
- \( 15 \mod 9 = 6 \)
- \( 26 \mod 9 = 8 \)
- \( 33 \mod 9 = 6 \)
- \( 12 \mod 9 = 3 \)
- \( 17 \mod 9 = 8 \)
- \( 10 \mod 9 = 1 \)
Mapping keys to indices:
- Index 1: $\{28, 19, 10\}$ $\rightarrow$ Length = 3
- Index 3: $\{12\}$ $\rightarrow$ Length = 1
- Index 5: $\{5\}$ $\rightarrow$ Length = 1
- Index 6: $\{15, 33\}$ $\rightarrow$ Length = 2
- Index 8: $\{26, 17\}$ $\rightarrow$ Length = 2
Step 4: Final Answer:
The longest chain is at Index 1 with a length of 3.
Top Questions on Hashing
- In ................. the search time is independent of the number of elements $n$.
- All the elements that hash to the same slot are placed into the same linked list in:
- Suppose we are given \(n\) keys, \(m\) hash table slots, and two simple uniform hash functions \(h_1\) and \(h_2\). Further suppose our hashing scheme uses \(h_1\) for the odd keys and \(h_2\) for the even keys. What is the expected number of keys in a slot?
- GATE CS - 2022
- Algorithms
- Hashing
Consider a dynamic hashing approach for 4-bit integer keys:
- There is a main hash table of size 4.
- The 2 least significant bits of a key are used to index into the main hash table.
- Initially, the main hash table entries are empty.
- To resolve collisions, the set of keys corresponding to a main hash table entry is organized as a binary tree that grows on demand.
- First, the 3rd least significant bit is used to divide the keys into left and right subtrees.
- Further collisions are resolved by subdividing based on the 4th least significant bit.
- A split is done only if needed, i.e., only when there is a collision.
Consider the following state of the hash table. Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?
- GATE CS - 2021
- Algorithms
- Hashing
- Want to practice more? Try solving extra ecology questions todayView All Questions