Linear Probing

Below is a hash table that uses a hash function of key % 10. Starting with an empty table, the following operations are performed on the table.

HashInsert(newTable, item 25)
HashInsert(newTable, item 54)
HashInsert(newTable, item 27)
HashInsert(newTable, item 84)
HashInsert(newTable, item 83)
HashRemove(newTable, 25)

Give the bucket number where the following search will end up with after executing the following search operation?

HashSearch(newTable, 74)

0 1 2 3 4 5 6 7 8 9
83 54 ghost 84 27

Question

Linear Probing

Below is a hash table that uses a hash function of key % 10. Starting with an empty table, the following operations are performed on the table.

HashInsert(newTable, item 25)
HashInsert(newTable, item 54)
HashInsert(newTable, item 27)
HashInsert(newTable, item 84)
HashInsert(newTable, item 83)
HashRemove(newTable, 25)

Give the bucket number where the following search will  end up with  after executing  the following search operation?

HashSearch(newTable, 74)

0	1	2	3	4	5	6	7	8	9
			83	54	ghost	84	27

BlackTom AI · Accepted Answer

Linear probing uses hash(key) = key % 10, so the initial probe index for 74 is 74 % 10 = 4.

Relevant concepts:
- Hash index = key mod table_size (here 10).
- Linear probing: if the probe slot is occupied by a different key or a deleted marker ("ghost"), advance to the next slot (index+1 mod table_size) and continue.
- A deleted slot (tombstone or "ghost") does not terminate a search — only an empty (never-used) slot does.

Step-by-step reasoning and intermediate steps:
1. Compute initial index: 74 % 10 = 4. So the search checks bucket 4 first.
2. Inspect bucket 4: it contains 54 (from earlier inserts). Since 54 ≠ 74, continue probing.
3. Advance to bucket 5 (linear probing): bucket 5 is marked "ghost" (deleted item 25). A ghost does not mean the key is absent for sure, so continue probing.
4. Advance to bucket 6: contains 84. 84 ≠ 74, continue probing.
5. Advance to bucket 7: contains 27. 27 ≠ 74, continue probing.
6. Advance to bucket 8: in the table this bucket is empty (no entry). An empty slot means the key was never inserted beyond this point, so the search terminates here and reports failure — the probe stops at bucket 8.

Why the correct answer is 8:
- The probe sequence for 74 is 4 → 5 → 6 → 7 → 8.
- None of the visited occupied slots match 74, and the deleted slot at 5 does not stop the search.
- The first truly empty slot is bucket 8, so the search ends at 8.

Why other buckets are not the termination point:
- Bucket 4, 6, and 7 contain other keys, so the search must continue.
- Bucket 5 is a deleted/tombstone slot and does not terminate the search.
- Any earlier bucket is therefore not the stopping point; bucket 8 is the first empty slot.

Final confirmation: the search for 74 ends at bucket 8, matching the provided answer (8).

类似问题

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)?

A project has a required return of 12.6 percent, an initial cash outflow of $42,100, and cash inflows of $16,500 in Year 1, $11,700 in Year 2, and $10,400 in Year 4. What is the net present value?

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单