图文并茂,深入浅出HashMap经典详解
什么是HashMap?
HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。
HashMap的数据结构
在Java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。
文字形容永远要配上图才能更好的讲解数据结构,HashMap的结构图

从上图中可以看出,HashMap底层就是一个数组结构,数组中的每一项又是一个链表或者者红黑树。当新建一个HashMap的时候,就会初始化一个数组。
下面先通过大概看下HashMap的核心成员。

HashMap的初始化

通过源码可以看出初始化时并没有初始化数组table,那只能在put操作时放入了,为什么要这样做?预计是避免初始化了HashMap之后不使用反而占用内存吧,哈哈哈。
HashMap的存储操作

下面我们详细讲一下HashMap是如何确定数组索引的位置、进行put操作的详细过程以及扩容机制(resize)
hash计算,确定数组索引位置
不论添加、删除、查找键值对,定位到哈希桶数组的位置都是很关键的第一步。前面说过HashMap的数据结构是数组和链表的结合,所以我们当然希望这个HashMap里面的元素位置尽量分布均匀些,尽量使得每个位置上的元素数量只有一个,那么当我们用hash算法求得这个位置的时候,马上即可以知道对应位置的元素就是我们要的,不用遍历链表,大大优化了查询的效率。HashMap定位数组索引位置,直接决定了hash方法的离散性能。
看下源码的实现:

通过hashCode()的高16位异或者低16位实现的:(h = k.hashCode()) ^ (h >>> 16),主要是从速度、功效、质量来考虑的,这么做可以在数组table的length比较小的时候,也能保证考虑到高低Bit都参加到Hash的计算中,同时不会有太大的开销。
大家都知道上面代码里的key.hashCode()函数调用的是key键值类型自带的哈希函数,返回int型散列值。理论上散列值是一个int型,假如直接拿散列值作为下标访问HashMap主数组的话,考虑到2进制32位带符号的int表值范围从‑2147483648到2147483648。前后加起来大概40亿的映射空间。只需哈希函数映射得比较均匀松散,一般应用是很难出现碰撞的。但问题是一个40亿长度的数组,内存是放不下的。你想,HashMap扩容之前的数组初始大小才16。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算,得到的余数才能用来访问数组下标。源码中模运算是在这个indexFor( )函数里完成。

顺便说一下,这也正好解释了为什么HashMap的数组长度要取2的整次幂。由于这样(数组长度‑1)正好相当于一个“低位掩码”。“与”操作的结果就是散列值的高位一律归零,只保留低位值,用来做数组下标访问。以初始长度16为例,16‑1=15。2进制表示是00000000 0000000000001111。和某散列值做“与”操作如下,结果就是截取了最低的四位值。

但这时候问题就来了,这样就算我的散列值分布再松散,要是只取最后几位的话,碰撞也会很严重。更要命的是假如散列本身做得不好,分布上成等差数列的漏洞,刚好使最后几个低位呈现规律性重复,就无比蛋疼。这时候“扰动函数”的价值就出来了,说到这大家应该都明白了,看下图。

右位移16位,正好是32bit的一半,自己的高半区和低半区做异或者,就是为了混合原始哈希码的高位和低位,以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征,这样高位的信息也被变相保留下来。
putVal方法
HashMap的put方法执行过程可以通过下图来了解,自己有兴趣可以去比照源码更清楚地研究学习。

源码以及解释如下:

扩容机制
HashMap的扩容机制用的很巧妙,以最小的性能来完成扩容。扩容后的容量就变成了变成了之前容量的2倍,初始容量为16,所以经过rehash之后,元素的位置要么是在原位置,要么是在原位置再向高下标移动上次容量次数的位置,也就是说假如上次容量是16,下次扩容后容量变成了16+16,假如一个元素在下标为7的位置,下次扩容时,要不还在7的位置,要不在7+16的位置。
我们下面来解释一下Java8的扩容机制是怎样做到的?n为table的长度,图(a)表示扩容前的key1和key2两种key确定索引位置的示例,图(b)表示扩容后key1和key2两种key确定索引位置的示例,其中hash1是key1对应的哈希与高位运算结果。

元素在重新计算hash之后,由于n变为2倍,那么n-1的mask范围在高位多1bit(红色),因而新的index就会发生这样的变化:

因而,我们在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,只要要看看原来的hash值新添加的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCap”,可以看看下图为16扩充为32的resize示用意:

而hash值的高位能否为1,只要要和扩容后的长度做与操作即可以了,由于扩容后的长度为2的次幂,所以高位必为1,低位必为0,如10000这种形式,源码中有e.hash & oldCap来做到这个逻辑。
这个设计的确非常的巧妙,既省去了重新计算hash值的时间,而且同时,因为新添加的1bit是0还是1可以认为是随机的,因而resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新添加的优化点。有一点注意区别,JDK1.7中rehash的时候,旧链表迁移新链表的时候,假如在新表的数组索引位置相同,则链表元素会倒置,但是从上图可以看出,JDK1.8不会倒置。下面是JDK1.8的resize源码,写的很赞,如下:

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 图文并茂,深入浅出HashMap经典详解