HashMap分析
2018-06-18 01:18:49来源：未知 阅读 ()
HashMap分析
这篇文章，分析一下面试中经常会被问到的数据结构——HashMap。
HashMap是啥
大家都知道HashMap是基于key-value机制存储数据的，那么是否有思考过底层是怎样的数据结构从而可以支持这种存储机制呢？
上图，以便看清楚HashMap的数据结构：
我们把这张图分成两部分来看：
1.首先是左边竖着的一个个矩形框（也被称为桶，专业术语叫Bucket），其实这是一个数组(Table)，每一个矩形框对应的就是数组中的一个索引位置，而每个索引位置处存放的就是该索引位置处对应链表的头节点(Entry,亦即Node)；
2.每个Bucket都有自己所对应的单向链表，链表的每个节点其实就是一个 key-value键值对。
我们再看一张图：
这张图和上面那张有什么区别呢？可以看到在图中倒数第2个Bucket中，节点并不是以链表形式存储，而是以红黑树的形式进行了存储！
上面图片是JDK1.7的HashMap存储结构，而下面这张图是JDK1.8的HashMap存储结构。
1.8中最大的变化就是在一个Bucket中，如果存储节点的数量超过了8个，就会将该Bucket中原来以链表形式存储节点转换为以树的形式存储节点;而如果少于6个，就会还原成链表形式存储。
为什么要这样做？前面已经说过LinkedList的遍历操作不太友好，如果在节点个数比较多的情况下性能会比较差，而树的遍历效率是比较好的，主要是优化遍历，提升性能。
接着我们看下源码中和数据结构相关的部分：
1 //初始容量（桶的数量）,默认为16 2 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 3 4 //最大支持容量，2^30 5 static final int MAXIMUM_CAPACITY = 1 << 30; 6 7 //负载因子，默认0.75 8 static final float DEFAULT_LOAD_FACTOR = 0.75f; 9 10 //当一个桶中的entry数量大于8时，就满足了链表转化为树结构存储的其中一个条件 11 static final int TREEIFY_THRESHOLD = 8; 12 13 //当一个桶中的entry数量小于6时，将这个桶中的键值对转化为桶+链表的结构存储 14 static final int UNTREEIFY_THRESHOLD = 6; 15 16 //桶的数量大于64个，链表转化为树结构存储的另一个条件 17 static final int MIN_TREEIFY_CAPACITY = 64; 18 19 //存放桶的数组 20 transient HashMap.Node<K,V>[] table; 21 22 //map中实际存储键值对的数量 23 transient int size; 24 25 //rehash操作的临界值 26 int threshold; 27 28 //标准单向链表的节点构成 29 static class Node<K,V> implements Map.Entry<K,V> { 30 final int hash; //结点哈希值，和Bucket对应的index相同 31 final K key; 32 V value; 33 HashMap.Node<K,V> next; //指向下一个结点 34 35 Node(int hash, K key, V value, HashMap.Node<K,V> next) { 36 this.hash = hash; 37 this.key = key; 38 this.value = value; 39 this.next = next; 40 } 41 42 public final K getKey() { return key; } 43 public final V getValue() { return value; } 44 public final String toString() { return key + "=" + value; } 45 46 //计算节点hashCode的方法 47 public final int hashCode() { 48 //直接调用object类的hashcode()方法 49 //key和value的hashcode按位异或，不同为真 50 //注意：一个数a两次对同一个值b进行异或操作得到的还是它本身 51 return Objects.hashCode(key) ^ Objects.hashCode(value); 52 } 53 54 public final V setValue(V newValue) { 55 V oldValue = value; 56 value = newValue; 57 return oldValue; 58 } 59 60 //判断两个节点对象是否相同 61 public final boolean equals(Object o) { 62 if (o == this) //内存地址相同，直接返回true 63 return true; 64 if (o instanceof Map.Entry) { //key和value都相同才返回true 65 Map.Entry<?,?> e = (Map.Entry<?,?>)o; 66 if (Objects.equals(key, e.getKey()) && 67 Objects.equals(value, e.getValue())) 68 return true; 69 } 70 return false; 71 } 72 }
对其中较重要的属性（常量）解释一下：
1.capacity：指的是桶的数量，代码第二行中可以看到定义了 DEFAULT_INITIAL_CAPACITY = 1 << 4，这个意思是如果在初始化HashMap时没有指定桶的数量，则默认桶的数量为16。
2.loadFactor：负载因子，默认为0.75, 影响hashMap最多可以装多少个节点的条件之一。
3.threshold： 这个变量的值是通过 capacity * loadFactor 计算得出的，它指的是当前map中能够存放节点的最大值，如果超过这个值，就需要做rehash操作。
并且我们可以看到这里节点的定义和LinkedList的节点定义不一样，这里的节点由4部分组成：
1.hash：指的是这个节点应该存放在哪个Bucket中，它的值和对应存放的Bucket的index是相同的。
2.key：节点对应的键。
3.value：节点对应的值。
4.next：指向后一个节点的引用，可以看出这里的链表是单向链表，遍历时就只能从头节点开始往后遍历，这点和LinekdList不同。
HashMap核心源码分析(JDK Version 1.8)
1.构造函数
1 /** 2 * 无参构造方法，只设置了默认的负载因子 3 */ 4 public HashMap() { 5 this.loadFactor = DEFAULT_LOAD_FACTOR; 6 } 7 8 /** 9 * 带初始容量参数的构造方法 10 * @param initialCapacity 自定义table初始容量 11 */ 12 public HashMap(int initialCapacity) { 13 this(initialCapacity, DEFAULT_LOAD_FACTOR); 14 } 15 16 /** 17 *可以自定义初始容量和负载因子的构造方法 18 * 19 * @param initialCapacity 初始容量 20 * @param loadFactor 负载因子 21 * @throws IllegalArgumentException 传入值边界检查异常 22 */ 23 public HashMap(int initialCapacity, float loadFactor) { 24 if (initialCapacity < 0) 25 throw new IllegalArgumentException("Illegal initial capacity: " + 26 initialCapacity); 27 if (initialCapacity > MAXIMUM_CAPACITY) 28 initialCapacity = MAXIMUM_CAPACITY; 29 if (loadFactor <= 0 || Float.isNaN(loadFactor)) 30 throw new IllegalArgumentException("Illegal load factor: " + 31 loadFactor); 32 this.loadFactor = loadFactor; 33 this.threshold = tableSizeFor(initialCapacity); 34 } 35 36 //返回大于所传入的自定义容量的最小2的整数幂(比如传入13，则返回16) 37 static final int tableSizeFor(int cap) { 38 int n = cap - 1; 39 n |= n >>> 1; 40 n |= n >>> 2; 41 n |= n >>> 4; 42 n |= n >>> 8; 43 n |= n >>> 16; 44 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 45 }
一些重载的构造函数，主要保证capacity和loadFactor都有初始值以避免后续rehash出错。
这里主要看下第37行的 tableSizeFor(int cap)这个方法，该方法会保证hashMap的初始桶数量必定为2的整数幂（比如16、32、64、128........）, 为啥要这么做呢？
初始桶数量默认设置16，是为了避免桶数量太少而频繁引发rehash操作造成不必要的性能开销（rehash操作默认会将当前桶的数量扩大一倍）。
而对于计算机来说它底层的计算是基于二进制的（比如16就是 00010000）,此时rehash操作会将桶数量变更为32（对应二进制为 00100000）
可以看到这种情况下每次rehash操作对于计算机来说就是将1向左边移动一位，效率非常高。
但是试想一下若初始化时桶的数量不是2的整数幂，比如22，对应的二进制为 00010110，
此时rehash操作会将桶数量变更为44，对应的二进制为 00101100，改变了四个数字，从效率上来说肯定是不如上面2的整数幂的情况。
2.通过key查找对应节点的方法
1 /** 2 * 对外封装的get方法，实际调用的是getNode()这个方法 3 */ 4 public V get(Object key) { 5 Node<K,V> e; 6 return (e = getNode(hash(key), key)) == null ? null : e.value; 7 } 8 9 /** 10 * 根据key对象获取结点 11 * 12 * @param hash key对象的哈希值 13 * @param key key对象 14 * @return 如果存在该key对应节点，则返回节点；否则返回null 15 */ 16 final HashMap.Node<K,V> getNode(int hash, Object key) { 17 HashMap.Node<K,V>[] tab; //Bucket数组 18 HashMap.Node<K,V> first, e; //first是链表头节点，e为遍历链表时每次循环到的当前节点 19 int n; //Bucket数组大小 20 K k; //遍历链表时每次循环到的当前节点对应的key 21 if ((tab = table) != null && (n = tab.length) > 0 && 22 (first = tab[(n - 1) & hash]) != null) { //如果桶数组已经初始化且初始大小>0，则根据传入key的hash寻找其应该存放的桶里存储链表的头节点，并赋值给first变量 23 if (first.hash == hash && // 头节点存在，总是先检查第一个结点 24 ((k = first.key) == key || (key != null && key.equals(k)))) 25 return first; //如果头节点和所需查找节点的hash值相同并且key也相同，则直接返回头节点（要找的结点就是第一个结点,一次命中） 26 if ((e = first.next) != null) { //如果该桶中第一个结点还有后续结点,则继续遍历查找，否则返回null 27 if (first instanceof TreeNode) //如果该桶中节点已经是红黑树形式存储，则直接调用树结点的get方法 28 return ((TreeNode<K,V>)first).getTreeNode(hash, key); 29 do { //如果还是链表方式存储，则遍历链表，若有找到hash相同并且key也相同的结点，那么就是需要找的结点，返回该结点;没找到则返回null 30 if (e.hash == hash && 31 ((k = e.key) == key || (key != null && key.equals(k)))) //key有可能是基本数据类型，也有可能是对象 32 return e; 33 } while ((e = e.next) != null); 34 } 35 } 36 return null; 37 }
查找节点的过程就不再多说了，注释已经写的很详细了，只需要注意一下JDK1.8新增了对树存储结构的相关操作（第27、28行）。
但是这里需要注意一点，看下第22行代码，在计算当前查找的节点应该存放在哪个bucket时调用了这行代码 (n - 1) & hash，而这里的hash是通过如下方法计算得到的：
1 //每个Node计算hash的方法，返回的是最终放的桶的index 2 static final int hash(Object key) { //注意key为null时，默认是放在0桶位的 3 int h; 4 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 5 }
可以看到这里计算key对应的hash值时，先调用了当前key的hashCode()方法，然后再和该值向右移动16位得到的值进行异或操作，为啥要这么做呢？为什么不直接使用key的hashcode去和 （n-1）做&操作呢？
在n-1很小的情况下，其二进制串只有末几位是有效的，如果直接使用key的hashCode对应的32bit二进制串去和n-1对应的二进制串去做&操作，其实最终只有末几位参与了运算。
这样导致的结果就是会造成大量的碰撞（即大量的节点可能存放于同一个Bucket中，造成分布不均），这样不仅会造成内存空间的浪费，而且遍历的效率很差。
而 (h = key.hashCode()) ^ (h >>> 16) 这行代码的作用就是先将key的hashCode对应的32bit的二进制串，对其高16bit和低16bit进行一次异或操作，然后再和 n-1 对应的二进制串去做&操作。
这么做的好处就是无论你key的hashCode是怎样的，都会先对hashCode的二进制串做一次异或操作，至少保证了高16bit的二进制数字参与了运算，降低了最终的碰撞概率。
当然，上面也提到过，JDK1.8中如果一个Bucket中存放的节点超过8个就会转换为树的存储结构，通过这两种方法的结合降低了碰撞概率，同时保证了碰撞较多时结点的遍历效率。
放一张图片，便于理解（假设此时Bucket数组容量为16）：
还是觉得比较难理解的童鞋，可以参考下方链接中作者写的文章：
http://yikun.github.io/2015/04/01/Java-HashMap工作原理及实现/
3.更新/插入节点的方法
1 /** 2 * 对外封装的put方法，实际调用putVal方法 3 */ 4 public V put(K key, V value) { 5 return putVal(hash(key), key, value, false, true); 6 } 7 8 /** 9 * 根据传入的key和value添加/设置值 10 * 若原先table中已存在该key对象对应的键值对，则将其值更改为新的value 11 * 若原先table中不存在该key对象对应键值对，则计算其所需放入的bucket位置，将其放入 12 * 13 * @param hash key的hash值 14 * @param key key对象 15 * @param value 新的value 16 * @param onlyIfAbsent 如果为true，则不改变已存在键值对的值(默认为false) 17 * @param evict 如果为false，则table处于creation模式 18 * @return 之前有键值对存在，则返回之前该key对应的value；否则返回null 19 */ 20 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 21 boolean evict) { 22 HashMap.Node<K,V>[] tab; //Bucket数组 23 HashMap.Node<K,V> p; //某个Bucket的首结点 24 int n, i; 25 if ((tab = table) == null || (n = tab.length) == 0) //如果bucket数组还没有初始化，先调用resize()方法初始化table 26 n = (tab = resize()).length; //记录下初始化完成后此时table的大小(桶的数量) 27 if ((p = tab[i = (n - 1) & hash]) == null) //根据hash值计算出该键值对应该放的桶位置，若此时该位置还没有结点存在 28 tab[i] = newNode(hash, key, value, null); //直接将该键值对设置为该桶的第一个结点 29 else { //执行到这里，说明发生碰撞，即tab[i]不为空，需要组成单链表或红黑树 30 HashMap.Node<K,V> e; 31 K k; 32 if (p.hash == hash && 33 ((k = p.key) == key || (key != null && key.equals(k)))) 34 e = p; //发现该位置处第一个结点的key就是新传入键值对的key，则将该结点记录下来 35 else if (p instanceof TreeNode) //如果桶中首结点已经是以红黑树结构存储 36 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //调用树的put()方法 37 else { //桶中结点依旧还是链表存储 38 for (int binCount = 0; ; ++binCount) { //遍历链表，binCount记录已遍历结点个数 39 if ((e = p.next) == null) { //如果当前遍历到的结点为空,说明之前遍历过的结点没有和当前传入键值对key相同的结点，需要新增该结点 40 p.next = newNode(hash, key, value, null); //新增结点 41 if (binCount >= TREEIFY_THRESHOLD - 1) //如果新增该结点后，当前桶中的结点个数大于树化的界定值(8) 42 treeifyBin(tab, hash); //转为红黑树结构存储 43 break; 44 } 45 if (e.hash == hash && //如果遍历过程中在桶中找到了和当前传入键值对key相同的结点，则将该结点记录下来 46 ((k = e.key) == key || (key != null && key.equals(k)))) 47 break; 48 p = e; 49 } 50 } 51 if (e != null) { //如果之前在链表或树中找到了和当前传入键值对key相同的结点，则将值进行替换 52 V oldValue = e.value; 53 if (!onlyIfAbsent || oldValue == null) 54 e.value = value; 55 afterNodeAccess(e); //回调LinkedHashMap自己的方法，用于新增LinkedHashMap的双向链表中节点之间的前后关系 56 return oldValue; //返回原先该结点的value 57 } 58 } 59 ++modCount; 60 if (++size > threshold) //总结点数+1，如果插入该结点后map总结点个数大于阙值，则需要扩容和rehash 61 resize(); 62 afterNodeInsertion(evict); 63 return null; 64 }
没啥好讲的，跟着源码走一遍应该就清楚流程了。
4.删除节点的方法
1 /** 2 * 对外封装的删除方法，实际调用removeNode方法 3 */ 4 public V remove(Object key) { 5 Node<K,V> e; 6 return (e = removeNode(hash(key), key, null, false, true)) == null ? 7 null : e.value; 8 } 9 10 /** 11 * 根据传入的key值(必要时可增加value值判断)删除结点 12 * 13 * @param hash key的hash值 14 * @param key key对象 15 * @param value 需要判断value时才传入(默认为null) 16 * @param matchValue 如果为true，则必须key和value同时和传入结点相同才会被删除(默认为false) 17 * @param movable 如果为false，删除时不移动其他结点(默认为true) 18 * @return 被删除结点，或没找到要删除结点则返回null 19 */ 20 final HashMap.Node<K,V> removeNode(int hash, Object key, Object value, 21 boolean matchValue, boolean movable) { 22 HashMap.Node<K,V>[] tab; 23 HashMap.Node<K,V> p; 24 int n, index; 25 if ((tab = table) != null && (n = tab.length) > 0 && 26 (p = tab[index = (n - 1) & hash]) != null) { //如果table已经初始化，大小不为0，且根据key的hash计算桶的位置处已有结点存在 27 HashMap.Node<K,V> node = null, e; 28 K k; 29 V v; 30 if (p.hash == hash && 31 ((k = p.key) == key || (key != null && key.equals(k)))) //如果要删除的结点就是该桶中链表的第一个结点 32 node = p; //将该结点保存下来 33 else if ((e = p.next) != null) { //如果第一个结点不是要删除的结点，则需要先遍历查找到该结点，再删除 34 if (p instanceof TreeNode) //如果该桶中头结点是树结点，说明已是树存储结构 35 node = ((TreeNode<K,V>)p).getTreeNode(hash, key); //需调用树的get()方法查找和当前需删除结点key相同的结点 36 else { //否则依旧还是链表存储，遍历链表 37 do { 38 if (e.hash == hash && 39 ((k = e.key) == key || 40 (key != null && key.equals(k)))) { //如果找到和要删除结点的key相同的结点 41 node = e; //保存下来 42 break; 43 } 44 p = e; 45 } while ((e = e.next) != null); 46 } 47 } 48 if (node != null && (!matchValue || (v = node.value) == value || 49 (value != null && value.equals(v)))) { //如果之前在桶中找到了和当前传入键值对key相同的结点 50 if (node instanceof TreeNode) //之前找到的结点是树结点 51 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); //调用树的remove()方法 52 else if (node == p) //之前找到的结点是桶中链表的头结点 53 tab[index] = node.next; //将桶的头结点删除，并将下一个结点设置为头结点 54 else //之前找到的结点是链表中其中一个结点(非头节点) 55 p.next = node.next; //删除该结点，并将前一个结点后驱指向被删除结点的下一个结点 56 ++modCount; 57 --size; //map总结点个数减1 58 afterNodeRemoval(node); //回调LinkedHashMap的方法，用于删除LinkedHashMap双向链表中节点之间的前后关系 59 return node; //返回被删除的结点 60 } 61 } 62 return null; 63 }
同样，跟着源码走一遍就清楚流程了，主要分为查找节点和删除节点两步，每步又分为头节点、非头节点（树/链表）几种情况的实现。
5.HashMap核心方法——扩容及rehash方法
1 /** 2 * 核心方法：扩容以及rehash操作. 3 * 初值为空时，则根据初始容量开辟空间来创建数组. 4 * 否则， 因为我们使用2的幂定义数组大小，数据要么待在原来的下标， 要么移动到新数组的高位下标 5 * 比如初始容量为16，原来有两个数据在index为1的桶中；resize后容量为32，原来那两个数据既可以在index为1的桶，也可以在index为17的桶中 6 * 7 * @return 扩容后的新数组 8 */ 9 final HashMap.Node<K,V>[] resize() { 10 HashMap.Node<K,V>[] oldTab = table; //记录原数组 11 int oldCap = (oldTab == null) ? 0 : oldTab.length; //记录原数组Capacity 12 int oldThr = threshold; //记录原数组的rehash阙值 13 int newCap, newThr = 0; //新数组capacity,rehash阙值 14 if (oldCap > 0) { //如果原数组capacity>0 15 if (oldCap >= MAXIMUM_CAPACITY) { //原数组capacity已经达到容量最大值,无法再扩容 16 threshold = Integer.MAX_VALUE; //阙值设置为最大值 17 return oldTab; //直接返回原数组 18 } 19 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 20 oldCap >= DEFAULT_INITIAL_CAPACITY) //新数组capacity为原数组两倍 21 newThr = oldThr << 1; //如果此时数组大小在16至最大值之间,新阙值也变为原先的两倍 22 } 23 else if (oldThr > 0) // 如果原阙值>0,说明调用HashMap构造方法(带阙值参数的那个)时只设置了阙值大小但没有设置capacity 24 newCap = oldThr; //将阙值大小直接赋值给新数组的capacity 25 else { //如果直接调用HashMap无参构造方法，则初始capacity和阙值都没有被设置，此处给它设置上 26 newCap = DEFAULT_INITIAL_CAPACITY; //初始capacity默认为16 27 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //阙值默认为16*0.75=12 28 } 29 if (newThr == 0) { //如果新阙值为0，重新设置阙值，防止意外情况 30 float ft = (float)newCap * loadFactor; //用新capacity * 当前负载因子得到计算结果 31 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 32 (int)ft : Integer.MAX_VALUE);//若新容量和该计算结果都未达到最大值，则新阙值就是该计算结果；否则新阙值为int最大值 33 } 34 threshold = newThr; 35 36 HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap]; 37 table = newTab; //用新容量初始化新数组 38 if (oldTab != null) { //若旧数组已经被初始化,需要对原先存放的结点进行rehash操作 39 for (int j = 0; j < oldCap; ++j) { //遍历旧数组每个桶，对桶中每一个结点判断应放入高位还是低位，并放入新数组对应的桶中 40 HashMap.Node<K,V> e; 41 if ((e = oldTab[j]) != null) { //如果当前遍历到的桶中第一个结点不为空，才继续往下走，否则直接进行下一个桶的遍历 42 oldTab[j] = null; //将该桶的首结点置空 43 if (e.next == null) //如果该结点没有后续结点，即该桶中只有这一个结点 44 newTab[e.hash & (newCap - 1)] = e; //将该结点重新计算index后，放入新数组的桶中 45 else if (e instanceof TreeNode) //如果该结点有后续结点，且该结点已经是树存储 46 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //则直接调用树的split方法 47 else { //如果该结点有后续结点，且该桶中结点存储方式还是链表存储 48 HashMap.Node<K,V> loHead = null, loTail = null; 49 HashMap.Node<K,V> hiHead = null, hiTail = null; 50 HashMap.Node<K,V> next; 51 do { 52 next = e.next; 53 //e.hash & oldCap 将该链表的所有结点均匀分散为新数组低位和高位两个位置 54 if ((e.hash & oldCap) == 0) { // 如果被分到低位，则在新数组中的桶位置和原先的桶是一样的 55 if (loTail == null) //如果新数组中低位桶尾结点为空，说明该桶当前还没有结点 56 loHead = e; //则将当前链表中遍历到的结点保存至loHead变量中，待遍历完一整条链表后，新数组低位桶设置头节点使用 57 else //如果新数组中低位桶尾结点不为空 58 loTail.next = e; //则将当前链表中遍历到的结点添加到新数组中该低位桶的链表尾部 59 loTail = e; //新数组中该低位桶的链表尾结点设置为该结点 60 } 61 else { //如果被分到高位，则在新数组中的桶位置为原先所在桶位置+原先桶的capacity 62 if (hiTail == null) //如果新数组中高位桶尾结点为空，说明该桶当前还没有结点 63 hiHead = e; //则将当前链表中遍历到的结点保存至hiHead变量中，待遍历完一整条链表后，新数组高位桶设置头节点使用 64 else //如果新数组中高位桶尾结点不为空 65 hiTail.next = e; //则将当前链表中遍历到的结点添加到新数组中该高位桶的链表尾部 66 hiTail = e; //新数组中该高位桶的链表尾结点设置为该结点 67 } 68 } while ((e = next) != null); 69 if (loTail != null) { //如果新数组低位桶的尾结点非空 70 loTail.next = null; //则将其下一个结点设置为null，方便后续结点插入 71 newTab[j] = loHead; //并将新数组中低位桶头结点设置为loHead中保存的结点 72 } 73 if (hiTail != null) { //如果新数组高位桶的尾结点非空 74 hiTail.next = null; //则将其下一个结点设置为null，方便后续结点插入 75 newTab[j + oldCap] = hiHead; //并将新数组中高位桶头结点设置为hiHead中保存的结点 76 } 77 } 78 } 79 } 80 } 81 return newTab; 82 }
这个方法是HashMap核心的方法了，以35行为分界线分成上下两部分看。
35行之前的代码主要就是将Bucket数组容量扩大一倍，并设置新的阙值，没啥好讲的。
重点是35行之后的代码，这部分代码是在依次遍历原Bucket数组的每一条链表，并根据一定的规则重新计算链表中每个节点新的hash值，以便定位应该放在新Bucket数组中的哪个位置。
在JDK1.8之前，每条链表的每个节点都会重新再计算一遍hash值，以确认在新Bucket数组中存放位置；
而在JDK1.8及之后，不再重新对每个结点计算新hash值，如54行代码所示，直接用该节点原先的hash值的二进制串与原Bucket数组容量的二进制串进行&操作以确认节点rehash后应该放在新数组的位置，为啥要这么做？
首先要明确两点：
1.HashMap的Bucket数组默认初始容量为16，并且每次扩容后的大小都为2的幂,并且对于计算机来说每次扩容其实就是将二进制串中的1往左移动一位。
2.&操作的特性是 两个二进制串相同bit位 都是1结果才为1，其他情况结果均为0。
明确以上两点后，再解释一下这么做的原因：
每次扩容，1会在二进制串中向左移动一位，而对于原先节点来说每个节点的二进制串在该bit位是0或1的可能性是随机的
那么此时只需要对两个二进制串中该bit位做&操作即可，而&操作的结果可能有两个：0或1
所以代码中定义了当&操作结果为0时，表示当前节点在新Bucket数组中的位置和原Bucket数组相同(也就是注释中说的低位桶)；
而&操作结果为1时，表示当前节点在新Bucket数组中的位置是 原bucket数组索引 + 原Bucket容量处(也就是注释中说的高位桶)。
因为每个结点对应的二进制串每个bit位为0或1的可能性是随机的，所以最后被分配到新数组是在低位还是高位也可以认为是随机的。
这种做法巧妙的利用了HashMap自身以及&操作的特性，避免了JDK1.8以前每次rehash时每个节点都要重新计算hash值造成的大量性能消耗。
同样放几张图，以便大家结合着理解：
还是理解不了的童鞋，请打开上方引用的链接，作者在他的文章中也做了详细的解释 :)
注: 图片均来自于链接中作者的文章，非本人原创!
HashMap存在的较隐蔽的一个问题
HashMap在做rehash操作的时候会发生死循环从而造成CPU100%，这个问题只会在多线程环境下使用HashMap进行操作时才可能会出现。
而导致这个问题的主要原因是多线程环境下如果不使用锁，将无法保证线程的执行顺序，那么就可能出现一个线程执行期间被另一个线程抢占到执行资源从而让出执行权。
然后就可能出现这样的情况 线程A中将节点之间的引用变为 E1 -> E2, 而线程B中将节点之间的引用变为 E2 -> E1, 此时其实就形成了一个闭环，两个节点相互引用。
如果此时再执行了 get/put 操作，因为都需要先遍历链表，如果遍历到E1,E2这两个节点，那么就会无限循环，最终导致的结果就是死循环。
若想深入了解该问题，可参考下方链接中的文章：
https://www.cnblogs.com/dongguacai/p/5599100.html
当然这个问题的解决方案也很简单，在多线程场景下请使用 ConCurrentHashMap 进行操作（这个类会在后续多线程相关的文章中进行分析）。
好了，到这里HashMap的分析就差不多了，碍于篇幅原因这里并没有介绍转换为树存储后的一系列相关方法，感兴趣的童鞋可以自己跟一下源码 : )
下篇文章会分析LinkedHashMap的相关源码。
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
上一篇：Netty入门（三）构成部分
下一篇：java基础（22）、反射
- HashMap：源代码（构造方法、put、resize、get、remove、rep 2020-06-04
- 数据结构:用实例分析ArrayList与LinkedList的读写性能 2020-06-04
- HashMap1.7和1.8，红黑树原理！ 2020-06-03
- 数据分析 | 数据可视化图表，BI工具构建逻辑 2020-06-02
- JDK1.7和1.8的HashMap对比详解 2020-06-02
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
