Hashing

collision

• Static Hashing Schemes
• linear probe hashing: find next available
• good for insert but bad for delete and update
• if non-unique key
• Choice #1: Separate Linked List. key point to a table save all value
• Choice #2: Redundant Keys: Store duplicate keys entries together in the hash table.
• ROBIN HOOD HASHING:
• Variant of linear probe hashing that steals slots from "rich" keys and give them to "poor" keys.
• Each key tracks the number of positions difference its optimal position in the table.
• no grantee better, avoid worst case
• cuckoo hashing
• Use multiple hash tables with different hash functions.
• ping pong, 出现collision去另一个
• 如果两个都collision，选一个替换，把被替换的放在另一个table里
• If we find a cycle, then we can rebuild the entire hash tables with new hash functions.
• Dynamic Hashing Schemes
• chained hashing: use linkedlist
• grow infinitely because you just keep adding new buckets to the linked list.
• extendible hashing
• split buckets
• local depth: 就是之前没分的长度
• linear hashing
• Maintain a pointer that tracks the next bucket to split.
• When any bucket overflows, split the bucket at the pointer location.

python dict

• 存hash|key|value，每次都是看hash和key是不是一样
• 处理collusion
  • 出现collision，看j = ((5*j) + 1) mod 2**i 下一个是不是空的，是的话就放进去

---

Backlinks

• Algo (my_note)