1 哈希函数特点

• 输入域无限，输出域有限

• 对于同一哈希函数，输入相同，输出一定相同

• 哈希函数的输出值在一定范围内具有离散性，哈希函数的输出值 % m (即对m取模)后，结果仍就有均匀性

  由第一个特性，对于不同的输入，哈希函数的输出有可能相同，即存在哈希碰撞。
  由第三个特性，当输入数量足够大时，哈希函数的输出值在一定域内（如 0 ~ m-1）的分布是离散的，且碰撞到域中的每个值的数量是几乎均匀的。

2 哈希表的扩容

当哈希表的碰撞累计数量超出一定范围是，哈希表在碰撞链上的查询需消耗更多的时间（尽管碰撞链的查询是线性的）

此时需要对哈希表进行扩容，一般哈希表的初始容量设为奇数（可稍稍提高输出的均匀性），当扩容时，如从17 -> 34，需要对哈希表的内容重新计算哈希值。理论上，平均每插入一个数据，哈希表扩容的时间成本为 ，由于其常数项非常小，故可近似视为 。

此外，对于使用虚拟机的语言，如Java中的JVM，虚拟机会在后台离线扩容，从而不占用用户在线等待时间，进一步减少了哈希表扩容时间成本（用户在线等待的时间成本）。

C++，C等无虚拟机，故每次扩容为在线扩容。