CMU15445-06-HashTable

• • 哈希方案分类（hash scheme）

    1. 静态哈希：静态哈希方案，这意味着我们在一开始分配内存时就需要知道希望保存的key的数量。

       • 线性探针哈希（Linear Probe Hashing）
         • 墓碑法（Tombstone）和移动法（Movement）解决删除时遇到的空slot问题
       • 罗宾汉哈希（Robin Hood Hashing）
         • 追求平衡，但会带来更多的缓存无效
       • 布谷鸟哈希（Cuckoo Hashing）

    2. 动态哈希

       • 链式哈希（Chained Hashing）
         • 每个 key 对应一个链表，每个节点是一个 bucket，装满了就再往后挂一个 bucket。需要写操作时，需要请求 latch。
         • 
         • 这么做的好处就是简单，坏处就是最坏的情况下 Hash Table 可能降级成链表，使得操作的时间复杂度降格为 O(n) 。
       • 拓展哈希表（Extendible Hashing）
         • 基于链式哈希，可以扩展overflow的chain
         • 
       • 线性散列（Linear Hashing）
    • 上述Extendible Hashing是指数级的扩张hash表的，这未免也太快了。所以便有了LINEAR HASHING，线性扩张hash表，即每次只增加一个。其基本思想是维护一个指针split pointer，其指向下一个被拆分bucket，当任意bucket溢出时，将指针指向的当前bucket的拆分。
      •