透过面试题掌握HashMap【持续升级中】

最近做了一个面试题解答的开源项目，大家可以看一看，假如对大家有帮助，希望大家帮忙给一个star，谢谢各位大佬了！

《面试指北》项目地址： NotFound9/interviewGuide

image.png

下面是主要是自己看了《疯狂Java讲义》和少量Java容器类相关的博客，以及很多面经中涉及到的Java容器相关的面试题后，自己一律手写的解答，也花了少量流程图，之后会继续升级这一部分。

HashMap相关的面试题

1.HashMap增加一个键值对的过程是怎样样的？

2.ConcurrentHashMap增加一个键值对的过程是怎样样的？

3.HashMap与HashTable，ConcurrentHashMap的区别是什么？

4.HashMap扩容后能否需要rehash？

5.HashMap扩容是怎么扩容的，为什么都是2的N次幂的大小？

6.ConcurrentHashMap是怎样记录元素个数size的？

7.为什么ConcurrentHashMap，HashTable不支持key，value为null?

8.HashSet和HashMap的区别？

9.HashMap遍历时删除元素的有哪些实现方法？

HashMap增加一个键值对的过程是怎样样的？

流程图如下：

image

1.初始化table

判断table能否为空或者为null，否则执行resize()方法（resize方法一般是扩容时调用，也可以调用来初始化table）。

2.计算hash值

根据键值key计算hash值。（由于hashCode是一个int类型的变量，是4字节，32位，所以这里会将hashCode的低16位与高16位进行一个异或者运算，来保留高位的特征，以便于得到的hash值更加均匀分布）

static final int hash(Object key) {    int h;    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

3.插入或者升级节点

根据(n – 1) & hash计算得到插入的数组下标i，而后进行判断

table[i]==null

那么说明当前数组下标下，没有hash冲突的元素，直接新建节点增加。

table[i].hash == hash &&(table[i]== key || (key != null && key.equals(table[i].key)))

判断table[i]的首个元素能否和key一样，假如相同直接升级value。

table[i] instanceof TreeNode

判断table[i] 能否为treeNode，即table[i] 能否是红黑树，假如是红黑树，则直接在树中插入键值对。

其余情况

上面的判断条件都不满足，说明table[i]存储的是一个链表，那么遍历链表，判断能否存在已有元素的key与插入键值对的key相等，假如是，那么升级value，假如没有，那么在链表末尾插入一个新节点。插入之后判断链表长度能否大于8，大于8的话把链表转换为红黑树。

4.扩容

插入成功后，判断实际存在的键值对数量size能否超多了最大容量threshold(一般是数组长度*负载因子0.75)，假如超过，进行扩容。

源代码如下：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                   boolean evict) {    Node<K,V>[] tab; Node<K,V> p; int n, i;    // tab为空则创立     if ((tab = table) == null || (n = tab.length) == 0)        n = (tab = resize()).length;    // 计算index，并对null做解决      // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)    if ((p = tab[i = (n - 1) & hash]) == null)        tab[i] = newNode(hash, key, value, null);    // 桶中已经存在元素    else {        Node<K,V> e; K k;        // 节点key存在，直接覆盖value         // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等        if (p.hash == hash &&            ((k = p.key) == key || (key != null && key.equals(k))))                // 将第一个元素赋值给e，用e来记录                e = p;        // 判断该链为红黑树         // hash值不相等，即key不相等；为红黑树结点        else if (p instanceof TreeNode)            // 放入树中            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);        // 该链为链表         // 为链表结点        else {            // 在链表最末插入结点            for (int binCount = 0; ; ++binCount) {                // 到达链表的尾部                if ((e = p.next) == null) {                    // 在尾部插入新结点                    p.next = newNode(hash, key, value, null);                    // 结点数量达到阈值，转化为红黑树                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                        treeifyBin(tab, hash);                    // 跳出循环                    break;                }                // 判断链表中结点的key值与插入的元素的key值能否相等                if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))                    // 相等，跳出循环                    break;                // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表                p = e;            }        }        // 表示在桶中找到key值、hash值与插入元素相等的结点        if (e != null) {             // 记录e的value            V oldValue = e.value;            // onlyIfAbsent为false或者者旧值为null            if (!onlyIfAbsent || oldValue == null)                //用新值替换旧值                e.value = value;            // 访问后回调            afterNodeAccess(e);            // 返回旧值            return oldValue;        }    }    ++modCount;    // 超过最大容量 就扩容     // 实际大小大于阈值则扩容    if (++size > threshold)        resize();    // 插入后回调    afterNodeInsertion(evict);    return null;}

ConcurrentHashMap增加一个键值对的过程是怎样样的？

这是我自己流程图如下所示：

image

1.判断null值

判断key==null 或者者 value == null，假如是，抛出空指针异常。

2.计算hash

根据key计算hash值(计算结果跟HashMap是一致的，写法不同)。

3.进入for循环，插入或者升级元素

• 3.1 tab==null || tab.length==0，

  说明当前tab还没有初始化。

  那么调用initTable()方法初始化tab。（在initTable方法中，为了控制只有一个线程对table进行初始化，当前线程会通过CAS操作对SIZECTL变量赋值为-1，假如赋值成功，线程才能初始化table，否则会调用Thread.yield()方法让出时间片）。

• 3.2 f ==null

  （Node<K,V> f根据hash值计算得到数组下标，下标存储的元素，f可能是null，链表头节点，红黑树根节点或者迁移标志节点ForwardNode）

  说明当前位置还没有哈希冲突的键值对。

  那么根据key和value创立一个Node，使用CAS操作设置在当前数组下标下，并且break出for循环。

• 3.3 f != null && f.hash = -1

  说明ConcurrentHashMap正在在扩容，当前的节点f是一个标志节点，当前下标存储的hash冲突的元素已经迁移了。

  那么当前线程会调用helpTransfer()方法来辅助扩容，扩容完成后会将tab指向新的table，而后继续执行for循环。

• 3.4 除上面三种以外情况

  说明f节点是一个链表的头结点或者者是红黑树的根节点，那么对f加sychronize同步锁，而后进行以下判断：

  • f.hash > 0

    假如是f的hash值大于0，当前数组下标存储的是一个链表，f是链表的头结点。

    对链表进行遍历，假如有节点跟当前需要插入节点的hash值相同，那么对节点的value进行升级，否则根据key，value创立一个Node<K,V>，增加到链表末尾。

  • f instanceof TreeBin

    假如f是TreeBin类型，那么说明当前数组下标存储的是一个红黑树，f是红黑树的根节点，调用putTreeVal方法，插入或者升级节点。

  插入完成后，判断binCount（数组下标存储是一个链表时，binCount是链表长度），当binCount超过8时，那么调用treeifyBin方法将链表转换为红黑树。最后break出for循环。

4.判断能否需要扩容

调用addCount()对当前数组长度加1，在addCount()方法中，会判断当前元素个数能否超过sizeCtl(扩容阈值，总长度*0.75)，假如是，那么会进行扩容，假如正处于扩容过程中，当前线程会辅助扩容。

HashMap与HashTable，ConcurrentHashMap的区别是什么？

主要从底层数据结构，线程安全，执行效率，能否允许Null值，初始容量及扩容，hash值计算来进行分析。

1.底层数据结构

    transient Node<K,V>[] table; //HashMap        transient volatile Node<K,V>[] table;//ConcurrentHashMap        private transient Entry<?,?>[] table;//HashTable

HashMap=数组+链表+红黑树

HashMap的底层数据结构是一个数组+链表+红黑树，数组的每个元素存储是一个链表的头结点，链表中存储了一组哈希值冲突的键值对，通过链地址法来处理哈希冲突的。为了避免链表长渡过长，影响查找元素的效率，当链表的长度>8时，会将链表转换为红黑树，链表的长度<6时，将红黑树转换为链表。之所以临界点为8是由于红黑树的查找时间复杂度为logN，链表的平均时间查找复杂度为N/2，当N为8时，logN为3，是小于N/2的，正好可以通过转换为红黑树减少查找的时间复杂度。

Hashtable=数组+链表

Hashtable底层数据结构跟HashMap一致，底层数据结构是一个数组+链表，也是通过链地址法来处理冲突，只是链表过长时，不会转换为红黑树来减少查找时的时间复杂度。Hashtable属于历史遗留类，实际开发中很少使用。

ConcurrentHashMap=数组+链表+红黑树

ConcurrentHashMap底层数据结构跟HashMap一致，底层数据结构是一个数组+链表+红黑树。只不过使用了volatile来进行修饰它的属性，来保证内存可见性(一个线程修改了这些属性后，会使得其余线程中对于该属性的缓存失效，以便下次读取时取最新的值)。

2.线程安全

HashMap 非线程安全

HashMap是非线程安全的。（例如多个线程插入多个键值对，假如两个键值对的key哈希冲突，可能会使得两个线程在操作同一个链表中的节点，导致一个键值对的value被覆盖）

HashMap 非线程安全

HashTable是线程安全的，主要通过使用synchronized关键字修饰大部分方法，使得每次只能一个线程对HashTable进行同步修改，性能开销较大。

ConcurrentHashMap 线程安全

ConcurrentHashMap是线程安全的，主要是通过CAS操作+synchronized来保证线程安全的。

CAS操作

往ConcurrentHashMap中插入新的键值对时，假如对应的数组下标元素为null，那么通过CAS操作原子性地将节点设置到数组中。

//这是增加新的键值对的方法final V putVal(K key, V value, boolean onlyIfAbsent) {...其余代码  if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {    if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))              break; // 由于对应的数组下标元素为null，所以null作为预期值，new Node<K,V>(hash, key, value, null)作为即将升级的值，只有当内存中的值与即将预期值一致时，才会进行升级，保证原子性。  }...其余代码}static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,                                        Node<K,V> c, Node<K,V> v) {        return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);}

synchronized锁

往ConcurrentHashMap中插入新的键值对时，假如对应的数组下标元素不为null，那么会对数组下标存储的元素(也就是链表的头节点)加synchronized锁， 而后进行插入操作，

Node<K,V> f = tabAt(tab, i = (n - 1) & hash));synchronized (f) {//f就是数组下标存储的元素    if (tabAt(tab, i) == f) {        if (fh >= 0) {            binCount = 1;            for (Node<K,V> e = f;; ++binCount) {                K ek;                if (e.hash == hash &&                    ((ek = e.key) == key ||                     (ek != null && key.equals(ek)))) {                    oldVal = e.val;                    if (!onlyIfAbsent)                        e.val = value;                    break;                }                Node<K,V> pred = e;                if ((e = e.next) == null) {                    pred.next = new Node<K,V>(hash, key,                                              value, null);                    break;                }            }        }        else if (f instanceof TreeBin) {            Node<K,V> p;            binCount = 2;            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,                                           value)) != null) {                oldVal = p.val;                if (!onlyIfAbsent)                    p.val = value;            }        }    }}

3.执行效率

由于HashMap是非线程安全的，执行效率会高少量，其次是ConcurrentHashMap，由于HashTable在进行修改和访问时是对整个HashTable加synchronized锁，所以效率最低。

4.能否允许null值出现

HashMap的key和null都可以为null，假如key为null，那么计算的hash值会是0，最终计算得到的数组下标也会是0，所以key为null的键值对会存储在数组中的首元素的链表中。value为null的键值对也能正常插入，跟普通键值对插入过程一致。

static final int hash(Object key) {    int h;    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

HashTable的键和值都不能为null，假如将HashTable的一个键值对的key设置为null，由于null值没法调用hashCode()方法获取哈希值，所以会抛出空指针异常。同样value为null时，在put方法中会进行判断，而后抛出空指针异常。

public synchronized V put(K key, V value) {        // Make sure the value is not null        if (value == null) {            throw new NullPointerException();        }        Entry<?,?> tab[] = table;        int hash = key.hashCode();        ...其余代码}

ConcurrentHashMap的键和值都不能为null,在putVal方法中会进行判断，为null会抛出空指针异常。

final V putVal(K key, V value, boolean onlyIfAbsent) {    if (key == null || value == null) throw new NullPointerException();    int hash = spread(key.hashCode());    ...其余代码}

5.初始容量及扩容

不指定初始容量

假如不指定初始容量，HashMap和ConcurrentHashMap默认会是16，HashTable的容量默认会是11。

不指定初始容量

假如制定了初始容量，HashMap和ConcurrentHashMap的容量会是比初始容量略微大少量的2的幂次方大小，HashTable会使用初始容量，

扩容

扩容时，HashMap和ConcurrentHashMap扩容时会是原来长度的两倍，HashTable则是2倍加上1.

6.hash值计算

HashTable会扩容为2n+1，HashTable之所以容量取11，及扩容时是是2n+1，是为了保证 HashTable的长度是一个素数，由于数组的下标是用key的hashCode与数组的长度取模进行计算得到的，而当数组的长度是素数时，可以保证计算得到的数组下标分布得更加均匀，可以看看这篇文章http://zhaox.github.io/algorithm/2015/06/29/hash

public synchronized V put(K key, V value) {         ...其余代码        // Makes sure the key is not already in the hashtable.        Entry<?,?> tab[] = table;        int hash = key.hashCode();        int index = (hash & 0x7FFFFFFF) % tab.length;        ...其余代码}

HashMap和ConcurrentHashMap的hash值都是通过将key的hashCode()高16位与低16位进行异或者运算(这样可以保留高位的特征，避免少量key的hashCode高位不同，低位相同，造成hash冲突)，得到hash值，而后将hash&(n-1)计算得到数组下标。（n为数组的长度，由于当n为2的整数次幂时，hash mod n的结果在数学上等于hash&(n-1)，而且计算机进行&运算更快，所以这也是HashMap的长度总是设置为2的整数次幂的起因）

//HashMap计算hash值的方法static int hash(Object key) {    int h;    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }//ConcurrentHashMap计算hash值的方法 static  int spread(int h) {//h是对象的hashCode    return (h ^ (h >>> 16)) & HASH_BITS;// HASH_BITS = 0x7fffffff;}  

HashMap扩容后能否需要rehash？

在JDK1.8以后，不需要rehash，由于键值对的Hash值主要是根据key的hashCode()的高16位与低16位进行异或者计算后得到，根据hash%length，计算得到数组的下标index，由于length是2的整数次幂，当扩容后length变为原来的两倍时，hash%(2*length)的计算结果结果差别在于第length位的值是1还是0，假如是0，那么在新数组中的index与旧数组的一直，假如是1，在新数组中的index会是旧数组中的数组中的index+length。

HashMap扩容是怎么扩容的，为什么都是2的N次幂的大小？

触发扩容

在没有指定初始长度的情况下，HashMap数组的默认长度为16，在增加一个新的键值对时，会调用putVal()方法，在方法中，成功增加一个新的键值对以后，会判断当前的元素个数能否超过阀值(数组长度*负载因子0.75)，假如超过那么调用resize方法进行扩容。具体的扩容步骤如下：

计算扩容后的长度

• 假如当前table为null

  那么直接初始化一个数组长度为16的数组返回。

• 假如当前table的length已经大于HashMap指定的最大值2的30次方

  那么直接返回旧table，不进行扩容。

• 其余情况

  将table的length扩容为2倍，而后计算新的扩容阀值（新数组长度*0.75）。

初始化新数组

会根据扩容后的数组长度初始化话一个新的数组，并且直接赋值给当前hashMap的成员变量table。

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;

这一步就很有意思，也是HashMap是非线程安全的体现之一，由于此时newTab还是一个空数组，假如有其余线程访问HashMap，根据key去newTab中找键值对，会返回null。实际上可能key是有对应的键值对的，只不过键值对都保存在旧table中，还没有迁移过来。

（与之相反，HashTable在处理扩容时其余线程访问的问题，是通过对大部分方法使用sychronized关键字修饰，也就是某个线程在执行扩容方法时，会对HashTable对象加锁，其余线程无法访问HashTable。ConcurrentHashMap在处理扩容时其余线程访问的问题，是通过设置ForwardingNode标识节点来处理的，扩容时，某个线程对数组中某个下标下所有Hash冲突的元素进行迁移时，那么会将数组下标的数组元素设置为一个标识节点ForwardingNode，之后其余线程在访问时，假如发现key的hash值映射的数组下标对应是一个标识节点ForwardingNode（ForwardingNode继承于普通Node，区别字啊呀这个节点的hash值会设置为-1，并且会多一个指向扩容过程中新tab的指针nextTable），那么会根据ForwardingNode中的nextTable变量，去新的tab中查找元素。（假如是增加新的键值对时发现是ForwardingNode，那么辅助扩容或者阻塞等待，扩容完成后去新数组中升级或者插入元素）

迁移元素

由于HashMap的数组长度总是2的N次幂，扩容后也是变为原来的2倍，所以有一个数学公式，当length为2的N次幂时，

hash%length=hash&(length-1)

而由于length是2的N次幂，length-1在二进制中其实是N-1个1。例如：

length为16，length用2进制表示是10000，

length-1是15，用2进制表示是1111，

2*length为32，length用2进制表示是100000，

2*length-1为31，length用2进制表示是11111，

所以hash&(length-1)的计算结果与hash&(2*length-1)的计算结果差别在于扩容后需要多看一位，也就是看第N位的1与hash值的&结果。

假设原数组长度为16，length-1二进制表示为1111。key1的hash值为9，二进制表示为01001，key2的hash值为25，11001，

所以hash&(length-1)的结果只需看低4位的结果，9和25的低4位都是1001，所以计算结果一致，计算结果都是9，所以在数组中处于数组下标为9的元素链表中。

扩容后数组长度为32，length-1二进制表示为11111，key1的hash值为9，二进制表示为01001，key2的hash值为25，11001，

所以hash&(2*length-1)的结果需要看低5位的结果，9和25的低4位都是1001，所以计算结果不一致，计算结果都是9和25，由于key2的hash值的第五位为1，key1的hash值的第五位为0，所以会多16，也就是原数组长度的大小。

所以原数组同一下标index下的链表存储的hash冲突的元素，扩容后在新数组中的下标newIndex要么为index，要么为index+length（去决定于hash值的第N位为1，还是0，也就是hash&length的结果，原数组长度length为2的N-1次幂）

所以会遍历链表(或者者红黑树)，而后对数组下标index下每个节点计算hash&length的结果，而后存放在两个不同的临时链表中，遍历完成后，hash&length结果为0的元素组成的临时链表会存储在新数组index位置，hash&length结果为1的元素组成的临时链表会存储在新数组index+length位置。

ConcurrentHashMap是怎样记录元素个数size的？

HashMap默认是非线程安全的，可以认为每次只有一个线程来执行操作，所以hashMap就使用一个很简单的int类型的size变量来记录HashMap键值对数量就行了。

HashMap记录键值对数量的实现如下：

transient int size;public int size() {    return size;}

ConcurrentHashMap记录键值对数量的实现如下：

//size方法最大只能返回Integer.MAX_VALUEpublic int size() {    long n = sumCount();    return ((n < 0L) ? 0 : (n > (long)Integer.MAX_VALUE) ?Integer.MAX_VALUE : (int)n);}//mappingCount方法可以返回long类型的最大值，public long mappingCount() {    long n = sumCount();    return (n < 0L) ? 0L : n; // ignore transient negative values}private transient volatile long baseCount;private transient volatile CounterCell[] counterCells;//sumCount会返回sumCount加上CounterCells数组中每个元素as存储的valuefinal long sumCount() {        CounterCell[] as = counterCells; CounterCell a;        long sum = baseCount;        if (as != null) {                for (int i = 0; i < as.length; ++i) {                    if ((a = as[i]) != null)                            sum += a.value;                }        }        return sum;}@sun.misc.Contended //这个注解可以避免伪共享，提升性能。加与不加，性能差距达到了 5 倍。在缓存系统中，因为一个缓存行是出于32-256个字节之间，常见的缓存行为64个字节。而一般的变量可能达不到那么多字节，所以会出现多个相互独立的变量存储在一个缓存行中的情况，此时即使多线程访问缓存行上相互独立变量时，也涉及到并发竞争，会有性能开销，加了@sun.misc.Contended这个注解，在jDK8中，会对对象前后都添加128字节的padding，使用2倍于大多数硬件缓存行的大小来避免相邻扇区预取导致的伪共享冲突。static final class CounterCell {    volatile long value;    CounterCell(long x) { value = x; }}

每次增加x个新的键值对后，会调用addCount()方法使用CAS操作对baseCount+x，假如操作失败，那么会新建一个CounterCell类型的对象，保存新添加的数量x，并且将对象增加到CounterCells数组中去。

为什么ConcurrentHashMap，HashTable不支持key，value为null？

由于HashMap是非线程安全的，默认单线程环境中使用，假如get(key)为null，可以通过containsKey(key)
方法来判断这个key的value为null，还是不存在这个key，而ConcurrentHashMap，HashTable是线程安全的，
在多线程操作时，由于get(key)和containsKey(key)两个操作和在一起不是一个原子性操作，
可能在执行中间，有其余线程修改了数据，所以无法区分value为null还是不存在key。
至于ConcurrentHashMap，HashTable的key不能为null，主要是设计者的设计用意。

HashSet和HashMap的区别？

HashMap主要是用于存储非重复键值对，HashSet存储非重复的对象。尽管HashMap是继承于AbstractMap，实现了Map接口，HashSet继承于AbstractSet，实现了Set接口。但是因为它们都有去重的需求，所以HashSet主要实现都是基于HashMap的（假如需要复用一个类，我们可以使用继承模式，也可以使用组合模式。组合模式就是将一个类作为新类的组成部分，以此来达到复用的目的。）例如，在HashSet类中，有一个HashMap类型的成员变量map，这就是组合模式的应用。

    public class HashSet<E>    extends AbstractSet<E>    implements Set<E>, Cloneable, java.io.Serializable{    private transient HashMap<E,Object> map;    private static final Object PRESENT = new Object();//占位对象    public HashSet() {        map = new HashMap<>();    }    public boolean add(E e) {        return map.put(e, PRESENT)==null;//占位对象    }}

在HashSet的构造方法中，创立了一个HashMap，赋值给map属性，之后在增加元素时，就是将元素作为key增加到HashMap中，只不过value是一个占位对象PRESENT。除了 clone()、writeObject()、readObject()是 HashSet 自己不得不实现之外，其余方法都是直接调用 HashMap 中的方法。那么HashMap又是如何实现key不重复的呢？

在调用HashMap的putVal方法增加新的键值对时，会进行如下操作：

1.根据key计算hash值。

2.根据hash值映射数组下标，而后获取数组下标的对应的元素。

3.数组下标存储的是一个链表，链表包含了哈希冲突的元素，会对链表进行遍历，判断hash1==hash2，除此以外，还必需要key1==key2，或者者key1.equals(key2)。

由于两个不同的对象的hashCode可能相等，但是相同的对象的hashCode一定相等，

==是判断两个变量或者实例是不是指向同一个内存地址，假如是同一个内存地址，对象一定相等。

int hash = hash(key);//根据key计算hash值p = tab[i = (n - 1) & hash];//根据hash值映射数组下标，而后获取数组下标的对应的元素。for (int binCount = 0; ; ++binCount) {//数组下标存储的是一个链表，链表包含了哈希冲突的元素，会对链表进行遍历，判断每个节点的hash值与插入元素的hash值能否相等，并且是存储key对象的地址相等，或者者key相等。if (e.hash == hash &&    ((k = e.key) == key || (key != null && key.equals(k))))        break;        p = e;}

HashMap遍历时删除元素的有哪些实现方法？

首先结论如下：

第1种方法 – for-each遍历HashMap.entrySet，使用HashMap.remove()删除(结果：抛出异常)。

第2种方法-for-each遍历HashMap.keySet，使用HashMap.remove()删除(结果：抛出异常)。

第3种方法-使用HashMap.entrySet().iterator()遍历删除(结果：正确删除)。

下面让我们来详细探索一下起因吧！

HashMap的遍历删除方法与ArrayList的大同小异，只是api的调用方式不同。首先初始化一个HashMap，我们要删除key包含”3″字符串的键值对。

HashMap<String,Integer> hashMap = new HashMap<String,Integer>();hashMap.put("key1",1);hashMap.put("key2",2);hashMap.put("key3",3);hashMap.put("key4",4);hashMap.put("key5",5);hashMap.put("key6",6);

第1种方法 – for-each遍历HashMap.entrySet，使用HashMap.remove()删除(结果：抛出异常)

for (Map.Entry<String,Integer> entry: hashMap.entrySet()) {        String key = entry.getKey();        if(key.contains("3")){            hashMap.remove(entry.getKey());        }     System.out.println("当前HashMap是"+hashMap+" 当前entry是"+entry);}

输出结果：

当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前entry是key1=1当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前entry是key2=2当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前entry是key5=5当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前entry是key6=6当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4} 当前entry是key3=3Exception in thread "main" java.util.ConcurrentModificationException    at java.util.HashMap$HashIterator.nextNode(HashMap.java:1429)    at java.util.HashMap$EntryIterator.next(HashMap.java:1463)    at java.util.HashMap$EntryIterator.next(HashMap.java:1461)    at com.test.HashMapTest.removeWayOne(HashMapTest.java:29)    at com.test.HashMapTest.main(HashMapTest.java:22)

第2种方法-for-each遍历HashMap.keySet，使用HashMap.remove()删除(结果：抛出异常)

Set<String> keySet = hashMap.keySet();for(String key : keySet){    if(key.contains("3")){        keySet.remove(key);    }    System.out.println("当前HashMap是"+hashMap+" 当前key是"+key);}

输出结果如下：

当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前key是key1当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前key是key2当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前key是key5当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前key是key6当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4} 当前key是key3Exception in thread "main" java.util.ConcurrentModificationException    at java.util.HashMap$HashIterator.nextNode(HashMap.java:1429)    at java.util.HashMap$KeyIterator.next(HashMap.java:1453)    at com.test.HashMapTest.removeWayTwo(HashMapTest.java:40)    at com.test.HashMapTest.main(HashMapTest.java:23)

第3种方法-使用HashMap.entrySet().iterator()遍历删除(结果：正确删除)

Iterator<Map.Entry<String, Integer>> iterator  = hashMap.entrySet().iterator();while (iterator.hasNext()) {    Map.Entry<String, Integer> entry = iterator.next();    if(entry.getKey().contains("3")){        iterator.remove();    }    System.out.println("当前HashMap是"+hashMap+" 当前entry是"+entry);}

输出结果：

当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 当前entry是key1=1当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 当前entry是key2=2当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 当前entry是key5=5当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 当前entry是key6=6当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 当前entry是key4=4当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4} 当前entry是deletekey=3

第1种方法和第2种方法抛出ConcurrentModificationException异常与上面ArrayList错误遍历-删除方法的起因一致，HashIterator也有一个expectedModCount，在遍历时获取下一个元素时，会调用next()方法，而后对
expectedModCount和modCount进行判断，不一致就抛出ConcurrentModificationException异常。

abstract class HashIterator {    Node<K,V> next;        // next entry to return    Node<K,V> current;     // current entry    int expectedModCount;  // for fast-fail    int index;             // current slot    HashIterator() {        expectedModCount = modCount;        Node<K,V>[] t = table;        current = next = null;        index = 0;        if (t != null && size > 0) { // advance to first entry            do {} while (index < t.length && (next = t[index++]) == null);        }    }    public final boolean hasNext() {        return next != null;    }    final Node<K,V> nextNode() {        Node<K,V>[] t;        Node<K,V> e = next;        if (modCount != expectedModCount)            throw new ConcurrentModificationException();        if (e == null)            throw new NoSuchElementException();        if ((next = (current = e).next) == null && (t = table) != null) {            do {} while (index < t.length && (next = t[index++]) == null);        }        return e;    }    public final void remove() {        Node<K,V> p = current;        if (p == null)            throw new IllegalStateException();        if (modCount != expectedModCount)            throw new ConcurrentModificationException();        current = null;        K key = p.key;        removeNode(hash(key), key, null, false, false);        expectedModCount = modCount;    }}

PS：ConcurrentModificationException是什么？

根据ConcurrentModificationException的文档详情，少量对象不允许并发修改，当这些修改行为被检测到时，就会抛出这个异常。（例如少量集合不允许一个线程一边遍历时，另一个线程去修改这个集合）。

少量集合（例如Collection, Vector, ArrayList，LinkedList, HashSet, Hashtable, TreeMap, AbstractList, Serialized Form）的Iterator实现中，假如提供这种并发修改异常检测，那么这些Iterator可以称为是”fail-fast Iterator”，意思是快速失败迭代器，就是检测到并发修改时，直接抛出异常，而不是继续执行，等到获取到少量错误值时在抛出异常。

异常检测主要是通过modCount和expectedModCount两个变量来实现的，

• modCount
  集合被修改的次数，一般是被集合(ArrayList之类的)持有，每次调用add()，remove()方法会导致modCount+1

• expectedModCount
  期待的modCount，一般是被Iterator(ArrayList.iterator()方法返回的iterator对象)持有，一般在Iterator初始化时会赋初始值，在调用Iterator的remove()方法时会对expectedModCount进行升级。（可以看看上面的ArrayList.Itr源码）

而后在Iterator调用next()遍历元素时，会调用checkForComodification()方法比较modCount和expectedModCount，不一致就抛出ConcurrentModificationException。

单线程操作Iterator不当时也会抛出ConcurrentModificationException异常。（上面的例子就是）

总结

由于ArrayList和HashMap的Iterator都是上面所说的“fail-fast Iterator”，Iterator在获取下一个元素，删除元素时，都会比较expectedModCount和modCount，不一致就会抛出异常。

所以当使用Iterator遍历元素(for-each遍历底层实现也是Iterator)时，需要删除元素，肯定需要使用 Iterator的remove()方法 来删除，而不是直接调用ArrayList或者HashMap自身的remove()方法,否则会导致Iterator中的expectedModCount没有及时升级，之后获取下一个元素或者者删除元素时，expectedModCount和modCount不一致，而后抛出ConcurrentModificationException异常。