多槽位multiple slots
桶单元细分成若干槽位slot，存放（与同一单元）冲突的词条
只要槽位数目不多，依然可以保证O(1)的时间效率
但是，难以预测需要为每个桶配备多少个槽位才能保证O(1)，若预留过多则空间浪费，无论预留多少，极端情况下仍有可能不够
独立链linked-list chaining
每个桶存放一个指针，冲突的词条组织成列表
优点：无需为每个桶预留多个槽位，任意多次的冲突都可解决，删除操作实现简单、统一
缺点：指针需要额外空间，节点需要动态申请，更重要的是，空间未必连续分布，系统缓存几乎失效
开放定址open addressing~closed hashing
为每个桶都事先约定若干备用桶，它们构成一个查找链probing sequence/chain
查找：沿查找链，逐个转向下一桶单元，直到命中成功或者抵达一个空桶（已遍历所有冲突的词条）
线性试探linear probing：一旦冲突，则试探后一紧邻桶单元；
[hash(key)+1]%M，[hash(key)+2]%M，[hash(key)+3]%M，...... 直到命中成功或者抵达一个空桶
优点：无需附加的（指针、链表或溢出区等）空间，查找链具有局部性，可充分利用系统缓存，有效减少I/O
缺点：操作时间>O(1)，冲突增多——以往的冲突会导致后续的冲突clustering
懒惰删除
按照开放定址策略：先后插入，相互冲突的一组词条，将存放于同一查找链中
若需删除其中某一词条，应如何实现？
lazy removal：仅做删除标记，查找链不必续接
