Linear Probing

Consider a hash table named idTable that uses linear probing and a hash function of key % 10.

Which bucket will 97 be inserted to?

HashInsert(idTable, item 97)

0 1 2 3 4 5 6 7 8 9
??? ??? 92 ??? ??? 45 76 67 78 79

Question

Linear Probing

Consider a hash table named idTable that uses linear probing and a hash function of key % 10.

Which bucket will 97 be inserted to?

HashInsert(idTable, item 97)

0	1	2	3	4	5	6	7	8	9
???	???	92	???	???	45	76	67	78	79

BlackTom AI · Accepted Answer

Linear probing inserts at hash(key) = key % table_size, and if that bucket is occupied it checks the next index, continuing sequentially and wrapping modulo the table size until an empty bucket is found.

1) Relevant concepts
- Hash function: key % 10 gives the initial bucket index for a table of size 10.
- Linear probing: if the initial bucket is occupied, try (index + 1) mod 10, then (index + 2) mod 10, etc., stopping at the first empty slot.

2) Step-by-step reasoning and calculations
- Compute the hash index: 97 % 10 = 7.
- Check bucket 7: table shows 67 occupying index 7 → occupied.
- Probe next index: 8 (7 + 1 mod 10). Index 8 contains 78 → occupied.
- Probe next index: 9 (8 + 1 mod 10). Index 9 contains 79 → occupied.
- Probe next index: 0 (9 + 1 mod 10 wraps to 0). Index 0 shows ??? (empty) → first available slot.

Intermediate steps explicitly:
- 97 % 10 = 7
- Check indices in order: 7 (occupied), 8 (occupied), 9 (occupied), 0 (empty) → insert at 0.

3) Why the correct answer is correct
Because linear probing inserts at the first empty bucket encountered starting from the hashed index 7 and moving forward with wrap-around. The first empty bucket encountered in that probe sequence is index 0, so 97 is inserted into bucket 0.

4) Why the other options are incorrect
- 3, 1, 4: although some of these indices are empty in the table, they are not the first empty slot encountered when probing from the initial hash index 7. Probing found index 0 empty before ever reaching indices 1, 3, or 4, so 97 will not be placed in those buckets.

Conclusion: The correct insertion bucket for 97 under linear probing with hash = key % 10 is 0, matching the provided answer.

Linear Probing Consider a hash table named idTable that uses linear probing and a hash function of key % 10. Which bucket will 97 be inserted to? HashInsert(idTable, item 97) 0 1 2 3 4 5 6 7 8 9 ??? ??? 92 ??? ??? 45 76 67 78 79单项选择题

类似问题

HT-Linear Probing (Search) Given the following hash table and a hash function of key % 10, HashSearch(hashTable, 53) probes A buckets. HashSearch(hashTable, 63) probes B buckets. Note that # probes means the #slots that were visited. 1: A 2: B

Consider the hash table of size 11 that uses linear probing shown below, where the hash function is h(k) = (k mod 11). Thus h(14)=3, h(25)=3. What indices are examined if we now perform get(3)?

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单