JDK1.8源码-07-java.util.HashMap

字数统计: 8.8k字   |   阅读时长≈ 36分钟

JDK1.8源码-08-java.util.HashMap

本篇来介绍在 JDK1.8 中 HashMap 的源码实现，这也是最常用的一个集合。但是在介绍 HashMap 之前，我们先介绍什么是 Hash表。

B站很好的HashMap视频： https://www.bilibili.com/video/BV1LJ411W7dP

1. 哈希表

Hash表也被称为散列表，也有直接译为哈希表，Hash表是一个根据关键字值（key-value）而直接进行访问的数据结构。

也就是说它通过把关键码映射到表中一个位置来访问记录，以此来加快查找的速度。

在链表，数组等数据结构中，查找某个关键字，通常要遍历整个数据结构，也就是O(N)的时间复杂度，但对于哈希表来说，只是O(1)的时间复杂度。

比如对于，ArrayList集合和LinkedList来说，如果要查找两个集合中的某个元素，通常是通过遍历整个集合，需要O(N)的时间复杂度。

mark

如果是哈希表的话，它是通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。只需要O(1)的时间复杂度。

mark

①、存放在哈希表中的数据是key-value 键值对，比如存放哈希表的数据为:

　　{Key1-Value1,Key2-Value2,Key3-Value3,Key4-Value4,Key5-Value5,Key6-Value6}

如果我们想查找是否存在键值对 Key3-Value3，首先通过 Key3 经过散列函数，得到值 k3，然后通过 k3 和散列表对应的值找到是 Value3。

②、当然也有可能存放哈希表的值只是 Value1,Value2,Value3这种类型：

{Value1,Value2,Value3,Value4,Value5,Value6}

这时候我们假设Value1是等于Key1的，也就是{Value1-Value1,Value2-Value2,Value3-Value3,Value4-Value4,Value5-Value5,Value6-Value6}。可以将Value1经过散列函数转换成与散列表对应的值。

1
大家都用过汉语字典吧，汉语字典的优点是我们可以通过前面的拼音目录快速定位到所要查找的汉字。当给定我们某个汉字时，大脑会自动将汉字转换成拼音（如果我们认识，不认识可以通过偏旁部首），这个转换的过程我们可以看成是一个散列函数，之后在根据转换得到的拼音找到该字所在的页码，从而找到该汉字。

汉语字典是哈希表的典型实现，但是我们仔细思考，会发现这样几个问题？

①、为什么要有散列函数？

对于第一个问题，散列函数的存在能够帮助我们更快的确定key和value的映射关系，试想一下，如果没有汉字和拼音的转换规则（或者汉字和偏旁部首的），给你一个汉字，你该如何从字典中找到该汉字？我想除了遍历整部字典，你没有什么更好的办法。

②、多个 key 通过散列函数会得到相同的值，这时候怎么办？

对于第二个问题，多个key通过散列函数得到相同的值，这其实也就是哈希表最大的问题–冲突，比如同音字汉字，我们得到的拼音就是相同的。那么我们该如何在字典中存放同音字汉字呢？有两种做法：

  • 第一种：开放地址法

    • 当我们遇到冲突了，这时候通过另一种函数再计算一遍，得到相应的映射关系。
    • 比如对于汉语字典，一个字 “余”，拼音是“yu”，我们将其放在页码为567(假设在该位置)，这时候又来了一个汉字“于”，拼音也是“yu”，那么这时候我们要是按照转换规则，也得将其放在页码为567的位置，但是我们发现这个页码已经被占用了，这时候怎么办？我们可以在通过另一种函数，得到的值加1。那么汉字”于”就会被放在576+1=577的位置。

  • 第二种：链地址法

    • 我们可以将字典的每一页都看成是一个子数组或者子链表，当遇到冲突了，直接往当前页码的子数组或者子链表填充即可。
    • 那么我们进行同音字查找的时候，可能需要遍历其子数组或者子链表。如下图所示：

mark

小结：

  • 对于开放地址法，可能会遇到二次冲突，三次冲突，所以需要良好的散列函数，分布的越均匀越好。
  • 对于链地址法，虽然不会有二次冲突，但是如果一次冲突很多，那么会造成子数组或者子链表。

2. 什么是HashMap?

听名字就知道，HashMap 是一个利用哈希表原理来存储元素的集合。遇到冲突时，HashMap 是采用的链地址法来解决，

  • 在JDK1.7中，HashMap是由数组+链表构成的。

  • 但是在 JDK1.8 中，HashMap 是由 数组+链表+红黑树构成，新增了红黑树作为底层的数据结构，结构变复杂了，但是效率也更高效。

mark

3. 定义

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射，而且 key 和 value 都可以为 null。

1
2
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

mark

首先该类实现了一个Map接口，该接口定义的一组键和值对映射的通用操作。存储的一组成对的key-value对象，提供key到value的映射。

Map中的key不要求有序,不允许重复。

Map中的value同样不要求有序,但可以重复。

但是我们发现该接口方法有很多，我们设计某个键值对的集合有时候并不想实现那么多方法，那该怎么办？

JDK 还为我们提供了一个抽象类 AbstractMap ，该抽象类继承 Map 接口，所以如果我们不想实现所有的 Map 接口方法，就可以选择继承抽象类 AbstractMap 。

但是我们发现 HashMap 类即继承了 AbstractMap 接口，也实现了 Map 接口，这样做难道不是多此一举？后面我们会讲的 LinkedHashSet 集合也有这样的写法。

毕竟 JDK 经过这么多年的发展维护，起初也是认为这样是有具体的作用的，后来找了很多资料，发现这其实完全没有任何作用。[说明链接][https://stackoverflow.com/questions/2165204/why-does-linkedhashsete-extend-hashsete-and-implement-sete]

1
据 java 集合框架的创始人Josh Bloch描述，这样的写法是一个失误。在java集合框架中，类似这样的写法很多，最开始写java集合框架的时候，他认为这样写，在某些地方可能是有价值的，直到他意识到错了。显然的，JDK的维护者，后来不认为这个小小的失误值得去修改，所以就这样存在下来了。

HashMap集合还实现了Cloneable接口和Serializable接口，分别用来对对象进行克隆和序列化。

4. 字段属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//序列化和反序列化时，通过该字段进行版本一致性验证
   private static final long serialVersionUID = 362498820763181265L;
   //默认 HashMap 集合初始容量为16（必须是 2 的倍数）
   static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
   //集合的最大容量，如果通过带参构造指定的最大容量超过此数，默认还是使用此数
   static final int MAXIMUM_CAPACITY = 1 << 30;
   //默认的填充因子
   static final float DEFAULT_LOAD_FACTOR = 0.75f;
   //当桶(bucket)上的结点数大于这个值时会转成红黑树(JDK1.8新增)
   static final int TREEIFY_THRESHOLD = 8;
   //当桶(bucket)上的节点数小于这个值时会转成链表(JDK1.8新增)
   static final int UNTREEIFY_THRESHOLD = 6;
   /**(JDK1.8新增)
    * 当集合中的容量大于这个值时，表中的桶才能进行树形化 ，否则桶内元素太多时会扩容，
    * 而不是树形化 为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
    */
   static final int MIN_TREEIFY_CAPACITY = 64;

注意：后面三个字段是 JDK1.8 新增的，主要是用来进行红黑树和链表的互相转换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
     * 初始化使用，长度总是 2的幂
     */
    transient Node<K,V>[] table;

    /**
     * 保存缓存的entrySet（）
     */
    transient Set<Map.Entry<K,V>> entrySet;

    /**
     * 此映射中包含的键值映射的数量。（集合存储键值对的数量）
     */
    transient int size;

    /**
     * 跟前面ArrayList和LinkedList集合中的字段modCount一样，记录集合被修改的次数
     * 主要用于迭代器中的快速失败
     */
    transient int modCount;

    /**
     * 调整大小的下一个大小值（容量*加载因子）。capacity * load factor
     */
    int threshold;

    /**
     * 散列表的加载因子。
     */
    final float loadFactor;

下面我们重点介绍上面几个字段：

①、Node<K,V>[] table

HashMap是有数组+链表+红黑树组成，这里的数组就是table字段。后面对其进行初始化长度默认是 DEFAULT_INITIAL_CAPACITY= 16。

而且jdk声明数组长度总是2的n次方（一定是合数：合数是指在大于1的整数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。）。

为什么这里要求是合数，一般我们知道哈希算法为了避免冲突都要求长度是质数，这里要求是合数。下面在介绍 HashMap 的hashCode() 方法(散列函数)，我们再进行讲解。

②、size

集合中存放key-value 的数组大小。

③、loadFactor

装载因子，是用来衡量HashMap满的程度。计算HashMap的实时装载因子的方法为：size/capacity。而不是用占用桶的数量去除以capacity，capacity是桶的数量，也就是table的长度length。

默认的负载因子0.75 是对空间和时间效率的一个平衡选择，建议不要修改。

除非在时间和空间都比较特殊的情况下，如果内存空间很多而对时间效率的要求很高，可以降低loadFactor的值；相反，如果内存空间紧张同时又对时间效率要求不高，可以增加loadFactor的值，这个值可以大于1。

④、threshold

计算公式：capacity * loadFactor 。

这个值是当前已经数组长度的最大值。超过这个数目就要进行resize(扩容)。扩容后的HashMap容量是之前容量的两倍。

5. 构造函数

①、默认无参构造函数

1
2
3
4
5
6
/**
     * 默认构造函数，初始化加载因子loadFactor = 0.75
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; 
    }

无参构造器，初始化散列表的加载因子为0.75

②、指定初始容量的构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
     * 
     * @param initialCapacity 指定初始化容量
     * @param loadFactor 加载因子 0.75
     */
    public HashMap(int initialCapacity, float loadFactor) {
        //初始化容量不能小于 0 ，否则抛出异常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        //如果初始化容量大于2的30次方，则初始化容量都为2的30次方
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        //如果加载因子小于0，或者加载因子是一个非数值，抛出异常
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

    // 返回大于等于initialCapacity的最小的二次幂数值。
    // >>> 操作符表示无符号右移，高位取0。
    // | 按位或运算
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

6. 确定哈希桶数组索引位置

前面讲解哈希表的时候，我们知道是用散列函数来确定索引的位置。散列函数设计的越好，使得元素分布的越均匀。

HashMap 是数组+链表+红黑树的组合，我们希望在有限个数组位置的时候，尽量没有位置的元素只有一个，那么当我们用散列函数求得索引位置的时候，能马上知道对应位置的元素是不是我们想要的，而不是进行链表的遍历或者红黑树的遍历。这会大大优化我们的查询效率。

看一下HashMap中的hash算法：

1
2
3
4
5
6
7
static final int hash(Object key) {
        int h;
    // >>>表示无符号右移，也叫逻辑右移，即若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    i = (table.length - 1) & hash;//这一步是在后面添加元素putVal()方法中进行位置的确定

主要分为三步：

  1. 取HashCode的值：key.hashCode()
  2. 高位参与运算：h>>>16
  3. 取模运算：(n-1) & hash

这里获取 hashCode() 方法的值是变量，但是我们知道，对于任意给定的对象，只要它的 hashCode() 返回值相同，那么程序调用 hash(Object key) 所计算得到的 hash码 值总是相同的。

为了让数组元素分布均匀，我们首先想到的是把获得的 hash码对数组长度取模运算( hash%length)，但是计算机都是二进制进行操作，取模运算相对开销还是很大的，那该如何优化呢？

HashMap使用的方法很巧妙，它通过hash&(table.length-1)来得到该对象的保存位，前面说过HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。

当length总是2的n次方的时候，hash & (length-1)运算等价于对 length 取模，也就是hash%length。但是&比%具有更高的效率。比如 n % 32 = n & (32 -1)

这也解释了为什么要保证数组的长度总是2的n次方。

再就是在JDK1.8中还有个高位参与运算，hashCode()得到的是一个32位的int类型的值，通过hashCode()的高16位 异或 低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度，功效，质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低bit都参数Hash的计算中，同时不会有太大的开销。

下面举例说明：n为table的长度：

mark

7. 添加元素

JDK1.8中put方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//hash(key)就是上面讲的hash方法，对其进行了第一步和第二步处理
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    /**
     * 
     * @param hash 索引的位置
     * @param key  键
     * @param value  值
     * @param onlyIfAbsent true 表示不要更改现有值
     * @param evict false表示table处于创建模式
     * @return
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
            boolean evict) {
         Node<K,V>[] tab; Node<K,V> p; int n, i;
         //如果table为null或者长度为0，则进行初始化
         //resize()方法本来是用于扩容，由于初始化没有实际分配空间，这里用该方法进行空间分配，后面会详细讲解该方法
         if ((tab = table) == null || (n = tab.length) == 0)
             n = (tab = resize()).length;
         //注意：这里用到了前面讲解获得key的hash码的第三步，取模运算，下面的if-else分别是 tab[i] 为null和不为null
         if ((p = tab[i = (n - 1) & hash]) == null)
             tab[i] = newNode(hash, key, value, null);//tab[i] 为null，直接将新的key-value插入到计算的索引i位置
         else {//tab[i] 不为null，表示该位置已经有值了
             Node<K,V> e; K k;
             if (p.hash == hash &&
                 ((k = p.key) == key || (key != null && key.equals(k))))
                 e = p;//节点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);
                         //链表长度大于8，转换成红黑树
                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                             treeifyBin(tab, hash);
                         break;
                     }
                     //key已经存在直接覆盖value
                     if (e.hash == hash &&
                         ((k = e.key) == key || (key != null && key.equals(k))))
                         break;
                     p = e;
                 }
             }
             if (e != null) { // existing mapping for key
                 V oldValue = e.value;
                 if (!onlyIfAbsent || oldValue == null)
                     e.value = value;
                 afterNodeAccess(e);
                 return oldValue;
             }
         }
         ++modCount;//用作修改和新增快速失败
         if (++size > threshold)//超过最大容量，进行扩容
             resize();
         afterNodeInsertion(evict);
         return null;
    }

  1. 判断键值对数组table是否为空或者为null,否则执行resize()进行扩容或进行空间分配；

  2. 根据键值对key计算hash值得到插入的数组索引i,如果table[i] == null，直接就在新建节点添加；转下下面的6,如果talbe[i] 不为空，转向3

  3. 判断talbe[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向4，这里的相同指的是hashcode以及equals。

  4. 判断table[i]是否是treeNode，即table[i]是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向5

  5. 遍历table[i]，判断链表长度是否大于8，大于8的话就把链表转换成红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可。

  6. 插入成功后，判断实际存在的键值对数量size是否超过了最大容量threshold，如果超过，则进行扩容。

  7. 如果新插入的key不存在，则返回null,如果新插入的key存在，则返回原key对应的value值（注意新插入的value会覆盖原来的value值）

注意1：看第58，59行代码：

1
2
if (++size > threshold)//超过最大容量，进行扩容
    resize();

这里有个考点，我们知道 HashMap 是由数组+链表+红黑树（JDK1.8）组成，如果在添加元素的时候，发生冲突，会将冲突的数放在链表上，当链表长度超过8时。会自动转换成红黑树。

那么有如下问题：数组上有5个元素，而某个链表上有3个元素，问此HashMap的 size 是多大？

我们分析第58,59 行代码，很容易知道，只要是调用put()方法添加元素，那么就会调用++size（这里有个例外是插入重复的key的键值对，不会调用，但是重复的key元素不会影响到size）

所以，上面的答案是7

注意2：看第 53 、 60 行代码：

1
2
afterNodeAccess(e);
afterNodeInsertion(evict);

这里调用的该方法，其实是调用了如下实现方法：

1
2
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }

　　这都是一个空的方法实现，我们在这里可以不用管，但是在后面介绍 LinkedHashMap 会用到，LinkedHashMap 是继承的 HashMap，并且重写了该方法，后面我们会详细介绍。

8. 扩容机制

扩容（resize），我们知道集合是由数组+链表+红黑树构成，向 HashMap 中插入元素时，如果HashMap 集合的元素已经大于了最大承载容量threshold（capacity * loadFactor），这里的threshold不是数组的最大长度。

那么必须扩大数组的长度，Java中的数组都是无法自动扩容的，我们采用的方法是用一个更大的数组代替这个小的数组。就好比以前用的事小桶装水，现在小桶装不下了，使用一个更大的桶。

  • JDK1.8融入了红黑树的机制，比较复杂，这里我们先介绍 JDK1.7的扩容源码，便于理解，然后在介绍JDK1.8的源码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//参数 newCapacity 为新数组的大小
    void resize(int newCapacity) {
        Entry[] oldTable = table;//引用扩容前的 Entry 数组
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {//扩容前的数组大小如果已经达到最大(2^30)了
            threshold = Integer.MAX_VALUE;///修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
            return;
        }

        Entry[] newTable = new Entry[newCapacity];//初始化一个新的Entry数组
        transfer(newTable, initHashSeedAsNeeded(newCapacity));//将数组元素转移到新数组里面
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//修改阈值
    }
    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {//遍历数组
            while(null != e) {
                Entry<K,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;//访问下一个 Entry 链上的元素
            }
        }
    }

通过方法我们可以看到，JDK1.7中首先是创建一个新的大容量的数组，然后依次重新计算原集合所有元素的索引，然后重新赋值。

如果数组某个位置产生了hash冲突，使用的是单链表的头插入方式，同一个位置的新元素总是放在链表的头部，这样与原集合链表对比，扩容之后的可能就是倒序的链表了。

下面我们在看看JDK1.8的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.
 *
 * @return the table
 */
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    // 原数组如果为null，则长度赋值0
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 如果原数组长度大于0
    if (oldCap > 0) {
        // 数组大小如果已经大于等于最大值(2^30)
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 原数组长度大于等于初始化长度16，并且原数组长度扩大1倍也小于2^30次方
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 阈值扩大一倍
            newThr = oldThr << 1; // double threshold
    }
    // 旧阈值大于0，则将新容量直接等于旧的阈值 
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // 阈值等于0，oldCap也等于0（集合未进行初始化）
    else {               // zero initial threshold signifies using defaults
        // 数组长度初始化为16
        newCap = DEFAULT_INITIAL_CAPACITY;
        // 阈值等于16*0.75 = 12 
        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) {
        // 把每个bucket都移动到新的buckets中
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                // 元数据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;
                        }
                        // 原索引+oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原索引放到bucket里
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 原索引+oldCap放到bucket里
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

该访问分为两部分，首先是计算新桶数组的容量newCap和新阈值newThr，然后将原集合的元素重新映射到新集合中。

mark

相比较于JDK1.7, JDK1.8使用的是2次幂扩展（指长度扩展为原来的两倍）。所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。

在扩充HashMap的时候，不需要像JDK1.7那样重新计算hash值，只需要看看原来的hash值新增的那个bit是1还是0就好了，如果是0的话索引不变，是1的话索引变成“原索引+oldCap”。

9. 删除元素

HashMap删除元素首先是要找到桶的位置，然后如果是链表，则进行链表遍历。找到需要删除的元素后，进行删除。

如果是红黑树，也就是进行树的遍历，找到元素删除后，进行平衡调节。需要注意的是，当红黑树的节点小于6的时候，会自动转换成链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/**
 * Removes the mapping for the specified key from this map if present.
 *
 * @param  key key whose mapping is to be removed from the map
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
 *         (A <tt>null</tt> return can also indicate that the map
 *         previously associated <tt>null</tt> with <tt>key</tt>.)
 */
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}


/**
 * Implements Map.remove and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to match if matchValue, else ignored
 * @param matchValue if true only remove if value is equal
 * @param movable if false do not move other nodes while removing
 * @return the node, or null if none
 */
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    // (n - 1) & hash找到桶的位置
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // 如果键的值与链表的第一个节点相等，则将node指向该节点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        // 如果桶节点存在下一个节点
        else if ((e = p.next) != null) {
            // 红黑树
            if (p instanceof TreeNode)
                //找到需要删除的红黑树节点
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            // 是链表的话，遍历链表，找到待删除的节点
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 删除节点，并进行调节红黑树平衡
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            // 红黑树
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // 链表
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

注意第 46 行代码：

1
afterNodeRemoval(node);

这也是为实现 LinkedHashMap 做准备的，在这里和上面一样，是一个空方法实现，可以不用管。而在 LinkedHashMap 中进行了重写，用来维护删除节点后，链表的前后关系。

10. 查找元素

①、通过 key 查找 value

首先通过key找到计算索引，找到桶位置。

先检查第一个节点，如果是则返回，如果不是，则遍历其后面的链表或者红黑树。其余情况全部返回null。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

/**
 * Implements Map.get and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @return the node, or null if none
 */
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 根据key计算的索引  检查第一个索引
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 不是第一个节点
        if ((e = first.next) != null) {
            // 遍历树进行查找
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 遍历链表进行查找
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

②、判断是否存在给定的 key 或者 value

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
   /**
    * Returns <tt>true</tt> if this map contains a mapping for the
    * specified key.
    *
    * @param   key   The key whose presence in this map is to be tested
    * @return <tt>true</tt> if this map contains a mapping for the specified
    * key.
    */

// 根据key来吵着
   public boolean containsKey(Object key) {
       return getNode(hash(key), key) != null;
   }



   /**
    * Returns <tt>true</tt> if this map maps one or more keys to the
    * specified value.
    *
    * @param value value whose presence in this map is to be tested
    * @return <tt>true</tt> if this map maps one or more keys to the
    *         specified value
    */
   public boolean containsValue(Object value) {
       Node<K,V>[] tab; V v;
       if ((tab = table) != null && size > 0) {
           //   遍历桶
           for (int i = 0; i < tab.length; ++i) {
               //  遍历桶的每个节点的元素
               for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                   if ((v = e.value) == value ||
                       (value != null && value.equals(v)))
                       return true;
               }
           }
       }
       return false;
   }

11. 遍历元素

首先构造一个 HashMap 集合：

1
2
3
4
HashMap<String, Object> map = new HashMap<>();
map.put("A","1");
map.put("B","2");
map.put("C","3");

①、分别获取 key 集合和 value 集合。

1
2
3
4
5
6
7
//1、分别获取key和value的集合
for(String key : map.keySet()){
    System.out.println(key);
}
for(Object value : map.values()){
    System.out.println(value);
}

②、获取 key 集合，然后遍历key集合，根据key分别得到相应value

1
2
3
4
5
// 2. 获取key集合，然后遍历key集合，根据key分别得到相应的value
Set<String> keySet = map.keySet();
for (Object str : keySet) {
    System.out.println(str + "->" + map.get(str));
}

③、得到 Entry 集合，然后遍历 Entry

1
2
3
4
5
// 3. 得到Entry集合，然后遍历Entry
Set<Map.Entry<String, Object>> entrySet = map.entrySet();
for (Map.Entry<String, Object> entry : entrySet) {
    System.out.println(entry.getKey() + "-->" + entry.getValue());
}

④、迭代

1
2
3
4
5
6
// 4. 迭代
Iterator<Map.Entry<String, Object>> iterator = map.entrySet().iterator();
while (iterator.hasNext()){
    Map.Entry<String, Object> mapEntry = iterator.next();
    System.out.println(mapEntry.getKey()+ "-->" + mapEntry.getValue());
}

基本上使用第三种方法的性能是最好的

第一种遍历方法我们只需要key集合或者只需要value集合时候使用

第二种遍历方法效率太低，不用就行

第四种效率也还行，关键是在遍历的过程中我们可以对元素进行删除。

12. 总结

Java7 HashMap的问题：

  1. 并发环境下的死锁

  2. 可以通过精心构造的恶意请求引发Dos攻击

HashMap总结：

①、基于JDK1.8的HashMap是由数组+链表+红黑树组成，当链表长度超过 8 时会自动转换成红黑树，当红黑树节点个数小于 6 时，又会转化成链表。相对于早期版本的 JDK HashMap 实现，新增了红黑树作为底层数据结构，在数据量较大且哈希碰撞较多时，能够极大的增加检索的效率。

②、允许 key 和 value 都为 null。key 重复会被覆盖，value 允许重复。

③、非线程安全

④、无序（遍历HashMap得到元素的顺序不是按照插入的顺序）

参考链接：

https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html#

https://www.cnblogs.com/ysocean/p/8711071.html

https://www.cnblogs.com/nullllun/p/8327664.html

13. HashMap 死循环

参考博客：https://www.jianshu.com/p/1e9cf0ac07f4

  • HashMap 在并发使用的时候可能发生死循环，导致cpu100%
  • 如果是在单线程下使用HashMap，自然是没有问题的，如果后期由于代码优化，这段逻辑引入了多线程并发执行
    • 在一个未知的时间点，会发现CPU占用100%，居高不下，通过查看堆栈，会惊讶的发现，线程都则赛在hashMap 的 get() 方法上，服务器重启之后，问题消失，过段时间又出来了。
    • 这是为什么？

原因分析

  1. 在内部，hashMap 使用一个 Entry 数组保存key value, 当一对key value 被加入的时候，会通过hashmap的寻址算法得到数组下标index,算法很简单，根据key的hash值，对数组的大小取模 hash & (table.length - 1),并把结果插入数组的对应位置，如果该位置上已经有元素了，就说明存在hash冲突，这样会在index位置生成链表。
  2. 如果存在hash冲突，最惨的情况，就是所有元素都定位到同一个位置，形成一个长长的链表，这样get一个值时，最坏情况需要遍历所有节点，性能变成了O(n)，所以元素的hash值算法和HashMap的初始化大小很重要。
  3. 当插入一个新的节点时，如果不存在相同的key，则会判断当前内部元素是否已经达到阈值（默认是数组大小的0.75），如果已经达到阈值，会对数组进行扩容，也会对链表中的元素进行rehash.

举例分析

  • 假设HashMap初始化大小为4，插入个3节点，不巧的是，这3个节点都hash到同一个位置，如果按照默认的负载因子的话，插入第3个节点就会扩容，为了验证效果，假设负载因子是1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,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;
        }
    }
}

以下是节点移动的相关逻辑。

mark

  • 插入第4个节点时，发生rehash，假设现在有两个线程同时进行，线程1和线程2，两个线程都会新建新的数组。

mark

  1. 假设 线程2 在执行到Entry<K,V> next = e.next;之后，cpu时间片用完了，这时变量e指向节点a，变量next指向节点b。
  2. 线程1继续执行，很不巧，a、b、c节点rehash之后又是在同一个位置7，开始移动节点
  3. 第一步，移动节点a
  4. 第二步，移动节点b
  5. 注意，这里的顺序是反过来的，继续移动节点c

mark

mark

mark

  1. 这个时候 线程1 的时间片用完，内部的table还没有设置成新的newTable， 线程2 开始执行，这时内部的引用关系如下：

  2. 这时，在 线程2 中，变量e指向节点a，变量next指向节点b，开始执行循环体的剩余逻辑。

mark

1
2
3
4
5
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;

执行之后的引用关系如下图

mark

  1. 执行后，变量e指向节点b，因为e不是null，则继续执行循环体，执行后的引用关系

mark

变量e又重新指回节点a，只能继续执行循环体，这里仔细分析下：
1、执行完Entry<K,V> next = e.next;，目前节点a没有next，所以变量next指向null；
2、e.next = newTable[i]; 其中 newTable[i] 指向节点b，那就是把a的next指向了节点b，这样a和b就相互引用了，形成了一个环；
3、newTable[i] = e 把节点a放到了数组i位置；
4、e = next; 把变量e赋值为null，因为第一步中变量next就是指向null；

所以最终的引用关系是这样的：

mark

节点a和b互相引用，形成了一个环，当在数组该位置get寻找对应的key时，就发生了死循环。

另外，如果线程2把newTable设置成到内部的table，节点c的数据就丢了，看来还有数据遗失的问题。

所以在并发的情况，发生扩容时，可能会产生循环链表，在执行get的时候，会触发死循环，引起CPU的100%问题，所以一定要避免在并发环境下使用HashMap。

打赏
  • 版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！
  • © 2019-2022 Zhuuu
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信