HashMap 怎么 hash？又如何 map？

百家号Lite小程序热议话题「HashMap 怎么 hash？又如何 map？」
HashMap是Java中Map的一个实现类，它是一个双列结构(数据+链表)，这样的结构使得它的查询和插入效率都很高。HashMap允许null键和值，它的键唯一，元素的存储无序，并且它是线程不安全的。
由于HashMap的这些特性，它在Java中被广泛地使用，下面我们就基于Java8分析一下HashMap的源码。
双列结构：数组+链表
首先HashMap是一个双列结构，它是一个散列表，存储方式是键值对。它继承了AbstractMap，实现了Map<K,V>CloneableSerializable接口。
HashMap的双列结构是数组Node[]+链表，我们知道数组的查询很快，但是修改很慢，因为数组定长，所以添加或者减少元素都会导致数组扩容。而链表结构恰恰相反，它的查询慢，因为没有索引，需要遍历链表查询。但是它的修改很快，不需要扩容，只需要在首或者尾部添加即可。HashMap正是应用了这两种数据结构，以此来保证它的查询和修改都有很高的效率。
HashMap在调用put()方法存储元素的时候，会根据key的hash值来计算它的索引，这个索引有什么用呢？HashMap使用这个索引来将这个键值对储存到对应的数组位置，比如如果计算出来的索引是n，则它将存储在Node[n]这个位置。
HashMap在计算索引的时候尽量保证它的离散，但还是会有不同的key计算出来的索引是一样的，那么第二次put的时候，key就会产生冲突。HashMap用链表的结构解决这个问题，当HashMap发现当前的索引下已经有不为null的Node存在时，会在这个Node后面添加新元素，同一索引下的元素就组成了链表结构，Node和Node之间如何联系可以看下面Node类的源码分析。
先了解一下HashMap里数组的几个参数：
DEFAULT_INITIAL_CAPACITY，默认初始长度，16：
staticfinalintDEFAULT_INITIAL_CAPACITY=1<<4;//aka16MAXIMUM_CAPACITY，最大长度，2^30：
staticfinalintMAXIMUM_CAPACITY=1<<30;DEFAULT_LOAD_FACTOR，默认加载因子，0.75：
staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;finalfloatloadFactor;threshold，阈值，扩容的临界值（capacity*loadfactor）
intthreshold;再看看HashMap构造函数
下边是非常重要的一个内部类Node，它实现了Map.Entry，Node是HashMap中的基本元素，每个键值对都储存在一个Node对象里，Node类有四个成员变量：hashkey的哈希值、键值对key与value，以及next指针。next也是Node类型，这个Node指向的是链表下一个键值对，这也就是前文提到的hash冲突时HashMap的处理办法。
Node类内部实现了Map.Entry接口中的getKey()、getValue()等方法，所以在遍历Map的时候我们可以用Map.entrySet()。
HashMapput()流程
put()方法put()主要是将key和value保存到Node数组中，HashMap根据key的hash值来确定它的索引，源码里put方法将调用内部的putVal()方法。
HashMap在put键值对的时候会调用hash()方法计算key的hash值，hash()方法会调用Object的native方法hashCode()并且将计算之后的hash值高低位做异或运算，以增加hash的复杂度。（Java里一个int类型占4个字节，一个字节是8bit，所以下面源码中的h与h右移16位就相当于高低位异或）
putVal()方法这部分是主要put的逻辑
计算容量：根据map的size计算数组容量大小，如果元素数量也就是size大于数组容量×0.75，则对数组进行扩容，扩容到原来的2倍。查找数据索引：根据key的hash值和数组长度找到Node数组索引。储存：这里有以下几种情况（假设计算出的hash为i，数组为tab，变量以代码为例）当前索引为null，直接new一个Node并存到数组里，tab[i]=newNode(hash,key,value,null)数组不为空，这时两个元素的hash是一样的，再调用equals方法判断key是否一致，相同，则覆盖当前的value，否则继续向下判断上面两个条件都不满足，说明hash发生冲突，Java8里实现了红黑树，红黑树在进行插入和删除操作时通过特定算法保持二叉查找树的平衡，从而可以获得较高的查找性能。本篇也是基于Java8的源码进行分析，在这里HashMap会判断当前数组上的元素tab[i]是否是红黑树，如果是，调用红黑树的putTreeVal的put方法，它会将新元素以红黑树的数据结构储存到数组中。
如果以上条件都不成立，表明tab[i]上有其它key元素存在，并且没有转成红黑树结构，这时只需调用tab[i].next来遍历此链表，找到链表的尾然后将元素存到当前链表的尾部。
HashMap的get()
get()方法会调用getNode()方法，这是get()的核心，getNode()方法的两个参数分别是hash值和key。
这里重点来看getNode()方法，前面讲到过，HashMap是通过key生成的hash值来存储到数组的对应索引上，HashMap在get的时候也是用这种方式来查找元素的。
根据hash值和数组长度找到key对应的数组索引。拿到当前的数组元素，也就是这个链表的第一个元素first，先用hash和equals()判断是不是第一个元素，是的话直接返回，不是的话继续下面的逻辑。不是链表的第一个元素，判断这个元素first是不是红黑树，如果是调用红黑树的getTreeNode方法来查询。如果不是红黑树结构，从first元素开始遍历当前链表，直到找到要查询的元素，如果没有则返回null。数组扩容时再哈希(re-hash)的理解
前面提到，当HashMap在put元素的时候，HashMap会调用resize()方法来重新计算数组容量，数组扩容之后，数组长度发生变化。我们知道HashMap是根据key的hash和数组长度计算元素位置的，那当数组长度发生变化时，如果不重新计算元素的位置，当我们get元素的时候就找不到正确的元素了，所以HashMap在扩容的同时也重新对数组元素进行了计算。
这时还有一个问题，re-hash的时候同一个桶(bucket)上的链表会重新排列还是链表仍然在同一桶上。先考虑一下当它扩容的时候同一个桶上的元素再与新数组长度做与运算&时，可能计算出来的数组索引不同。假如数组长度是16，扩容后的数组长度将是32。
下边用二进制说明这个问题：
最终的结果是00001111，和用oldLen计算的结果一样，其实看上式可以发现真正能改变索引值的是hash第5位(从右向左)上的值，也就是length的最高非零位，所以，同一个链表上的元素在扩容后，它们的索引只有两种可能，一种就是保持原位(最高非零位是0)，另一种就是length+原索引i(第五位是1，结果就相等于25+原索引i，也就是length+i)。
下边所示的HashMap源码中就是用这个思路来re-hash一个桶上的链表，e.hash&oldCap==0判断hash对应length的最高非0位是否是1，是1则把元素存在原索引，否则将元素存在length+原索引的位置。HashMap定义了四个Node对象，lo开头的是低位的链表(原索引)，hi开头的是高位的链表(length+原索引，所以相当于是新length的高位)。
HashMap与HashTable
另外对比一下HashMap与HashTable：
HashMap是线程不安全
的，HashTable线程安全，因为它在get、put方法上加了synchronized关键字。HashMap和HashTable的hash值是不一样的，所在的桶的计算方式也不一样。HashMap的桶是通过&运算符来实现(tab.length-1)&hash，而HashTable是通过取余计算，速度更慢（hash&0x7FFFFFFF)%tab.length（当tab.length=2^n时，因为HashMap的数组长度正好都是2^n，所以两者是等价的）HashTable的synchronized是方法级别的，也就是它是在put()方法上加的，这也就是说任何一个put操作都会使用同一个锁，而实际上不同索引上的元素之间彼此操作不会受到影响；ConcurrentHashMap相当于是HashTable的升级，它也是线程安全的，而且只有在同一个桶上加锁，也就是说只有在多个线程操作同一个数组索引的时候才加锁，极大提高了效率。总结
HashMap底层是数组+链表
结构，数组长度默认是16，当元素的个数大于数组长度×0.75时，数组会扩容。HashMap是散列表
，它根据key的hash值来找到对应的数组索引来储存，发生hash碰撞的时候（计算出来的hash值相等）HashMap将采用拉链式来储存元素，也就是我们所说的单向链表结构。在Java7中，如果hash碰撞，导致拉链过长，查询的性能会下降，所以在Java8中添加红黑树结构
，当一个桶的长度超过8时，将其转为红黑树链表，如果小于6，又重新转换为普通链表。re-hash
再哈希问题：HashMap扩容的时候会重新计算每一个元素的索引，重新计算之后的索引只有两种可能，要么等于原索引要么等于原索引加上原数组长度。由上一条可知，每次扩容，整个hashtable都需要重新计算索引，非常耗时，所以在日常使用中一定要注意这个问题。

该话题由百家号作者BaiduSpring「简介:技术才是第一生产力，一切事物都将信息化！」整理发布。
更多关于话题HashMap 怎么 hash？又如何 map？的细节请微信搜索百家号Lite小程序关注作者「BaiduSpring」进行订阅哦！