JCF_02 Map 数据结构对比


阅读数: 次   
如需转载，请根据 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 许可，附上本文作者及链接。
本文作者： 执笔成念
作者昵称： zbcn
本文链接： https://1363653611.github.io/zbcn.github.io/2020/10/08/JCF_02Map%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%AF%B9%E6%AF%94/

ConCurrentHashMap

put 方法分析

image-20200817135444955

源码

1
public V put(K key, V value) {
2
    return putVal(key, value, false);
3
}
4
5
final V putVal(K key, V value, boolean onlyIfAbsent) {
6
    //判断key==null 或者 value == null，如果是，抛出空指针异常。
7
    if (key == null || value == null) throw new NullPointerException();
8
    //根据key计算hash值(计算结果跟HashMap是一致的，写法不同)。
9
    int hash = spread(key.hashCode());
10
    int binCount = 0;
11
    //开始插入或者更新元素
12
    for (Node<K,V>[] tab = table;;) {
13
        Node<K,V> f; int n, i, fh;
14
        if (tab == null || (n = tab.length) == 0) //当前的tab 没有初始化
15
            //初始化tab
16
            //在initTable方法中，为了控制只有一个线程对table进行初始化，当前线程会通过CAS操作对SIZECTL变量赋值为-1，如果赋值成功，线程才能初始化table，否则会调用Thread.yield()方法让出时间片
17
            tab = initTable();
18
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {//如果tab 的当前位置没有元素
19
            //（Node<K,V> f根据hash值计算得到数组下标，下标存储的元素，f可能是null，链表头节点，红黑树根节点或迁移标志节点ForwardNode）说明当前位置还没有哈希冲突的键值对。那么根据key和value创建一个Node，使用CAS操作设置在当前数组下标下,并且退出循环
20
            if (casTabAt(tab, i, null,
21
                         new Node<K,V>(hash, key, value, null)))
22
                break;                   // no lock when adding to empty bin
23
        }
24
        //f.hash = -1, 说明ConcurrentHashMap正在在扩容，当前的节点f是一个标志节点，当前下标存储的hash冲突的元素已经迁移了。
25
        else if ((fh = f.hash) == MOVED)
26
            //当前线程会调用helpTransfer()方法来辅助扩容，扩容完成后会将tab指向新的table，然后继续执行for循环
27
            tab = helpTransfer(tab, f);
28
        else {//除上面三种以外情况
29
            V oldVal = null;
30
            //添加值前,加锁:f tab位置的头节点
31
            synchronized (f) {
32
                if (tabAt(tab, i) == f) {
33
                    if (fh >= 0) {//f.hash > 0,当前数组下标存储的是一个链表，f是链表的头结点。
34
                        binCount = 1;
35
                        //遍历链表
36
                        for (Node<K,V> e = f;; ++binCount) {
37
                            K ek;
38
                            //遍历的节点跟当前需要插入节点的hash值相同,key 也相同
39
                            if (e.hash == hash &&
40
                                ((ek = e.key) == key ||
41
                                 (ek != null && key.equals(ek)))) {
42
                                oldVal = e.val;
43
                                if (!onlyIfAbsent) //onlyIfAbsent= false ,则用当前的value替换遍历元素的value ,然后退出
44
                                    e.val = value;
45
                                break;
46
                            }
47
                            Node<K,V> pred = e;
48
                            if ((e = e.next) == null) {//否则找出链表中的最后一个元素,则根据key，value创建一个Node<K,V>，添加到链表末尾
49
                                pred.next = new Node<K,V>(hash, key,
50
                                                          value, null);
51
                                break;
52
                            }
53
                        }
54
                    }
55
                    else if (f instanceof TreeBin) { //如果f是TreeBin类型,那么说明当前数组下标存储的是一个红黑树，f是红黑树的根节点，调用putTreeVal方法，插入或更新节点
56
                        Node<K,V> p;
57
                        binCount = 2;
58
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
59
                                                              value)) != null) {
60
                            oldVal = p.val;
61
                            if (!onlyIfAbsent)
62
                                p.val = value;
63
                        }
64
                    }
65
                }
66
            }
67
            if (binCount != 0) {//判断binCount（数组下标存储是一个链表时，binCount是链表长度）
68
                if (binCount >= TREEIFY_THRESHOLD)//当binCount超过8时,并且数组的长度大于64时
69
                    //调用treeifyBin方法将链表转换为红黑树。
70
                    treeifyBin(tab, i);
71
                if (oldVal != null)
72
                    return oldVal;
73
                //break出for循环
74
                break;
75
            }
76
        }
77
    }
78
    //判断元素个数是否超过阈值,如果超过,则进行扩容
79
    addCount(1L, binCount);
80
    return null;
81
}

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方法，插入或更新节点。

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

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

NOTE:

很多技术文章都是说链表长度大于8就转换为红黑树，我当时也没有注意这个细节，直到有个群里的朋友指正，当原来的链表长度超过8时，确实会调用treeifyBin方法，但是在treeifyBin方法中会判断当前tab是否为空，或者数组长度是否小于64，如果满足条件，那么调用resize方法对tab初始化或者扩容，就不会将链表转换为红黑树了。

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

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

底层数据结构

1
transient Node<K,V>[] table; //HashMap
2
3
transient volatile Node<K,V>[] table;//ConcurrentHashMap
4
5
private transient Entry<？,？>[] table;//HashTable

HashMap=数组+链表+红黑树

HashMap的底层数据结构是一个数组+链表+红黑树，数组的每个元素存储是一个链表的头结点，链表中存储了一组哈希值冲突的键值对，通过链地址法来解决哈希冲突的。为了避免链表长度过长，影响查找元素的效率，当链表的长度>8时，会将链表转换为红黑树，链表的长度<6时，将红黑树转换为链表(但是红黑树转换为链表的时机不是在删除链表时，而是在扩容时，发现红黑树分解后的两个链表<6，就按链表处理，否则就建立两个小的红黑树，设置到扩容后的位置)。之所以临界点为8是因为红黑树的查找时间复杂度为logN，链表的平均时间查找复杂度为N/2，当N为8时，logN为3，是小于N/2的，正好可以通过转换为红黑树减少查找的时间复杂度。而且,依据泊松分布,每个桶中,链表的长度 8的可能性特别小.详见源码注释说明,

Hashtable=数组+链表

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

ConcurrentHashMap=数组+链表+红黑树

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

线程安全

HashMap 非线程安全

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

HashTable 线程安全

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

ConcurrentHashMap 线程安全

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

CAS操作

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

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

synchronized锁

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

1
Node<K,V> f = tabAt(tab, i = (n - 1) & hash));
2
synchronized (f) {//f就是数组下标存储的元素
3
    if (tabAt(tab, i) == f) {
4
        if (fh >= 0) {
5
            binCount = 1;
6
            for (Node<K,V> e = f;; ++binCount) {
7
                K ek;
8
                if (e.hash == hash &&
9
                    ((ek = e.key) == key ||
10
                     (ek != null && key.equals(ek)))) {
11
                    oldVal = e.val;
12
                    if (!onlyIfAbsent)
13
                        e.val = value;
14
                    break;
15
                }
16
                Node<K,V> pred = e;
17
                if ((e = e.next) == null) {
18
                    pred.next = new Node<K,V>(hash, key,
19
                                              value, null);
20
                    break;
21
                }
22
            }
23
        }
24
        else if (f instanceof TreeBin) {
25
            Node<K,V> p;
26
            binCount = 2;
27
            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
28
                                           value)) != null) {
29
                oldVal = p.val;
30
                if (!onlyIfAbsent)
31
                    p.val = value;
32
            }
33
        }
34
    }
35
}

执行效率

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

是否允许null值出现

  • HashMap的key和null都可以为null，如果key为null，那么计算的hash值会是0，最终计算得到的数组下标也会是0，所以key为null的键值对会存储在数组中的首元素的链表中。value为null的键值对也能正常插入，跟普通键值对插入过程一致。
1
static final int hash(Object key) {
2
	int h;
3
	return (key == null) ？ 0 : (h = key.hashCode()) ^ (h >>> 16);
4
}
  • HashTable的键和值都不能为null，如果将HashTable的一个键值对的key设置为null，因为null值没法调用hashCode()方法获取哈希值，所以会抛出空指针异常。同样value为null时，在put方法中会进行判断，然后抛出空指针异常。
1
public synchronized V put(K key, V value) {
2
        // Make sure the value is not null
3
        if (value == null) {
4
            throw new NullPointerException();
5
        }
6
        Entry<？,？> tab[] = table;
7
        int hash = key.hashCode();
8
        ...其他代码
9
}

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

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

初始容量及扩容

不指定初始容量

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

指定初始容量

如果制定了初始容量，HashMap和ConcurrentHashMap的容量会是比初始容量稍微大一些的2的幂次方大小，HashTable会使用初始容量，

扩容

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

hash值计算

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

1
public synchronized V put(K key, V value) {
2
         ...其他代码
3
        // Makes sure the key is not already in the hashtable.
4
        Entry<？,？> tab[] = table;
5
        int hash = key.hashCode();
6
        int index = (hash & 0x7FFFFFFF) % tab.length;
7
        ...其他代码
8
}

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的整数次幂的原因）

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

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 会根据扩容后的数组长度初始化话一个新的数组，并且直接赋值给当前hashMap的成员变量table。
1
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
2
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次幂时，

1
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，因为key2的hash值的第五位为1，key1的hash值的所以原数组同一下标index下的链表存储的hash冲突的元素，扩容后在新数组中的下标newIndex要么为index，要么为index+length（去决定于hash值的第N位为1，还是0，也就是hash&length的结果，原数组长度length为2的N-1次幂）第五位为0，所以会多16，也就是原数组长度的大小。

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

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

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

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

1
transient int size;
2
public int size() {
3
	return size;
4
}

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

1
//size方法最大只能返回Integer.MAX_VALUE
2
public int size() {
3
    long n = sumCount();
4
    return ((n < 0L) ？ 0 : (n > (long)Integer.MAX_VALUE) ？Integer.MAX_VALUE : (int)n);
5
}
6
7
//mappingCount方法可以返回long类型的最大值，
8
public long mappingCount() {
9
    long n = sumCount();
10
    return (n < 0L) ？ 0L : n; // ignore transient negative values
11
}
12
13
private transient volatile long baseCount;
14
private transient volatile CounterCell[] counterCells;
15
16
//sumCount会返回sumCount加上CounterCells数组中每个元素as存储的value
17
final long sumCount() {
18
		CounterCell[] as = counterCells; CounterCell a;
19
		long sum = baseCount;
20
		if (as != null) {
21
				for (int i = 0; i < as.length; ++i) {
22
					if ((a = as[i]) != null)
23
							sum += a.value;
24
				}
25
		}
26
		return sum;
27
}
28
//这个注解可以避免伪共享，提升性能。加与不加，性能差距达到了 5 倍。在缓存系统中，由于一个缓存行是出于32-256个字节之间，常见的缓存行为64个字节。而一般的变量可能达不到那么多字节，所以会出现多个相互独立的变量存储在一个缓存行中的情况，此时即便多线程访问缓存行上相互独立变量时，也涉及到并发竞争，会有性能开销，加了@sun.misc.Contended这个注解，在jDK8中，会对对象前后都增加128字节的padding，使用2倍于大多数硬件缓存行的大小来避免相邻扇区预取导致的伪共享冲突。
29
@sun.misc.Contended
30
static final class CounterCell {
31
    volatile long value;
32
    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，这就是组合模式的应用。

1
public class HashSet<E>
2
    extends AbstractSet<E>
3
    implements Set<E>, Cloneable, java.io.Serializable
4
{
5
    private transient HashMap<E,Object> map;
6
    private static final Object PRESENT = new Object();//占位对象
7
    public HashSet() {
8
        map = new HashMap<>();
9
    }
10
    public boolean add(E e) {
11
        return map.put(e, PRESENT)==null;//占位对象
12
    }
13
}

在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肯定相等，

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

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

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”字符串的键值对。

1
HashMap<String,Integer> hashMap = new HashMap<String,Integer>();
2
hashMap.put("key1",1);
3
hashMap.put("key2",2);
4
hashMap.put("key3",3);
5
hashMap.put("key4",4);
6
hashMap.put("key5",5);
7
hashMap.put("key6",6);
  • 第1种方法 - for-each遍历HashMap.entrySet，使用HashMap.remove()删除(结果：抛出异常)
1
for (Map.Entry<String,Integer> entry: hashMap.entrySet()) {
2
        String key = entry.getKey();
3
        if(key.contains("3")){
4
            hashMap.remove(entry.getKey());
5
        }
6
     System.out.println("当前HashMap是"+hashMap+" 当前entry是"+entry);
7
8
}

输出结果：

1
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前entry是key1=1
2
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前entry是key2=2
3
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前entry是key5=5
4
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前entry是key6=6
5
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4} 当前entry是key3=3
6
Exception in thread "main" java.util.ConcurrentModificationException
7
	at java.util.HashMap$HashIterator.nextNode(HashMap.java:1429)
8
	at java.util.HashMap$EntryIterator.next(HashMap.java:1463)
9
	at java.util.HashMap$EntryIterator.next(HashMap.java:1461)
10
	at com.test.HashMapTest.removeWayOne(HashMapTest.java:29)
11
	at com.test.HashMapTest.main(HashMapTest.java:22)
  • 第2种方法-for-each遍历HashMap.keySet，使用HashMap.remove()删除(结果：抛出异常)
1
Set<String> keySet = hashMap.keySet();
2
for(String key : keySet){
3
    if(key.contains("3")){
4
        keySet.remove(key);
5
    }
6
    System.out.println("当前HashMap是"+hashMap+" 当前key是"+key);
7
}

输出结果如下：

1
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前key是key1
2
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前key是key2
3
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前key是key5
4
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前key是key6
5
当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4} 当前key是key3
6
Exception in thread "main" java.util.ConcurrentModificationException
7
	at java.util.HashMap$HashIterator.nextNode(HashMap.java:1429)
8
	at java.util.HashMap$KeyIterator.next(HashMap.java:1453)
9
	at com.test.HashMapTest.removeWayTwo(HashMapTest.java:40)
10
	at com.test.HashMapTest.main(HashMapTest.java:23)
  • 第3种方法-使用HashMap.entrySet().iterator()遍历删除(结果：正确删除)
1
Iterator<Map.Entry<String, Integer>> iterator  = hashMap.entrySet().iterator();
2
while (iterator.hasNext()) {
3
    Map.Entry<String, Integer> entry = iterator.next();
4
    if(entry.getKey().contains("3")){
5
        iterator.remove();
6
    }
7
    System.out.println("当前HashMap是"+hashMap+" 当前entry是"+entry);
8
}

输出结果：

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

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

1
abstract class HashIterator {
2
    Node<K,V> next;        // next entry to return
3
    Node<K,V> current;     // current entry
4
    int expectedModCount;  // for fast-fail
5
    int index;             // current slot
6
7
    HashIterator() {
8
        expectedModCount = modCount;
9
        Node<K,V>[] t = table;
10
        current = next = null;
11
        index = 0;
12
        if (t != null && size > 0) { // advance to first entry
13
            do {} while (index < t.length && (next = t[index++]) == null);
14
        }
15
    }
16
17
    public final boolean hasNext() {
18
        return next != null;
19
    }
20
21
    final Node<K,V> nextNode() {
22
        Node<K,V>[] t;
23
        Node<K,V> e = next;
24
        if (modCount != expectedModCount)
25
            throw new ConcurrentModificationException();
26
        if (e == null)
27
            throw new NoSuchElementException();
28
        if ((next = (current = e).next) == null && (t = table) != null) {
29
            do {} while (index < t.length && (next = t[index++]) == null);
30
        }
31
        return e;
32
    }
33
34
    public final void remove() {
35
        Node<K,V> p = current;
36
        if (p == null)
37
            throw new IllegalStateException();
38
        if (modCount != expectedModCount)
39
            throw new ConcurrentModificationException();
40
        current = null;
41
        K key = p.key;
42
        removeNode(hash(key), key, null, false, false);
43
        expectedModCount = modCount;
44
    }
45
}

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异常。

LinkedHashMap

LinkedHashMap是HashMap的子类，与HashMap的实现基本一致，只是说所有的节点都有一个before和after指针，根据插入顺序形成一个双向链表。所以可以根据插入顺序进行遍历，默认accessOrder是false，也就是按照插入顺序来排序的，map.keySet().iterator().next()第一个元素是最早插入的元素的key。LinkedHashMap可以用来实现LRU算法。(accessOrder为true，会按照访问顺序来排序。) LRU算法实现：

1
//使用LinkedHashMap实现LRU算法(accessOrder为false的实现方式)
2
// LinkedHashMap默认的accessOrder为false，也就是会按照插入顺序排序，
3
// 所以在插入新的键值对时，总是添加在队列尾部，
4
// 如果是访问已存在的键值对，或者是put操作的键值对已存在，那么需要将键值对先移除再添加。
5
public class LRUCache{
6
    int capacity;
7
    Map<Integer, Integer> map;
8
    public LRUCache(int capacity) {
9
        this.capacity = capacity;
10
        map = new LinkedHashMap<>();
11
    }
12
    public int get(int key) {
13
        if (!map.containsKey(key)) { return -1; }
14
        //先删除旧的位置，再放入新位置
15
        Integer value = map.remove(key);
16
        map.put(key, value);
17
        return value;
18
    }
19
    public void put(int key, int value) {
20
        if (map.containsKey(key)) {
21
            map.remove(key);
22
            map.put(key, value);
23
            return;
24
        }
25
        map.put(key, value);
26
        //超出capacity，删除最久没用的,利用迭代器，删除第一个
27
        if (map.size() > capacity) {
28
  	map.remove(map.keySet().iterator().next());
29
        }
30
    }
31
}
32
//使用LinkedHashMap实现LRU算法(accessOrder为true的实现方式)
33
//如果是将accessOrder设置为true，get和put已有键值对时就不需要删除key了
34
public static class LRUCache2 {
35
    int capacity;
36
    LinkedHashMap<Integer, Integer> linkedHashMap;
37
    LRUCache2(int capacity) {
38
      this.capacity = capacity;
39
      linkedHashMap = new LinkedHashMap<Integer, Integer>(16,0.75f,true);
40
    }
41
    public int get(int key) {
42
      Integer value = linkedHashMap.get(key);
43
      return value == null ? -1 : value;
44
    }
45
    public void put(int key, int val) {
46
      Integer value = linkedHashMap.get(key);
47
      linkedHashMap.put(key, val);
48
      if (linkedHashMap.size() > capacity) {
49
       linkedHashMap.remove(linkedHashMap.keySet().iterator().next());
50
      }
51
    }
52
}

LinkedHashMap是怎么保存节点的插入顺序或者访问顺序的呢？

默认accessOrder为false，保存的是插入顺序，插入时调用的还是父类HashMap的putVal()方法，在putVal()中创建新节点时是会调用newNode()方法来创建一个节点，在newNode()方法中会调用linkNodeLast()方法将节点添加到双向链表的尾部。

1
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
2
                   boolean evict) {
3
//省略了部分代码...
4
tab[i] = newNode(hash, key, value, null);
5
//省略了部分代码...
6
}
7
//创建新节点
8
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
9
		LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
10
		linkNodeLast(p);
11
		return p;
12
}
13
//移动到双向链表尾部
14
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
15
    LinkedHashMap.Entry<K,V> last = tail;
16
    tail = p;
17
    if (last == null) head = p;
18
    else {
19
    		p.before = last;
20
    		last.after = p;
21
    }
22
}

如果accessOrder为true，会保存访问顺序，在访问节点时，会调用afterNodeAccess()方法将节点先从双向链表移除，然后添加到链表尾部。

1
public class LinkedHashMap<K,V>
2
    extends HashMap<K,V>
3
    implements Map<K,V>
4
{
5
//头结点，指向最老的元素
6
    transient LinkedHashMap.Entry<K,V> head;
7
//尾节点，指向最新的元素
8
    transient LinkedHashMap.Entry<K,V> tail;
9
//如果accssOrder为true，代表节点需要按照访问顺序排列，每次访问了元素，会将元素移动到尾部（代表最新的节点）。
10
public V get(Object key) {
11
        Node<K,V> e;
12
        if ((e = getNode(hash(key), key)) == null)
13
            return null;
14
        if (accessOrder)
15
            afterNodeAccess(e);
16
        return e.value;
17
}
18
//将节点从双向链表中删除，移动到尾部。
19
void afterNodeAccess(Node<K,V> e) { // move node to last
20
        LinkedHashMap.Entry<K,V> last;
21
        if (accessOrder && (last = tail) != e) {
22
            LinkedHashMap.Entry<K,V> p =
23
                (LinkedHashMap.Entry<K,V>)e,
24
            b = p.before, a = p.after;
25
            p.after = null;
26
            if (b == null) head = a;
27
            else b.after = a;
28
            if (a != null) a.before = b;
29
            else last = b;
30
            if (last == null) head = p;
31
            else {
32
                p.before = last;
33
                last.after = p;
34
            }
35
            tail = p;
36
            ++modCount;
37
        }
38
    }
39
}
赏

谢谢你请我吃糖果

支付宝
微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

身在井隅<br><br> 心想星光<br><br> 眼里有诗<br><br>自在远方