1 思想:哈希表是根据设定的
2 查找复杂度: O(1)
3 哈希函数:
直接寻址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a?key + b,其中a和b为常数(这种散列函数叫做自身函数)数字分析法:因此数字分析法就是找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址。比如一组员工的出生年月日,这时我们发现出生年月日的前几位数字大体相同,这样的话,出现冲突的几率就会很大,但是我们发现年月日的后几位表示月份和具体日期的数字差别很大,如果用后面的数字来构成散列地址,则冲突的几率会明显降低。4 hash冲突及解决 hash冲突在所难免,解决冲突是一个复杂问题。冲突主要取决于: (1)与散列函数有关,一个好的散列函数的值应尽可能平均分布。 (2)与解决冲突的哈希冲突函数有关。 (3)与负载因子的大小。太大不一定就好,而且浪费空间严重,负载因子和散列函数是联动的。 解决冲突的办法: (1)开放定址法:线性探查法、平方探查法、伪随机序列法、双哈希函数法。 (2) 拉链法:把所有同义词,即hash值相同的记录,用单链表连接起来。
5 应用: 1.字符串哈希 2.加密哈希 3.几何哈希 4.布隆过滤器
6 不足:获取有序序列复杂度高
参考: http://www.tuicool.com/articles/RnErui