六.哈希表

1.定义:哈希表是一种根据关键字(key)的值直接进行访问的数据结构。

    关键字的值就是数组的索引下标

用法:(1)可以快速的判断某个元素是否出现在集合里(HashSet)

   (2)通过key可以高效的查到所匹配的value(HashMap)

2.哈希函数:哈希函数可以将关键字转换为数组的索引下标

      index=hash(key)

(1)为了保证映射出来的索引数值都落在哈希表上,我们会再次对数值做一个取模的操作。index=hashCode(key)%array.length。也可以进行位运算

    java中的hashCode是一个对象的唯一标识。jdk中的哈希函数将一个对象的hashCode通过位运算转化为数组索引下标(把hashCode再做转化得到数组下标)

    hashCode函数可以将关键字转换为hashCode,然后索引就是:index=hashCode(key) >> 4

(2)不同的key通过哈希函数获得的下标可能是相同的

3.哈希碰撞:不同的key被转换成了同一个index。(不同的对象被转换成了相同的hashCode,放在了同一个位置)

(1)哈希碰撞的解决方法:开放地址法,拉链法。  开放地址法:线性探测法,二次探测法,再哈希法

(2)java中的ThreadLocal所使用的就是开放地址法

 

4.扩容

(1)当哈希表达到一定饱和度,冲突的概率会变高,此时就需要扩容

(2)jdk中的HashMap,影响其扩容的因素有两个:

  Capacity:容量

  LoadFactor:负载因子,默认:0.75

  衡量HashMap是否需要扩容的条件是:HashMap.Size>=Capacity*LoadFactor

(3)哈希表的扩容不是简单的把长度变大。二是经过了扩容和重新hash两个步骤:

    扩容:创建一个新的Entry数组,长度为原来的2倍

    重新hash:遍历原来的Entry数组,把所有的Entry重新hash到新数组中

  为什么要重新hash?因为长度扩大后,hash的规则也随之改变(哈希函数可能和容量有关)

可以结合HashMap的源码看一下

 

上一篇:四.源码解读


下一篇:java String 的hashCode