散列函数设计要求

• 散列函数计算得到的散列值是一个非负整数
• 如果 key1 = key2, 那 hash(key1) == hash(key2)
• 如果 key1 ≠ key2, 那 hash(key1) != hash(key2)

解决散列冲突

开放寻址法

如果冲突, 那么再重新探测一个空闲位置.

探测方法

• 线性探测

• 二次探测, 线性探测每次加1, 而二次探测每次加平方:
• 双重散列, 当冲突后使用其他散列函数继续散列

链表法

装载因子

表示空位的多少.

散列表的装载因子 = 填入表中的元素个数/散列表的长度

如何打造工业级哈希表

• 初始大小
• 装载因子
• 动态扩容
  • 慢慢扩容
• 哈希函数
  • 不能太复杂
  • 生成的值尽可能随机, 均匀分布
• 冲突解决方法的优缺点