HashMap源码了解一下

发表于 | 分类于 ， | 评论数：   |   字数统计: 6,100   |   阅读时长: 27min | 热度： ℃

前言

HashMap是我们最常使用的数据类型之一，也是面试中最容易问到的集合之一。本篇文章主要通过分析HashMap的源码，更深入的了解HashMap，以及对比HashMap在JDK1.8和JDK1.7的不同。

本文基于jdk1.8

HashMap简介

HashMap是一个散列表，属于java.util包，它存储的内容是键值对(key-value)映射 ，根据键的hashCode值存储数据。

HashMap类结构

HashMap类结构图

可以从上图看出，HashMap继承AbstractMap抽象类，实现了Cloneable，Serializable和Map接口。

ps：为什么HashMap继承了AbstractMap抽象类，还要实现Map接口？

​ Java集合框架的编写者Josh Bloch说这是一个错误。。在java集合框架中，类似这样的写法很多。 JDK的维护者，后来不认为这个小小的失误值得去修改。所以就这样存在下来了。

HashMap特点

  1. HashMap非线程安全，在多线程中保证线程安全的解决方法：使用ConcurrentHashMap，Map map = Collections.synchronizedMap(new HashMap());。
  2. HashMap底层是由数组和链表组成的，JDK1.8之后添加了红黑树，文章后续有介绍。
  3. HashMap的key和value都允许为null。
  4. HashMap的数据存储是无序的。
  5. 如果需要put的key为自定义的对象，需要重写该对象的equals方法和hashCode方法。注意如果对象是可变的，那你就有可能get不到你保存在HashMap中的数据了，所以重写hashCode的时候需要小心哦~

HashMap提供的API

方法名 方法解释
clear() 从HashMap中移除所有映射。
clone() 返回HashMap实例的浅表副本：key和value本身未被克隆。
compute( K key, BiFunction <? super K,? super V,? extends V> remappingFunction ) 根据key获取映射，如果存在将BiFunction的返回值设置为新的value，并返回新的value。如果获取不到映射，就设置新的映射。如果BiFunction的返回值为null，就删除该节点。
computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)
computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) 根据key获取映射，如果存在将BiFunction的返回值设置为新的value，并返回新的value。如果获取不到映射，就返回null。如果BiFunction的返回值为null，就删除该节点。
containsKey(Object key) 如果HashMap中包含指定key的映射，则返回true。
containsValue(Object value) 如果HashMap中包含指定value的一个或者多个映射，则返回true。
entrySet() 返回此HashMap中包含的映射的Set。
forEach(BiConsumer<? super K, ? super V> action) 将给定操作（BiConsumer）应用于HashMap的每一个元素，直到处理完所有数据或操作抛出异常为止。
get(Object key) 返回指定key映射到的值;如果HashMap中不包含key的映射，则返回null。
getOrDefault(Object key, V defaultValue) 返回指定key映射到的值;如果HashMap中不包含key的映射，则返回defaultValue。
isEmpty() 判断HashMap是否为空。
keySet() 返回HashMap中包含的key的Set。
merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) 功能大部分与compute相同，不同之处在于BiFunction中apply的参数，入参为oldValue、value，调用merge时根据两个value进行处理并返回value。
put(K key, V value) 将key和value添加到HashMap。
putAll(Map<? extends K, ? extends V> m) 将指定Map中的所有映射复制到此HashMap。
putIfAbsent(K key, V value) 如果HashMap中key不存在，就保存key-value映射，并返回null；反之就返回已存在的value，并不覆盖为value。
remove(Object key) 从HashMap中删除指定key的映射，并返回value。
remove(Object key, Object value) 只有在指定key映射到指定value时，才删除该数据。
replace(K key, V value) 替换key映射的value。
replace(K key, V oldValue, V newValue) 只有在指定key映射到指定oldValue时，才替换成newValue。
replaceAll(BiFunction<? super K, ? super V, ? extends V> function) 对HashMap调用给定函数（BiFunction）的结果替换每个数据的value，直到处理完所有数据或者该函数抛出异常。
size() 获取HashMap中的映射数量。
values() 返回HashMap中包含的value的集合。

HashMap源码

HashMap常量属性

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
/**
 * 初始容量为16，必须为2的幂次（这个后续会讲解）
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * 最大容量，2的30次，如果初始化的大小大于这个值，就会被这个最大容量代替
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 默认加载因子
 * 如果加载因子太大，空间利用率高，hash碰撞概率也越高；反之则hash碰撞概率低，空间利用率也越低
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 如果哈希桶（Node）中的节点数达到8，链表就会被转换为红黑树
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 与上面的属性相反，是将红黑树转换为链表的阈值
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 哈希桶（Node）转换为树（TreeNode）的最小容量
 */
static final int MIN_TREEIFY_CAPACITY = 64;

HashMap成员变量

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
/**
 * 哈希桶，在第一次使用时初始化，并调整为必要的大小。长度总是2的幂。
 */
transient Node<K,V>[] table;

/**
 * 哈希桶，在第一次使用时初始化，并调整为必要的大小。长度总是2的幂。
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * HashMap中k-v数据的数量
 */
transient int size;

/**
 * HashMap结构被修改的次数
 */
transient int modCount;

/**
 * HashMap下一次扩容的大小 (capacity * load factor)
 */
int threshold;

/**
 * 加载因子
 */
final float loadFactor;

HashMap内部类

Node

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
static class Node<K,V> implements Map.Entry<K,V> {
    /**
     * 定位数据在数组中的位置
     */
    final int hash;
    /**
     * HashMap中保存的数据的key
     */
    final K key;
    /**
     * HashMap中保存的数据的value
     */
    V value;
    /**
     * 链表的下一个node
     */
    Node<K,V> next;

    /**
     * 构造函数，设置hash，key，value，next
     */
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

TreeNode

TODO

HashMap构造函数

HashMap一共有四个构造函数：

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
/**
 * 指定初始容量和加载因子的构造函数
 */
public HashMap(int initialCapacity, float loadFactor) {
    // 判断初始容量是否小于0，是的话抛出参数非法的异常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    
    // 判断初始容量是否超过最大值，超过的话用最大值代替初始容量
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    // 判断加载因子是否小于0或者是否是数字，小于0或者非数字就抛出参数非法的异常
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    // 设置加载因子
    this.loadFactor = loadFactor;
    // 将初始容量设置为最接近的2的幂次大小
    this.threshold = tableSizeFor(initialCapacity);
}

/**
 * 指定初始容量的构造函数
 */
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
 * 使用默认值的构造函数
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

/**
 * 通过一个Map创建HashMap的构造函数
 */
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

HashMap静态工具方法

hash(Object key)

1
2
3
4
5
6
7
static final int hash(Object key) {
    int h;
    // key为null的话返回0
    // h = key.hashCode()：获取key的hashCode值
    // h ^ (h >>> 16)：利用hashCode的高16位与低16位进行异或，防止两个hashCode的高位不同，低位相同，导致hash碰撞
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

tab[i = (n - 1) & hash])

这是定位数组下标位置的一小段代码，其中n是数组的长度，hash是调用hash(Object key)方法返回的值。我们可以看到，这里使用数组长度减1然后与hash相与，获取数组下标。为什么要这么操作？

当n始终是2的幂次时，(n - 1) & hash相当于hash % n，即对hash取模。这也是hash算法中的除留余数法。

我们试一下数组长度为15和16，hashCode为4和5的情况下，计算数组下标的结果：

hash对比

很明显，假设数组长度为15，hashCode为4和5的时候，会发生hash碰撞，会降低查询效率和空间利用率。

ps：这也是为什么HashMap容量必须是2的幂次的原因。

仔细想一下，如果hashCode二进制为0001 0001 0001 0001 0000 0000 0010 1011和0000 0000 0000 0000 0000 0000 0010 1011的情况时，进行(n - 1) & hash，这样出来的下标是相同的。为了解决这个问题，HashMap使用hash(Object key)方法，进行高位异或运算，使得只有相同hash值的两个值才会被放到数组中的同一个位置上形成链表。

我们可以看一下下面的图：

高位异或运算hash对比

综上所述：HashMap的hash过程是：获取key的hashCode -> 高位异或运算 -> 取模运算。

hash流程

tableSizeFor(int cap)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static final int tableSizeFor(int cap) {
    // 防止cap已经是2的幂次，如果cap是2的幂次，不进行减1的话，最后的值会变成两倍的cap
    int n = cap - 1;
    // 使最高的1右边也确定为1，即有连续的两个1
    n |= n >>> 1;
    // 使最高的两个1右边也确定为两个1，即有连续的四个1
    n |= n >>> 2;
    // 使最高的四个1右边也确定为四个1，即有连续的八个1
    n |= n >>> 4;
    // 使最高的八个1右边也确定为八个1，即有连续的十六个1
    n |= n >>> 8;
    // 使最高的十六个1右边也确定为十六个1，即有连续的三十二个1
    n |= n >>> 16;
    // 加1，确保为2的幂次
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

代码里的描述可能有点抽象，不容易理解，让我们举个例子看一下：

假设我们传入的cap为33，然后tableSizeFor方法的流程如下：

tableSizeFor示例

HashMap重要方法解析

put(K key, V value)

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

  • putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)

    onlyIfAbsent：如果为true，就不改变已存在的key对应的value，只有key不存在才会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
    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和数组长度n）
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 定位数组下标，判断该位置是否null，如果为null，直接插入新节点（设置节点p和数组下标i）
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            // 如果定位到的节点hash和key与put的相同，后面会进行value覆盖（记录键k和节点e）
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 如果是红黑树节点，调用红黑树的putvalue方法
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            // 如果是链表节点
            else {
                // 遍历链表节点进行插入
                for (int binCount = 0; ; ++binCount) {
                    // 如果定位到的节点的下一个节点为null，将该节点插入到定位到的节点之后
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // 判断是否达到转换为红黑树的长度，如果达到了就进行转换
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 如果定位到的节点hash和key与put的相同，后面会进行value覆盖（记录键k和节点e）
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // 如果相同key的节点存在，就覆盖value，并返回旧值，操作次数不需要加1
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                // onlyIfAbsent为false或者旧值为null，进行覆盖
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                // HashMap定义了该方法，LinkedHashMap有实现
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // 操作次数加1
        ++modCount;
        // k-v映射数量加1，如果超过扩容阈值，就进行扩容
        if (++size > threshold)
            resize();
        // HashMap定义了该方法，LinkedHashMap有实现
        afterNodeInsertion(evict);
        return null;
    }

  • resize()

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
final Node<K,V>[] resize() {
    // 获取旧数组
    Node<K,V>[] oldTab = table;
    // 获取旧数组的长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 获取旧的扩容阈值
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 如果旧数组不为null
    if (oldCap > 0) {
        // 如果旧数组的长度达到了最大值，就设置扩容阈值为Integer最大值，返回旧数组，不进行扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 如果旧数组的长度没有达到最大值，并且将新的数组长度设置为旧数组的2倍没有超过最大值，以及旧数组长度大于默认值16
        // 将新的扩容阈值设置为旧的2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 如果旧数组为null，但是扩容阈值大于0（即new HashMap(int initialCapacity)后第一次put），将旧的扩容阈值设置为新数组的长度
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // 如果旧数组为null，且扩容阈值不大于0
    else {               // zero initial threshold signifies using defaults
        // 设置默认长度和计算扩容阈值
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 只有前面else if的条件满足下面的判断，设置新的扩容阈值
    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;
    // 如果旧数组不为null，将旧数组复制到新数组
    if (oldTab != null) {
        // 循环遍历
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // 如果数组中的节点不为null，进行复制操作
            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;
                        // 判断扩容之后hash新增的1bit是否是0
                        // 是的话添加到原位置节点列表
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 判断扩容之后hash新增的1bit是否是1
                        // 是的话添加到原位置加上原数组长度位置节点列表
                        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;
}

这样做的好处： TODO

  • treeifyBin(Node<K,V>[] tab, int hash)

    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
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        // 判断数组是否为空，或者数组长度是否小于哈希桶（Node）转换为树（TreeNode）的最小容量，满足的话进行扩容，即还没达到转换为红黑树的大小
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        // 达到了转为红黑树的大小，计算需要转换为红黑树的链表的数组下标
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                //新建一个树形节点，内容和当前链表节点e一致
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    //确定树头节点
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            //让数组的第一个元素指向新建的红黑树头结点，之后这个桶里的元素就是红黑树了
            if ((tab[index] = hd) != null)
                // 塑造红黑树，前面的只是创建了一个二叉树，并没有设置颜色值
                hd.treeify(tab);
        }
    }

  • 红黑树相关操作

    TODO

put(K key, V value)流程：

  1. 如果数组为空，进行第一次扩容。
  2. 计算key的hash
  3. 定位数组的下标：hash & (length – 1)。
  4. 如果该位置为null，插入新节点，操作计数，size+1，判断是否需要扩容，并返回null。
  5. 如果4不满足，判断该位置第一个节点的key是否与put的相符。
  6. 如果相符，就记录该节点。
  7. 如果不相符，判断该节点是否为红黑树。
  8. 如果该节点是红黑树，通过红黑树的方法进行put，记录返回节点。
  9. 如果该节点不是红黑树，就遍历列表，如果有key相符的节点，就记录该节点，如果没有就新增节点，并判断是否要转为红黑树。
  10. 判断记录节点是否为null
  11. 如果不为null，进行旧值覆盖，并返回旧值。
  12. 如果为null，操作计数，size+1，判断是否需要扩容，并返回null。

putIfAbsent(K key, V value)

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

onlyIfAbsent：为true，就不改变已存在的key对应的value，只有key不存在才会put。

putAll(Map<? extends K, ? extends V> m)

1
2
3
public void putAll(Map<? extends K, ? extends V> m) {
    putMapEntries(m, true);
}

  • putMapEntries(Map<? extends K, ? extends V> m, boolean evict)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            // 如果HashMap数组为null，进行初始化扩容阈值
            if (table == null) { // pre-size
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                if (t > threshold)
                    threshold = tableSizeFor(t);
            }
            // 如果传入的Map的size大于扩容阈值，就进行扩容
            else if (s > threshold)
                resize();
            // 遍历传入的Map，调用putVal进行添加k-v映射
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

    HashMap(Map<? extends K, ? extends V> m)也调用了putMapEntries方法。

get(Object key)

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

  • getNode(int hash, Object key)

    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
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // 数组不为空，定位到的数组下标对应的节点不为空（设置数组tab，设置数组长度n，设置定位到的第一个节点first）
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            // 判断第一个节点与需要获取的key是否相同（包括hash值），是的话就返回第一个节点（设置k）
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            // 没满足上面的判断，并且第一个节点的下一个节点不为null
            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);
            }
        }
        // 查找不到返回null
        return null;
    }

  • 红黑树相关操作

    TODO

get(Object key)流程：

  1. 计算key的hash值。
  2. 定位数组的下标：hash & (length – 1)。
  3. 返回key对应的值。其中查找节点流程：
    1. 如果定位到的数组下标的第一个节点与key相符，就返回该节点。
    2. 如果1没满足，判断是否是红黑树，如果是，则根据红黑树查找节点的方法返回节点。
    3. 如果2没满足，遍历链表，返回与key相符的节点。
    4. 如果3没满足，返回null。

getOrDefault(Object key, V defaultValue)

1
2
3
4
5
public V getOrDefault(Object key, V defaultValue) {
    Node<K,V> e;
    // 如果key不存在就返回默认值
    return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}

remove(Object key)

1
2
3
4
5
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

  • removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable)

    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
    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;
        // 数组不为空，定位到的数组下标对应的节点不为空（设置数组tab，设置数组长度n，设置定位到的节点p）
        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;
            // 如果p节点与需要remove的节点key相符，就记录为node
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            // p节点与需要remove的节点key不相符，并且p的下一个节点不为null
            else if ((e = p.next) != null) {
                // 如果是红黑树，根据红黑树的获取节点方法，获取节点记录为node
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    // 遍历链表，查找key相符的节点，并记录为node
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            // 如果记录的node不为null，并且matchValue为false或记录的node的value与传入的value相符，就进行remove
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                // 如果记录的node为红黑树，就调用红黑树的remove方法，移除节点，可能会触发红黑树转为链表的操作
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                // 如果记录的node是链表的第一个节点，将链表的第一个节点指向该节点的下一个节点
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                // 操作次数加1
                ++modCount;
                // HashMap中的映射数减1
                --size;
                // HashMap定义了该方法，LinkedHashMap有实现
                afterNodeRemoval(node);
                // 返回移除的节点
                return node;
            }
        }
        // 数组为空，返回null
        return null;
    }

  • 红黑树相关操作

    TODO

remove(Object key, Object value)

1
2
3
public boolean remove(Object key, Object value) {
    return removeNode(hash(key), key, value, true, true) != null;
}

replace(K key, V value)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public V replace(K key, V value) {
    Node<K,V> e;
    // 获取key对应的节点，如果不为null就进行替换
    if ((e = getNode(hash(key), key)) != null) {
        // 记录旧值
        V oldValue = e.value;
        // 替换旧值
        e.value = value;
        // HashMap定义了该方法，LinkedHashMap有实现
        afterNodeAccess(e);
        // 返回旧值
        return oldValue;
    }
    // 如果不存在就返回null
    return null;
}

replace(K key, V oldValue, V newValue)

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean replace(K key, V oldValue, V newValue) {
    Node<K,V> e; V v;
    // 获取key对应的节点，判断value是否相符，如果满足就进行替换
    if ((e = getNode(hash(key), key)) != null &&
        ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
        // 替换旧值
        e.value = newValue;
        // HashMap定义了该方法，LinkedHashMap有实现
        afterNodeAccess(e);
        return true;
    }
    return false;
}

compute相关方法和merge

TODO

HashMap引发死循环的情况

HashMap在JDK1.8和JDK1.7中的对比

总结

通过这篇文章，我们可以知道一下几个点：

  1. HashMap是线程不安全的，所以如果我们在多线程下，需要使用Collections.synchronizedMap或者ConCurrentHashMap。
  2. HashMap在JDK1.8中进行了很多优化，具体可以看HashMap在JDK1.8和JDK1.7中的对比这一节。
  3. HashMap中链表转为红黑树，需要满足两个条件，一是链表长度>=8，二是数组长度>=64。

ps：有一些TODO的内容，后续有空了再进行添加。

欢迎关注博主其他的文章。

感谢您的支持！

本文标题:HashMap源码了解一下

文章作者:yoga

发布时间:2017年01月22日 - 15:01

原始链接:https://yoga0521.github.io/2017/01/22/HashMap源码了解一下/

版权声明:本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。 转载请注明出处！