哈希小结
? 上学期就已经学过hash表，最近又将hash重看了一遍，以前只是稍微了解一下hash表的表皮知识，这次对
?
hash的代码有了一点的了解，上了一个档次啊，(*^__^*) 嘻嘻……
?
? ?今日这篇博客，觉得很肤浅，基本上都是理解而已，我现在还没有把hash剖析，我很想把它搞的更深一点再
?
写，但已经好久没有写关于java的博客了，这叫我感觉自己没有干啥事似的，更何况接下来半个月也不能专注这
?
个，半个月后可能就没有感觉了，还是决定记下现在的东西，毕竟写博客是很让我头疼的事情，映像会更加深刻
?
吧。
?
一.定义
?
1 何为hash表？
?
? ?哈希（hash）表是一种表，该表中存储的关键字是由hash函数和处理冲突的方法映射的，存储的地址为hash地
?
址或散列地址，这一映像过程为散列，或哈希造表。
?
2. 何为哈希函数？
?
? ? ?哈希函数就是一种关系f，是关键字与其在哈希表中存储位置的一种确定的对应关系。
?
3. 冲突
?
? ? 对不同的关键字，通过哈希函数映射后，可能会得到相同的哈希地址，这就产生了哈希冲突。产生冲突的关键
?
字叫做同义词。
?
二.哈希函数的构造方法
?
1. 直接定址法：关键字或关键字的某个线性函数值就是哈希地址。
适合：地址集合大小=关键字集合大小
2. 数字分析法：取关键字的若干数位组成哈希地址
? 适合：预先估计出全体关键字的每一位上的均匀位数或若干数位
3. 平方取中法：取关键字平方后的中间几位为哈希地址
适合：关键字中的每一位都有某些数字重复出现频度很高的现象
4. 折叠法：将关键字的若干位数分成相同 的几部分（最后一部分可以不同），然后将这几部分叠加（舍去进
?
位）求的和，作为哈希地址。
适合：关键字位数很多，且关键字中的每一位上数字分布较均匀
5. 除留余数法：关键字被某个不大于表长的数字p整除后的余数为哈希地址
6. 随机数法：取关键字的随机函数值为哈希地址
适合：关键字长度不等时
?
三. 处理冲突方法
?
1. 开放地址法
?
Hi=(H(key)+d)MODm ? i=1,2,...k(k<m)
H(key)为哈希函数，m为表长，d为增量序列
?
d的取法：
?
①线性探测再散列 d=1,2,...,m-1
②二次探测再散列 d=12，-12，22，-22，32，-32，±k2,(k ≤ m/2)
③伪随机探测再散列，d=伪随机数序列
?
2. 再哈希法：在产生冲突时，计算另一个哈希函数，直到冲突消除为止
Hi=RHi(key)i=1,2,...k
RHi(key)是不同的哈希函数
优点：不易产生关键字"聚集"
缺点：增加了计算时间
?
3. 链地址法：将关键字为同义词的存储在同一个线性链表中
?
4. 建立一个公共溢出区：将发生冲突的关键字放进溢出表
?
四. HashMap:受初始容量和加载因子的影响
?
默认的为0.75,这利于节省内存，但影响了查找速度
? ? ? 我将HashMap的加载因子改成0.8后，在100000个数据中的其中一组查找速度快了15ms(放入的关键字数
?
据是随机获取的),我用除留余数法和链地址法建的哈希表比加载因子为0.75的HashMap查找快31ms，但如此建
?
表比较耗时间。
?
? ? ? ?当关键字数量超过了加载因子和初始容量的乘积时，要进行rehash，重构hash表：增大hash表的容量（可
?
以增加倍数）和将原hash表中的数据要重新放到新的hash表中。
?
