CMU-15-445-笔记(四)

Index

Hash Table

Hash Function

• CRC-64
• MurmurHash
• Google CityHash
• Facebook XXHash
  • 一般用这个
• Google FarmHash

Static Hasing Schemes

Linear Probe Hasing

就是线性探测法

Non-Unique-Keys

键可能是重复的情况

Separate Linked List

将值存在列表中

Redundany Keys

直接把键存入hash table中

Robin Hood Hashing

Robin Hood Hashing 会记录每个key在hash table中距离它最优位置的距离。当一个key插入的时候，会比较插入位置的key距离最优位置和即将插入key距离最优位置的大小，如果后者大，则交换两者的位置。

Cuckoo Hashing

使用多个hash table，并且每个hash table都有不同的seed。

• 当插入一个键的时候，检查所有的table然后选择一个hash后的空槽。
• 如果没有空槽，那么就删掉一个元素，然后给这个元素rehash一下找新的位置
  
  
  
  
  
  

Dynamic Hash Tables

Chained Hashing

如果hash到同一个桶，那就用链表连接下去

Extendible Hashing

Extendible Hasing不同的hash值可以公用一个页，当页满的时候，就会扩hash值，重新rehash，寻找一个值的时候，会去对应的页线性查找

Linear Hashing

hash table维护一个分裂指针，表示当前指针以上都进行了分裂，需要进行二次hash才能获取其真正位置。当一个页overflows的时候，会在页后追加页，并且分裂当前分裂指针指向的桶，指针下移