hashmap遍历并删除元素,元素迁移的一般规律

HashMap基础源代码分析1.hashmap基础2 .何时开始扩展3 .迁移扩展机制java1.7扩展机制元素迁移java1.8扩展机制元素

一. HashMap基础

HashMap继承了AbstractMap抽象类，实现了Map、Cloneable、Serializable接口。HashMap的源码属性：

公共类hashmapk，V extends AbstractMapK，V implements MapK，v，Cloneable，Serializable {//初始容量为16staticfinalintdefault ////负载因子默认值staticfinalfloatdefault _ load _ factor=0.75 f； //桶链表长度大于等于8时，链表被转换为红黑树staticfinalinttreeify _ threshold=8； //桶红黑树大小小于等于6时，红黑树转换为链表staticfinalintuntreeify _ threshold=6； 如果//数组的容量大于64，链表将转换为红黑色树staticfinalintmin _ tree ify _ capacity=64。 初始容量：默认值为16，在第一次put时生成加载因子。 默认值为0.75的阈值。 阈值=容量*加载因子。 默认值12在要素数超过阈值时诱发最大容量的扩大。 如果超过230、230，则容量不扩大，阈值为231 -1java1.8，如果段的链表长度为8以上，则链表被变换为红黑树java1.8，如果段的红黑树的大小为6以下，则红黑树为树仅当阵列容量大于或等于660时，每次扩大容量时，以前的容量为http://www.Sina.com/http://www.Sina.com /

混列映射的容量必须是2的n次方，如果进行容量扩展，则容量将大于或等于指定容量的2次方。 也就是说，是容量初始化过程。

例如，在：进行参加初始化情况下：

newhashmap(5)初次put时，容量23=8，排列长度阈值6，容量16new HashMap(7) 7。初次put时，容量23=8，排列长度阈值6，容量16new HashMap(7) 13 当HashMap决定扩展时，扩展机制将调用HashMap类的resize )方法进行扩展。

java1.7中扩展机制HashMap的基本结构是java1.7之前的数组单链表。

resize ) )源代码：

voidresize(intnewcapacity ) { Entry[] oldTable=table； int oldCapacity=oldTable.length； if (old capacity==maximum _ capacity (/当原始表的长度达到上限且不再扩展时。 threshold=Integer.MAX_VALUE； 返回； } entry [ ] new table=newentry [ new capacity ]； 传输(new table，inithashseedasneeded ) newcapacity )； 表=新表； threshold=(int ) math.min ) newcapacity*loadfactor，MAXIMUM_CAPACITY 1)； }从源代码中可以看到，如果原始table的容量尚未达到最大值，则会创建新数组，并调用transfer )方法进行元素迁移(如下所示)。

第一次put时容量扩展初始化：如果容量等于或大于指定容量的2的幂(默认值为16 )不是第一次put，则扩展)新容量=旧容量) 2，新阈值=新容量)负载因素迁移transfer )源

void传输(entry [ ] new table，boolean rehash ) ) { int new capacity=new table.length； for(entryk，V e : table ) while(null！=e ) { EntryK，V 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<K,V>[] resize() { Node<K,V>[] 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 << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> 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()方法，将红黑树切分为两个链表，之后进行扩容操作