Cure: rehashing. Jab tombstones bahut zyada ho jayein (e.g. αeff ek threshold jaise 0.7 exceed kare), table rebuild karo: sirf OCCUPIED entries ko ek fresh array mein reinsert karo, saare tombstones drop karo. Yeh αeff ko true live load factor par reset kar deta hai.
Recall Forecast: m=5, h(k)=k mod 5, linear probing. 5,10,15 insert karo (sab 0 par hash karte hain). Phir 10 delete karo. 15 ko search karo — kitne probes, aur har slot kya read karta hai?
Insert: 5→slot0, 10→slot1, 15→slot2. Table [5 10 15 _ _].
10 delete karo → tombstone: [5 † 15 _ _].
15 search karo: slot0 probe karo (=5, nahi), slot1 (=†, jaari rakho), slot2 (=15 ✔). 3 probes. Tombstones ke bina, slot1 EMPTY search ko 2 probes par rok deta aur galat "not found" report karta.
Open addressing mein slot ko EMPTY set karke delete kyun nahi kar sakte?
EMPTY ka matlab hai "probe sequence khatam," toh beech ke slot ko blank karna baad ki searches ko chain mein jaldi rokwa deta hai aur keys ko missing report karta hai.
Tombstone marker kya hai?
Ek special DELETED slot state jiska matlab hai "ek key yahan se hatayi gayi hai, lekin probing jaari rakho" — yeh search chain ko preserve karta hai.
SEARCH tombstone ko kaise treat karta hai?
Ek occupied slot ki tarah — yeh probing jaari rakhta hai; sirf EMPTY par ya key milne par rukta hai.
INSERT tombstone ko kaise treat karta hai?
Reusable free space ki tarah: pehla tombstone yaad rakho, lekin yeh ensure karne ke liye ki koi duplicate nahi hai EMPTY tak scan karte raho, phir key yaad kiye gaye tombstone par rakho.
Open addressing mein deletion ke saath teen slot states kya hain?
EMPTY, OCCUPIED, DELETED (tombstone).
Effective load factor kya hai aur yeh kyun matter karta hai?
αeff=(noccupied+ntombstones)/m; search cost isi par depend karti hai, toh tombstones lookups slow karte hain chahe live keys kam hon.
Accumulated tombstones se kaise chutkara milta hai?
Rehash/rebuild: sirf OCCUPIED entries ko fresh table mein reinsert karo, saare tombstones drop karo; αeff reset ho jaata hai.
Insert mein pehle tombstone par key rakhne ki jagah aage scan karna kyun zaroori hai?
Key probe chain mein aage pehle se exist kar sakti hai; jaldi rukne se duplicate insert hone ka risk hai.
Recall Feynman: ek 12-saal ke bachche ko explain karo
Ek row of lockers imagine karo aur apna samaan dhundhne ka ek rule: "locker 3 se shuru karo; agar yeh tumhara nahi hai, agla try karo, aur agla — jab tak tumhara na mile YA ek empty locker na mile, jiska matlab hai ruko, tumhara samaan yahan nahi hai." Ab agar koi tumhare trail ke beech ek locker khali kar deta hai, tum us empty locker se takraoge aur bahut jaldi quit kar doge, agले locker mein apna samaan miss karte hue. Toh khali chhodne ki jagah, hum ek chhoti "yahan tha" sticky note (tombstone) lagate hain. Jab tum sticky note dekhte ho tum sochte ho "aage chalte raho!" aur tumhe apna samaan mil jaata hai. Kaafi sticкies pile up hone ke baad, trails lambi ho jaati hain, toh kabhi kabhi hum poori row saaf karte hain aur sab kuch wapas se neat tarike se rakhte hain.
