HT-Linear Probing

Consider a hash table named numTable that uses linear probing and a hash function of key % 5. What is the status of bucket 4 after the following operations?

(Buckets are numbered as 0, 1,2,3, ...)

HashInsert(numTable, item 24)
HashInsert(numTable, item 33)
HashInsert(numTable, item 51)
HashInsert(numTable, item 44)
HashInsert(numTable, item 52)
HashRemove(numTable, 44)
HashInsert(numTable, item 50)

Question

HT-Linear Probing

Consider a hash table named numTable that uses linear probing and a hash function of key % 5. What is the status of bucket 4 after the following operations?

(Buckets are numbered  as 0, 1,2,3, ...)

HashInsert(numTable, item 24)
HashInsert(numTable, item 33)
HashInsert(numTable, item 51)
HashInsert(numTable, item 44)
HashInsert(numTable, item 52)
HashRemove(numTable, 44)
HashInsert(numTable, item 50)

BlackTom AI · Accepted Answer

Hash index is key % 5, so compute each key’s target bucket and follow linear probing (increment index, wrapping mod 5) when a bucket is occupied.

Relevant concepts:
- Hash function: index = key % 5 (buckets 0–4).
- Linear probing: on collision, try next index (i+1 mod table_size) until an available slot is found.
- Removal may leave a tombstone (a "removed" marker) so subsequent probes/insertions consider that slot usable for insertion but not equivalent to “empty-since-start.”

Step-by-step reasoning and intermediate calculations:
1. Insert 24: 24 % 5 = 4 → bucket 4 is empty, place 24 in bucket 4.
   State: b0: -, b1: -, b2: -, b3: -, b4: 24
2. Insert 33: 33 % 5 = 3 → bucket 3 empty, place 33 in bucket 3.
   State: b0: -, b1: -, b2: -, b3: 33, b4: 24
3. Insert 51: 51 % 5 = 1 → bucket 1 empty, place 51 in bucket 1.
   State: b0: -, b1: 51, b2: -, b3: 33, b4: 24
4. Insert 44: 44 % 5 = 4 → bucket 4 occupied (24), linear probe to (4+1)%5 = 0 → bucket 0 empty, place 44 in bucket 0.
   State: b0: 44, b1: 51, b2: -, b3: 33, b4: 24
5. Insert 52: 52 % 5 = 2 → bucket 2 empty, place 52 in bucket 2.
   State: b0: 44, b1: 51, b2: 52, b3: 33, b4: 24
6. Remove 44: removes item in bucket 0. Bucket 0 becomes "removed" (tombstone) but bucket 4 is unaffected and still contains 24.
   State: b0: removed, b1: 51, b2: 52, b3: 33, b4: 24
7. Insert 50: 50 % 5 = 0 → probe starts at bucket 0, sees a removed slot and typically inserts into that slot. This insertion affects bucket 0, not bucket 4. Bucket 4 remains containing 24 (occupied).

Why the correct answer is "occupied":
Bucket 4 was filled by 24 on the first insertion and was never removed. No later operation evicted or relocated the item at bucket 4. Therefore bucket 4 remains occupied.

Why other options are wrong:
- "empty-since-start": false — bucket 4 was occupied by 24 early on.
- "removed from table": false — 24 was never removed.
- "empty-after-removal": false — no removal targeted bucket 4, so it did not become empty.

Conclusion: The final status of bucket 4 is occupied, 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)?

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搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单