bytejava Java进阶手册

# HashMap源码分析

# HashMap介绍、使用

# HashMap介绍

HashMap是平时开发过程中经常会用到的数据结构，同时HashMap也是大量面试中会问道的数据结构。

HashMap是Map的一个实现类，能够提供key-value键值对的存储、查询、遍历。

# Map(HashMap)常用方法介绍

常用的接口有

  • V put(K key, V value) 向map中添加key value键值对
  • V putIfAbsent(K key, V value) 只有当对应的key不存在的时候，再会添加，也就是不会覆盖。
  • V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) 当key不存在的时候添加数据，value值通过mappingFunction计算出来
  • V get(Object key) 获取key对应的value值，如果没有返回null
  • V getOrDefault(Object key, V default) 获取key对应的value值，如果没有返回default值
  • boolean containsKey(Object key) 是否包含key
  • Set<Map.Entry<K, V> entrySet(Object key) 获取所有的键值对(Map.Entry)的集合
  • Set<K> keySet() 获取所有的key集合
  • Collection<V> values() 获取所有的value集合
  • boolean remove(Object key) 从map中删除某个key
  • void clear() 清空map
  • int size() 获取map中元素的数量
  • void forEach(BiConsumer<? super K, ? super V> action 遍历Map中的key value数据

# HashMap使用注意事项

# HashMap线程安全问题

HashMap在多线程环境下使用可能产生线程安全问题，比如原子性、可见性、重排序等问题（其中一种情况是很多人常说的死锁问题，注意这只是其中一个问题，线程安全能出现的问题有很多），所以如果在多线程会访问操作同一个HashMap实例的情况下，建议 进行加锁或使用ConcurrentHashMap，在多线程并发相关的文章中我们会详细介绍。

# 注意key的hashCode()和equals()方法

如果HashMap中的key是自定义的类，则要注意实现自定义的hashCode和equals方法，默认情况下equals的实现是判断两个对象引用是否相同，即是否是同一个对象。 所以在自定义类的情况下，建议要实现hashCode和equals方法，可以使用idea的快捷键(Command + N选择generate equals() and hashCode()))生成。 又因为HashMap采取先计算hash映射再遍历判断equals, 所以要保证如果两个对象equals那么他们的hashCode应该也相等，否则可能出现查询不到、put覆盖不到、删除不了的情况。

# 如果对性能要求比较高，通过构造函数指定initialCapacity

在一些对性能和内存要求比较高的场景，如果HashMap数据可能会比较多，可以通过guava的Maps.newHashMapWithExpectedSize创建HashMap减少resize扩容对cpu和内存的消耗。

# Collections.emptyMap不能添加数据

如果其他方法返回了一个Map，而且没有明确返回的是什么样的map，如果我们要对map进行添加数据再返回，则要小心Map不能添加数据比如Collections.emptyMap 这种情况，如果需要在Map添加数据，建议通过HashMap(Map<? extends K, ? extends V> m)构造函数创建一个新HashMap对象。

# 多使用lambda

lambda表达式能够让代码更加简洁，map相关的经常使用lambda表达式的函数有

  • computeIfAbsent中的mappingFunction
  • Map的forEach(BiConsumer<? super K, ? super V)
  • 其他集合类的stream转换成map，通过Collections.toMap转换成map，示例list.stream() .collect(Collectors.toMap(Function.identity(), Function.identity())，不过toMap要注意key重复的情况会抛出异常，可以使用有处理key重复的版本的函数

# 多使用工具类

如果是业务开发，尽量多使用工具类，比如Guava中的 ImmutableMap创建不可变的Map、apache common-collections中的CollectionUtils判断集合是否为空、长度等（减少null判断、NPE）

# HashMap实现原理详解

HashMap的内部存储结构为数组+链表的组合，通过对key计算hash，映射到数组中的某个index上，数组每个元素又形成链表，然后再遍历链表查找、插入数据。 hash计算和数组访问都是O(1)的时间复杂度，但是链表遍历时间复杂度是O(N) N是链表长度，所以为了避免链表过长导致性能变差，HashMap在元素相对数组长度比例超过一定阈值时 会进行数组扩容来降低链表的平均长度将链表长度维持在常数级别，所以整体的put、get操作的时间复杂度保持在O(1)

img.png

本文以jdk8源码为基础，jdk8中为了进一步提高链表查询的速度，当链表超过一定长度时会转换成红黑树，使得查找速度更快。

# 基本结构

# put方法实现流程

put方法计算好hash值后，调用putVal方法

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
1
2
3

hash方法的实现是，如果key为null，返回0；否则将key值的hashCode()值与自身无符号右移16位的值异或得到最终的hash。 hash方法的目的是让hash值在对数组长度取模后更加均匀，因为数组长度是2的次方，如果直接按照hashCode方法的结果进行取模，则hashCode高位部分大部分情况下都用不到， 在一些hashCode低位不很均匀的情况下（比如float)会导致分散不均，所以通过这种右移异或能让高位的数据参与进来使得hash分散。

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

putVal方法负责具体的写入过程，两个特殊参数说明一下

onlyIfAbsent: 用来实现putIfAbsent方法，如果为true则只有在key不存在的时候才会写入数据 evict: 用来实现LinkedHashMap中的淘汰功能，在LinkedHashMap的文章中会详细讲解。

putVal会先判断HashMap的数组是否为空或长度为0，如果是会调用resize()进行初始化

然后计算key对应的数组中的index，index通过取余得到，又因为HashMap的数组长度为2的n次方，

所以取余操作能够通过更轻量的hash & (n - 1)简化，这也避免了取余时hash为负的额外处理。

得到index后，获取数组中的元素，如果数组对应的元素为null，说明对应的key肯定不存在，且链表也没有创建， 则使用对应的key、value、hash值创建一个Node节点作为链表的头结点。HashMap中的链表节点使用Node表示。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
1
2
3
4
5
6
7

如果数组元素不为空，会先快速判断一下第一个节点的hash值和key的hash值是否相同， 如果相同再判断下是否是同一个对象（引用==判断）、或key不为null的情况下两个key是否equals 这里的优化是先用hash值做判断能够拦截大量的不相等的情况，然后再用引用是否相等判断，最后用equals方法，因为equals方法的计算开销更大。

    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
1
2
3
4
5

如果第一个元素和key不相等，则有两种情况

  1. 元素为红黑树的TreeNode，则委托给红黑树TreeNode的putTreeVal方法
        else if (p instanceof TreeNode)
           e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
1
2
  1. 元素为链表Node节点，则对链表元素一次进行遍历，判断key是否equals（判断方式也是先判断hash值、引用、最后使用equals方法），如果key equals，则说明要替换的是这个键值对，把Node保存下来。 如果遍历到了链表结尾(next引用为null)，说明HashMap中没有这个key，则创建一个新的Node，追加到链表的最后（next指向新创建的Node)。 如果发现链表的长度>=TREEIFY_THRESHOLD-1(TREEIFY_THRESHOLD是8，-1是因为头结点跳过了)，也就是加完新节点之后长度等于8，则调用treeifyBin将当前的链表转变为红黑树，注意在treeifyBin中还会判断当前数组的capacitiy如果小于MIN_TREEIFY_CAPACITY默认64，会进行resize而不是红黑树转换。 如果数组节点红黑树因为删除或resize导致数量小于等于UNTREEIFY_THRESHOLD(6)，也会从红黑树转变回链表。
        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;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

对于key存在的情况，需要判断onlyIfAbsent，如果onlyIfAbsent为false且Node的value为null(HashMap允许key和value为null，value为null也会替换)，则 修改Node节点的value值。 这里还会调用afterNodeAccess，这也是给LinkedHashMap预留的回调函数，能够实现类似LRU的功能。 key存在的情况下，可以直接返回oldValue值。

        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
1
2
3
4
5
6
7
8

如果key不存在，则putVal方法会给modCount加1，modCount用来在对Map进行迭代的过程中判断Map是否出现了迭代过程中的修改抛出ConcurrentModificationException

然后再增加size（Map元素数量），并且判断size是否超过了threshold值（size * loadFactor默认0.75)，如果超过会调用resize()方法给HashMap数组进行扩容。

调用afterNodeInsertion(evict)回调方法，是给LinkedHashMap实现LRU功能的。

最后返回null，因为put方法会返回key对应的旧的值，没有则返回null。

    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
1
2
3
4
5
6

# resize扩容实现

在put方法中我们看到了当HashMap第一次put时或元素数量超过threshold时会调用resize来初始化或扩容2倍数组长度。

如果是初始化的情况（oldTab == null)，则计算初始时Node数组的长度 oldTab为null时，oldThreshold是有可能大于0的，因为在HashMap的一个构造函数中可以指定HashMap的初始容量initialCapacity和loadFactor

tableSizeFor的计算逻辑是计算第一个大于等于initialCapacity的2的次方数，比如initialCapacity是10，tableSizeFor得到16；如果initialCapacity是42，tableSizeFor就是64。

但是因为HashMap中没有单独保存capacity的字段，所以使用的threshold保存初始化时设置的initialCapacity

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}
1
2
3
4
5
6
7
8
9
10
11
12

所以初始化的情况如果oldThr > 0，使用初始值的threshold作为数组长度，然后计算新的threshold的值（newCap * loadFactor)； 对于扩容的情况(也就是oldCap >0)，则使用oldCap * 2作为新的数组的长度，同时为了避免数组长度超过int最大值，做了数组最大长度限制，并且新的threshold也会变为原有的threshold的两倍。

在从旧的链表迁移到新链表时，原有的hash在对新的数组长度取模时，要么值为之前的index，要么是index + oldCapacity。 比如hash为3，旧的capacity为8，新capacity16，则新旧的index都是3，如果hash为11，则旧的index为3，新的index为11。 resize方法中把小于capacity的新index成为low低位，高于的成为high高位。如何判断是在高位还是低位呢，是通过hash和oldCap取余判断的，如果为0说明在低位，否则在高位。 比如前面的hash=3(0011)和oldCap=8(1000)取余，得到0，则在低位；对于11取余不为0，在高位。 这是因为在高位一定>oldCap(容量是2的次方），二进制中为1的位次中一定有oldCap中1的哪一个bit位，反之没有。

resize在迁移Node数据的时候还保留了链表Node的顺序

resize方法实现在下面代码中进行了详细注释。

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    // 计算old capacity即旧数组长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 记录oldThreshold
    int oldThr = threshold;
    int newCap, newThr = 0;
    // oldCap > 0说明是扩容的情况
    if (oldCap > 0) {
        // 如果已经超出MAXIMUM_CAPACITY，threshold设置为Integer.MAX_VALUE不再扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 否则设置新数组长度为老数组长度的两倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 在新数组长度 < MAXIMUM_CAPACITY并且 oldCap >= DEFAULT_INITIAL_CAPACITY的情况下，threshold也提高到之前的2倍
            newThr = oldThr << 1; // double threshold
    }
    // 初始化的情况，如果通过HashMap(initialCapacity)构造函数指定了初始的容量，则使用初始容量作为数组长度（也是2的次方）
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // 否则使用默认的DEFAULT_INITIAL_CAPACITY(16)作为数组容量和loadFactor(0.75)计算threshold(12)
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // newThr为0，是构造函数指定容量的情况，这时要重新计算一下threshold因为之前的threshold保存的是初始容量。
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 修改threshold值为计算的新的threshold
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    // 创建新数组
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // 替换table引用为新数组
    table = newTab;
    // 如果老数组不为空，说明是扩容的情况，需要迁移老数组中的所有Node
    if (oldTab != null) {
        // 对老数组中的Node进行顺序遍历
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // 如果数组上Node不为null，保存Node引用
            if ((e = oldTab[j]) != null) {
                // 设置数组长的引用为null，可以帮助GC尽快清理
                oldTab[j] = null;
                // 如果Node的next为null，说明这个数组上Node是唯一节点，直接赋值给newTab上的对应index位置
                // 因为新数组长度是老数组长度的2倍并且都是2的次方，所以从旧数组迁移到新数组，新的index要么和之前一直，要么是oldCap + index, 不会出现被其他index上的旧数组覆盖的情况。
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 如果next不为null并且是TreeNode红黑树节点，使用红黑树TreeNode的split方法进行拆分
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 
                else { // preserve order
                    // loHead表示是hash取模后在低位，也就是之前的index,loTail同理。
                    Node<K,V> loHead = null, loTail = null;
                    // hiHead表示hash取模后在高位，也就是旧index + oldCap，hiTail同理。
                    Node<K,V> hiHead = null, hiTail = null;
                    // next保存的是遍历旧table时的next指针，链表循环遍历用
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 如果e.hash & oldCap ==0 取余为0，说明在低位
                        if ((e.hash & oldCap) == 0) {
                            // 如果新的tail为null说明第一次写入，则初始化loHead
                            if (loTail == null)
                                loHead = e;
                            // 否则不为空，则追加到loTail结尾的next上
                            else
                                loTail.next = e;
                            // 更新loTail
                            loTail = e;
                        }
                        // 取余不为0，说明映射到新数组的高位上
                        else {
                            // 如果hiTail为null，第一次写入，保存hiHead
                            if (hiTail == null)
                                hiHead = e;
                            // 否则追加到hiTail结尾的next上
                            else
                                hiTail.next = e;
                            // 更新hiTail
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 最后更新newTab新数组的引用，分为低位高位两个链表
                    if (loTail != null) {
                        // 更新loTail.next为null，这一步也很关键，是因为next可能引用到旧的链表上的元素。
                        loTail.next = null;
                        // 保存loHead到新的数组的低位index上
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        // 更新hiTail.next为null，这一步也很关键，是因为next可能引用到旧的链表上的元素。
                        hiTail.next = null;
                        // 保存hiHead到新的数组的高位index上
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    // resize完成，返回newTab新数组
    return newTab;
}
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
104
105
106
107
108
109
110

# get实现

get方法相对put简单一些，通过计算hash计算数组中的index，再遍历链表查询即可。

get方法会调用getNode方法查找Node对象，如果Node不为空，返回Node的value值，否则返回null

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
1
2
3
4

getNode方法先判断数组是否为null，以及hash对应的index上的Node是否为null。 如果不为空，则判断首个Node，快速判断hash值、引用、equals，如果是同一个key，返回node。 否则如果是TreeNode，交给TreeNode.getTreeNode查找； 如果不是TreeNode说明是链表，则对链表进行遍历，对每个Node节点判断hash、key引用、equals，如果找到对应的Node，返回。 最后如果还是没有找到，返回null

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) {
        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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 问题

# 为什么数组长度是2的次方

  1. 便于做取余计算，通过 & (n-1)可以得到。
  2. 扩容时，一个链表扩容成两个，而不是多个。

# 红黑树实现

关于HashMap的红黑树实现，我们单独写一篇文章来分析。

# 总结

本篇文章我们学习了HashMap的使用方法、使用注意实现，并且深入了解了HashMap的三个核心方法，学习了HashMap的put实现流程，学习了HashMap的resize初始化扩容流程，学习了HashMap的get查询实现。

← ConcurrentHashMap →