Hashmap的扩容机制及扩容后元素迁移 |
您所在的位置：网站首页 › hashmap转数组 › Hashmap的扩容机制及扩容后元素迁移 |
|
HashMap底层源码分析
一.HashMap基础二.何时触发扩容三.扩容机制java1.7下扩容机制元素迁移
java1.8+扩容机制元素迁移
一.HashMap基础
HashMap继承了AbstractMap抽象类，实现了Map，Cloneable，Serializable接口。 HashMap的源码属性： public class HashMap extends AbstractMap implements Map, Cloneable, Serializable { //初始容量为16 static final int DEFAULT_INITIAL_CAPACITY = 1 初次put时，容量扩为25 =32，数组长度达到阈值24，扩容为64 三.扩容机制当HashMap决定扩容时，会调用HashMap类中的resize()方法进行扩容。 java1.7下扩容机制HashMap的底层结构在java1.7版本之前是：数组+单链表。 resize()源码： void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) {//当原有table长度已经达到了上限，不再扩容。 threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }源码可见，当原table容量没有到达最大，则会新建一个新的数组，并调用transfer()方法进行元素迁移（见下）。 第一次put时，容量扩容初始化：其容量变为不小于指定容量的2的幂数(默认为16)不是第一次put时，扩容：新容量=旧容量 * 2 ，新阈值=新容量 * 加载因子 元素迁移transfer()源码： void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry e : table) { while(null != e) { Entry next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } }在准备好新的数组后，map会遍历数组的每个“桶”，然后遍历桶中的每个Entity，重新计算其hash值（也有可能不计算），找到新数组中的对应位置，以头插法插入新的链表。 注意： 因为是头插法，因此新旧链表的元素位置会发生转置现象。元素迁移的过程中在多线程情境下有可能会触发死循环（无限进行链表反转），因此HashMap线程不安全。 java1.8+扩容机制HashMap的底层结构在java1.8版本之后是：数组+单链表/红黑树。 resize()源码： final Node[] resize() { Node[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap float ft = (float)newCap * loadFactor; newThr = (newCap for (int j = 0; j oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode)e).split(this, newTab, j, oldCap); else { // preserve order Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }java1.8与java1.7扩容时容量的计算方法都为扩大为原来容量的二倍。 注意： 因为1.8版本之后HashMap的底层结构为：数组+单链表/红黑树。因此如果某个桶中的链表长度大于等于8了，则会判断当前的hashmap的容量是否大于64，如果小于64，则会进行扩容；如果大于64，则将链表转为红黑树。 元素迁移java1.8+在扩容时，不需要重新计算元素的hash进行元素迁移。 而是用原先位置key的hash值与旧数组的长度（oldCap）进行"与"操作。 如果结果是0，那么当前元素的桶位置不变。如果结果为1，那么桶的位置就是原位置+原数组 长度值得注意的是：为了防止java1.7之前元素迁移头插法在多线程是会造成死循环，java1.8+后使用尾插法 注意： java1.8 扩容的时候会判断当前的桶的位置有没有链表或者红黑树，如果没有链表或者红黑树，那么当前元素还是和JDK1.7中的求法一样，求新的桶的位置。如果有链表，那么链表的元素会按照上述方法求新的桶的位置。如果是红黑树，则会调用split()方法，将红黑树切分为两个链表，之后进行扩容操作 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |