1 思想：哈希表是根据设定的
哈希函数H(key)和处理冲突方法将一组关键字映射到一个有限的地址区间上，并将关键字对应的值存储在该地址空间，可以通过关键字快速获取对应的值，这种表称为哈希表或散列，所得存储位置称为哈希地址或散列地址。作为线性数据结构与表格和队列等相比，哈希表无疑是查找速度比较快的一种。2 查找复杂度: O(1)
3 哈希函数：
- 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a?key + b，其中a和b为常数（这种散列函数叫做自身函数）
- 数字分析法：因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。
- 平方取中法：取关键字平方后的中间几位作为散列地址
- 折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。
- 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。
4 hash冲突及解决 hash冲突在所难免，解决冲突是一个复杂问题。冲突主要取决于： （1）与散列函数有关，一个好的散列函数的值应尽可能平均分布。 （2）与解决冲突的哈希冲突函数有关。 （3）与负载因子的大小。太大不一定就好，而且浪费空间严重，负载因子和散列函数是联动的。 解决冲突的办法： （1）开放定址法：线性探查法、平方探查法、伪随机序列法、双哈希函数法。 （2)
拉链法：把所有同义词，即hash值相同的记录，用单链表连接起来。5 应用： 1.字符串哈希 2.加密哈希 3.几何哈希 4.布隆过滤器
6 不足：获取有序序列复杂度高
参考： http://www.tuicool.com/articles/RnErui
分享到:
閱讀更多 醉人Ryu 的文章
