散列
散列表用的是数组支持按照下标随机访问数据的特性,所以散列表其实就是数组的一种扩展,由数组演化而来。可以说,如果没有数组,就没有散列表。
散列函数
散列函数要求:
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)发生非常大的变化
参考:
对于“整数型”参数(“浮点型”可强转成“整数”处理),对一个素数取模:
“字符串型” 转换成 “整数型”,然后再取模: