1.Hash 的基本原理
总共有 M-1 个桶, hash(key) 指向一个特定的桶.
2.Hash function 散列函数
略
3. 哈希冲突及解决
闭合定址 (closed addressing):
linked-list chaining: 每个桶存放一个指针, 冲突的词条组织成列表. 新进来的插在第一个和第二个之间.
缺点是 1. 指针需要额外空间; 2. 节点需要动态申请
开放定址 (open addressing/closed hashing):
为每个桶事先约定若干备用桶, 它们构成一个查找链 (probing sequence).probing 的时候, 沿查找链逐个转向下一桶单元, 直到命中成功或者已遍历全部冲突的词条.
两种 closed hashing 方法:
1.linear probing
2.squre probing
来源: http://www.bubuko.com/infodetail-3356092.html