HashMap HashMap - 锐客网

【HashMap】HashMap存储元素的关系结构图

文章图片
image.png

文章图片
image.png

package collection.map; import java.util.HashMap; import java.util.Map; /** * @author haishen * @date 2019/2/26 */ public class HashMapTest { public static void main(String[] args) { Map hashMap = new HashMap(); hashMap.put(null, "1"); hashMap.put("1", "12"); hashMap.put("3",null); hashMap.get("3"); System.out.println(hashMap.size()); } }

文章图片
image.png

设置默认的扩容因子，DEFAULT_LOAD_FACTOR = 0.75f; 四分之三

put操作

文章图片
image.png

计算元素key 的hash值；
调用putVal方法。
- key和value是可以为null的。

计算key的hash值

文章图片
image.png

key.hashCode()函数调用的是key键值类型自带的哈希函数，返回int型散列值(4个字节，32位);
用这个散列值与这个散列值无符号右移16位的的值进行异或运算（相同为0，相反为1）。
可以看出key是可以为null的。

文章图片
image.png

“扰动函数”，右位移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。参考

putVal执行逻辑 image.png

如果表为空，或者表的长度为零，则先进行扩容逻辑；
根据key 的hash 值和数组容量大小-1的与操作的结果索引结果，如果该索引位置没有元素，则将新元素添加进去；
如果有元素，则说明出现了hash冲突，需要解决冲突，解决冲突的方式，
- 如果存在的节点和新添加的节点的hash值和key相同，确定值老节点，后续更新value即可
- 如果节点是树节点，走树节点解决冲突的逻辑；
- 以链表的形式添加节点，如果链表的节点长度超过8，链表转换从红黑树的数据结构。
- 如果链式节点索引到的节点和新添加的节点的hash值和key相同，确定是老的节点，后续更新value即可；
- 最后是已存在的节点则更新对应的value值。
判断当前map中记录的元素是否大于设置的阀值，如果大于，还需要进行扩容逻辑。

扩容逻辑
image.png

根据老数组的容量大小判断需要扩容的大小，如果没有设置初始值，则扩容大小为16，如果有初始值，在扩容大小为原容量的2倍；
创建一个新容量大小的数据；
循环遍历老数组，将老素组中的元素放到新的数组中去；
如果指定位置获取的元素没有后继节点，则将该老元素的赋值到该老元素的hash值与新数组大小减一进行与操作后的位置；
如果是树节点，则走树节点重新分配逻辑；
以上几种情况都不符合的话，说明该元素是有后继节点的，需要对后继节点进行重新hash；这个工程中定义了4个关键的Node对象，loHead（低位头节点）、loTail（低位尾节点）、hiHead（高位头节点）、hiTail（高位尾节点）；
整个doWhile循环体中做的事情就是判断拿到的节点的hsah值与老的数组容量的与操作结果是否为0，如果为零，则判断该元素还是在扩容前的位置，如果与操作结果不为0，则判断该元素的位置应该在扩容后的新增空间中，具体位置为该元素在（老数组容器中位置+老数组容量）的所指定的值；低位和高位的链式关系通过上面提到的4个关键的Node对象来指定；
最后节点的后继节点遍历完成之后，跳出循环体，将最终的低位头节点设置到扩容前的位置，将最终的高位头节点设置到扩容后的位置。

解决疑问

为什么判断拿到的节点的hsah值与老的数组容量的与操作结果是否为0，就可以区分元素是在扩容前还是在扩容后的位置？
为什么扩容后的位置为老数组容器中位置+老数组容量的值？

解答

首先明确，HashMap的容器大小为2的n次方；元素在数组中的位置是根据元素的hash值和和数组容量减一（对应的二进制值为全1）进行与操作后得到的值来确定的；元素的hash值的计算方式上文有提到，结论是这个值比较到大，大到会远远超出数组的大小，为了能够映射到数组内，所以进行了元素的hash值和数组容量减一的与操作，这个与操作的结果是映射到了数组容量范围内的值；
所以如果元素的hash值小于老数组容量，即hash值不需要截取就对应数组的某一个位置，那么这个元素的hash值与老数组容量（高位为1，低位全为0）进行与操作肯定为零；当数组容量是原来的2倍时，按位与操作更是零，低位还是原来的值，高位是零，所以还在老数组的位置；
所以如果元素的hash值不小于老数组容量，那么这个元素的hash值与老数组容量（高位为1，低位全为0）进行与操作时，按位与操作时低位还是原来的值，元素按位对应老数组容量最高位与操作结果为零时，高位为零，所以还在老数组的位置；元素对应老数组容量最高位不为零时，说明这个元素在数组容量最高位位置值的二进制值就是为1，在元素与新数组容量-1进行按位与操作获取索引位置时最高位为1，所以新所以的位置为（老数组容器中位置+老数组容量）。
总结就是新容量是老容量的2倍，其容量减一（全1）相比时新容量高位多了个1，当元素的hash与容量减一进行按位与操作时，如果对应新容量减一的高位为1，那么与操作之后的位置就比老容量的位置多了个老容量的大小。

get 操作

文章图片
image.png

执行getNode方法，判断是否有返回值，最后返回查询结果。

文章图片
image.png

根据key的hash值和容器长度-1 进行与操作索引数组元素；
如果索引的结果的hash值和key满足判断，这查找到节点，返回；
否则，判断如果索引的节点有后继节点，
判断如果过是树节点，走树节点查找逻辑；
如果不是树节点，走链式遍历逻辑，遇到hash值以及key和参数相同的节点则返回。

replace操作

文章图片
image.png

通过getNode方法查找对应的节点，然后对value重新赋值。

remove操作

文章图片
image.png

文章图片
image.png 遍历操作

Set keys = hashMap.keySet(); Iterator ite = keys.iterator(); while (ite.hasNext()) { String key = (String) ite.next(); System.out.println("key:{" + key + "}--->value:{" + hashMap.get(key) + "}"); }

文章图片
image.png

iterator()对应的方法是KeyIterator；

文章图片
image.png

KeyIterator继承父类HashIterator

文章图片
image.png

HashIterato初始化时会通过doWhile操作，寻找第一个不为null的元素节点；
执行nextNode方法时，判断当前节点是否有后继节点，如果没有从当前节点的索引+1的位置开始返回第一个不为null的节点；
否则就是有后继节点，直接返回后继节点，有先循环遍历链表节点，遍历完成之后；
所以hashmap的元素遍历顺序如下图，元素的输出顺序和添加顺序是不一致的。

文章图片
image.png

参考:
注意：JDK1.8后，除了对hashmap增加红黑树节点外，对原有造成死锁的关键原因点（新table复制在头端添加元素）改进为依次在末端添加新的元素。虽然JDK1.8后添加红黑树改进了链表过长查询遍历慢问题和resize时出现导致put死循环的bug，但还是非线性安全的，比如数据丢失等等。因此多线程情况下还是建议使用concurrenthashmap。