jdk源码阅读---HashMap

发表于 | 分类于

HashMap是我们最常用的集合类容器了，这篇文章阅读HashMap的源码做下总结，来深入理解HashMap。

HashMap

下图是HashMap类图，其中蓝色线条意味着继承，绿色线条意味着接口实现。
HashMap类图

HashMap描述

官方文档关于HashMap的介绍比较多，这里就不在贴出来了，主要有一下几点：

  • HashMap基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了不同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
  • HashMap该实现为基本操作（get和put）提供了恒定的性能，假设散列函数在桶之间正确分散元素。 迭代集合视图需要的时间与HashMap实例的“容量”（桶的数量）加上其大小（键值映射的数量）成正比。因此，如果迭代性能很重要，不要将初始容量设置得太高（或者负载因子太低）是非常重要的。
  • HashMap的一个实例有两个影响其性能的参数:初始容量和负载因子。容量是哈希表中的桶数（哈希桶数组的长度），初始容量只是创建哈希表时的容量。负载因子是一个度量，在它的容量自动增加之前，哈希表被允许达到的程度。当哈希表中的条目数（指的是键值对数）超过负载因子和当前容量的乘积时也就是阈值threshold，哈希表被重新散列(也就是说，内部数据结构被重新构建)，这样哈希表就有大约两倍的桶数。具体内容后面resize()会提到。
  • HashMap通常，默认加载因子（0.75）在时间和空间成本之间提供了良好的折衷。较高的值会减少空间开销，但会增加查找成本（反映在大部分HashMap类的操作中，包括get和put）。在设置初始容量时，应考虑映射中的条目数量及其负载因子，以尽量减少重新运行操作（resize）次数。如果初始容量大于最大条目数除以加载因子，则不会发生重新加载操作。
  • HashMap如果许多映射要存储在HashMap实例中，使用足够大的容量创建映射将允许映射存储的效率高于根据需要执行自动重新散列以增长表。请注意，使用具有相同 hashCode()的许多key会减慢任何哈希表的性能。为了改善影响，当键是Comparable时，这个类可以使用键之间的比较顺序来帮助打破关系。
  • HashMap请注意，此实现不同步。如果多个线程同时访问哈希映射，并且至少有一个线程在结构上修改了映射，则它必须在外部同步。（结构修改是添加或删除一个或多个映射的任何操作;仅更改与实例已包含的键相关的值不是结构修改。）这通常是通过在自然封装map的某个对象上进行同步来完成的。如果不存在这样的对象，则应该使用Collections.synchronizedMap方法包装该映射。这最好在创建时完成，以防止意外的非同步访问,map：Map m = Collections.synchronizedMap（new HashMap（…））;
  • HashMap所有这个类的“集合视图方法”返回的迭代器都是快速失败的：如果在迭代器创建后的任何时候，结构上都会修改映射，除了通过迭代器自己的remove方法之外，迭代器将抛出 ConcurrentModificationException。因此，面对并发修改，迭代器快速而干净地失败，而不是在将来未定的时间冒着任意的，非确定性的行为冒险。
  • HashMap请注意，迭代器的快速失败行为不能得到保证，因为一般来说，不可能在存在非同步并发修改的情况下做出任何硬性保证。失败快速迭代器尽最大努力抛出ConcurrentModificationException。因此，编写一个依赖于此异常的程序来保证正确性是错误的：迭代器的快速失败行为应该仅用于检测错误。 所以这里不应该用try catch 来尝试捕获异常.

    HashMap特点

  • HashMap底层是一个哈希桶数组，即链表数组，也是需要动态扩容（JDK1.8中进行了优化，当链表过长时(超过8)，将链表转换为红黑树）
  • HashMap不允许重复的键，允许重复的值
  • HashMap允许键为null（只允许一个），允许值为null，且键为null的键值对被放在第一位（索引0位置）
  • HashMap不是同步的，而HashTable是同步的
  • HashMap JDK 1.8中 resize后保证了原链表中的顺序

下图就是hashmap的存储结构示意图，图片来自网络，侵删。
HashMap

HashMap定义

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable{}
HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。

HashMap继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。

HashMap 的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。
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
//默认初始容量为16，必须为2的n次幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量为2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认加载因子为0.75f
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//默认的值为8，当桶中元素个数超过这个值时，需要使用红黑树节点替换链表节点。
//（桶的树化阈值）
static final int TREEIFY_THRESHOLD = 8;
//默认值为6，当扩容时，桶中元素个数小于这个值，就会把树形的桶元素 还原（切分）为链表结构。
//（树的链表还原阈值）
static final int UNTREEIFY_THRESHOLD = 6;
//当哈希表中的容量大于这个值时，表中的桶才能进行树形化，否则桶内元素太多时会扩容，而不是树形化
//为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
//为记录的数组
transient Node<K,V>[] table;
//保持缓存的entrySet（）
transient Set<Map.Entry<K,V>> entrySet;
//已存储元素的数量
transient int size;
//是用来实现fail-fast机制的
transient int modCount;
//下次扩容的临界值，size>=threshold就会扩容，threshold等于capacity*load factor
int threshold;
//加载因子
final float loadFactor;

上面代码中都已详细介绍了每个属性的含义。需要注意的是jdk8 HashMap 中有三个关于红黑树的关键参数:

  • TREEIFY_THRESHOLD
  • UNTREEIFY_THRESHOLD
  • MIN_TREEIFY_CAPACITY

jdk7与jdk8数据结构和参数方面的区别：
HashMap

HashMap构造方法

public HashMap() // 默认初始容量(16)和默认加载因子(0.75)的HashMap

public HashMap(int initialCapacity) // 构造一个指定初始容量和默认加载因子(0.75)的HashMap

public HashMap(int initialCapacity, float loadFactor) // 构造一个指定初始容量和加载因子的HashMap

public HashMap(Map m) // 构造一个映射关系与指定Map相同的HashMap

HashMap常用方法

get查找

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
 public V get(Object key) {
     Node<K,V> e;
     return (e = getNode(hash(key), key)) == null ? null : e.value;
 }
 
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;
 }
 
 public boolean containsKey(Object key) {
     return getNode(hash(key), key) != null;
 }

get方法和containsKey都是通过getNode实现。

（1）如何通过key的hash值找到key在数组中的位置？

注意代码line9，first = tab[(n - 1) & hash]，前面我们知道HashMap的容量是2的指数倍的，所以n-1可以保证低位全部都是1，例如n=16，n-1=1（00001111）。而(n - 1) & hash可以将hash值得高位置0，相当于hash%n，但计算速度比后者要快。

（2）找到该位置的对应节点

first表示该位置的第一个节点，当找到该位置时，总是要先检查一下first节点是不是查找的元素（line10-12）。若不是则往后遍历链表。

（3）hash(key)实现的原理

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

若非空，则高16位不变，低16位变成高16位和低16位的异或。为什么要这么做？前面我们知道定位是通过(length - 1) & hash，当length不够大时（也就是hashMap容量不够大），一直是hash值的低位起作用，这样容易造成碰撞（不同的hash值定位的结果相同），所以要提高高位的影响。然后就有了该操作。

注意key为null的情况，hashMap是允许key为null的，key为null的entry（键值对）存储在存储数组的0号位。

也可以查找value是否在集合中

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
    }

这里总结两个源码实现的小技巧：

（1）在遍历数组前先检查数组是否为空。((tab = table) != null && size > 0)

（2）判断对象是否相等的方式。((v = e.value) == value || (value != null && value.equals(v)))

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
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
 public V put(K key, V value) {
     // 对key的hashCode()做hash
     return putVal(hash(key), key, value, false, true);
 }
 
 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                boolean evict) {
     Node<K,V>[] tab; Node<K,V> p; int n, i;
      // 判断hash表是否为空，如果为空，则进行表空间扩容
     if ((tab = table) == null || (n = tab.length) == 0)
         n = (tab = resize()).length;
     // 判断通过Key得到的hash值在当前数组中是否存在对应的元素，如果不存在，
     //则新建链表节点并赋值给数组。如果值存在，则进入else分支
     if ((p = tab[i = (n - 1) & hash]) == null)
         tab[i] = newNode(hash, key, value, null);
     else {
         Node<K,V> e; K k;
         // 判断数组存储的内容是否和Key相等，相等则覆盖
         if (p.hash == hash &&
             ((k = p.key) == key || (key != null && key.equals(k))))
             e = p;
          // 如果不相等，则判断节点是不是红黑树
         else if (p instanceof TreeNode)
             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
         else {
         // 如果不相等也不是红黑树，则是链表。遍历链表
             for (int binCount = 0; ; ++binCount) {
              // 如果遍历链表的尾端也没有找到key值相同的节点，则新建一个Node,然后添加到第一个元素的后面
                 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;
             }
         }
         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;
 }
 //向红黑树插入 or 更新数据（键值对）
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                    int h, K k, V v) {
         Class<?> kc = null;
         boolean searched = false;
         TreeNode<K,V> root = (parent != null) ? root() : this;
         for (TreeNode<K,V> p = root;;) {
             int dir, ph; K pk;
             if ((ph = p.hash) > h)
                 dir = -1;
             else if (ph < h)
                 dir = 1;
             else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
                 return p;
             else if ((kc == null &&
                       (kc = comparableClassFor(k)) == null) ||
                      (dir = compareComparables(kc, k, pk)) == 0) {
                 if (!searched) {
                     TreeNode<K,V> q, ch;
                     searched = true;
                     if (((ch = p.left) != null &&
                          (q = ch.find(h, k, kc)) != null) ||
                         ((ch = p.right) != null &&
                          (q = ch.find(h, k, kc)) != null))
                         return q;
                 }
                 dir = tieBreakOrder(k, pk);
             }

             TreeNode<K,V> xp = p;
             if ((p = (dir <= 0) ? p.left : p.right) == null) {
                 Node<K,V> xpn = xp.next;
                 TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
                 if (dir <= 0)
                     xp.left = x;
                 else
                     xp.right = x;
                 xp.next = x;
                 x.parent = x.prev = xp;
                 if (xpn != null)
                     ((TreeNode<K,V>)xpn).prev = x;
                 moveRootToFront(tab, balanceInsertion(root, x));
                 return null;
             }
         }
     }

下图是HashMap添加操作的流程图(图片来自：http://tech.meituan.com/java-hashmap.html)
HashMap

jdk7与jdk8关于put操作的区别
HashMap

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
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) { // 容量不为空（已分配内存空间）
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab; //已到最大值，没法继续扩容
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY) //容量增为2倍，并检查
            newThr = oldThr << 1; // 将阈值也扩为2倍
    }
    else if (oldThr > 0) // 若容量为0，old阈值大于0。容量用阈值表示（见构造函数1）
        newCap = oldThr;
    else {               // 若容量为0，old阈值也为0。使用默认值初始化（见构造函数3）
        newCap = DEFAULT_INITIAL_CAPACITY;
        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) { //将旧的值复制到新的存储桶里面
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null) //如果该位置只有1个元素，直接插如到新的位置（从新计算位置）
                    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; // 当前个元素的next指向下一个元素
                            loTail = e; //尾节点移向下一个个元素
                        }
                        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;
}

下面重点分析line40-66，这里的任务是处理oldTab[j]位置的值不是单个元素，而是由多个元素组成链表的情况。

原理是通过头节点Head定位第一个元素，通过尾节点Tail的不断后移组装链表。但是为什么这里要使用两组头尾节点呢？（loHead+loTail、hiHead+hiTail）

这里是定位用的。举个例子原集合容量为16（0001 0000），(e.hash & oldCap) == 0表示hash值的第5位（从右往左）为0，这样扩容后定位为e.hash & （newCap-1）= e.hash &31（0001 1111），计算后第5位也为0，与旧集合的位置一样。所以line62直接将链表存在和同样的位置上。否则hash值的第5位为1，定位计算后第5位也为0，与原来相比大了2（5-1）=16，正好是大了旧集合的容量，所以line66定位用j+oldCap。可以把容量为32的新集合简单理解为高16位和低16位，结合取模计算就很好理解了。

jdk8扩容时数据存储位置重新计算的方式
HashMap

Thanks

本篇文章只是对HashMap常用的一些方法的源码解析，至于红黑树和链表的相互转换，红黑树下的平衡、删除等操作后面打算专一写一篇关于红黑树的操作，这里就不再展开。感谢一下博客：

https://juejin.im/post/5aa5d8d26fb9a028d2079264

https://www.cnblogs.com/ouym/p/8952328.html

https://blog.csdn.net/u011240877/article/details/53358305

https://www.jianshu.com/p/4a7d891312c9