散列

散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。

散列函数

散列函数要求：

• hash(str) > 0

• 当key1 == key2，有hash(key1) == hash(key2)

• 当key1 != key2，尽量有hash(key1) != hash(key2)

最后一点要求只能尽量满足，如果hash(key1) == hash(key2)了，则称为“哈希冲突”。

设计：

• 计算不能太复杂

• 生成的数组下标值尽量“随机”且“分布均匀”

• f(x) = hash(x)，x的微小变化可以使f(x)发生非常大的变化

参考：

对于“整数型”参数（“浮点型”可强转成“整数”处理），对一个素数取模：

“字符串型” 转换成 “整数型”，然后再取模：

解决冲突

开放寻址法

链表法