深入理解 HashMap

发表于 更新于 分类于 阅读次数： 本文字数： 12k 阅读时长 ≈ 11 分钟
JDK1.7 与 JDK1.8 中的 HashMap 数据结构与存取原理，这要是不知道，可不太行。

HashMap

JDK1.7 中的 HashMap

1. 数据结构

hashmap7

这是 HashMap 中比较核心的几个成员变量；看看分别是什么意思？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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; // 默认的负载因子（0.75）

  static final Entry<?,?>[] EMPTY_TABLE = {};

  transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE; // 真正存放数据的数组。

  transient int size; // `Map` 存放数量的大小。

  int threshold; // 桶大小，可在初始化时显式指定。

  final float loadFactor; // 负载因子，可在初始化时显式指定

桶数组给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量达到了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。

因此通常建议能提前预估 HashMap 的大小最好，尽量的减少扩容带来的性能损耗。

根据代码可以看到其实真正存放数据的是 table 数组：

1
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

这个数组，那么它又是如何定义的呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;

    /**
     * Creates new entry.
     */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }

Entry 是 HashMap 中的一个内部类，从他的成员变量很容易看出：

  • key 就是写入时的键。
  • value 自然就是值。
  • 开始的时候就提到 HashMap 是由数组和链表组成，所以这个 next 就是用于实现链表结构。
  • hash 存放的是当前key 的 hashcode。

知晓了基本结构，那来看看其中重要的写入、获取函数：

2. put方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}
  • 判断当前数组是否需要初始化。
  • 如果 key 为空，则 put 一个空值进去。
  • 根据 key 计算出 hashcode。
  • 根据计算出的 hashcode 定位出所在桶。
  • 如果桶是一个链表则需要遍历判断里面的 hashcode、key 是否和传入 key 相等，如果相等则进行覆盖，并返回原来的值。
  • 如果桶是空的，说明当前位置没有数据存入；新增一个 Entry 对象写入当前位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

当调用 addEntry 写入 Entry 时需要判断是否需要扩容。

如果需要就进行两倍扩充，并将当前的 key 重新 hash 并定位。

而在 createEntry 中会将当前位置的桶传入到新建的桶中，如果当前桶有值就会在位置形成链表。

3. 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
public V get(Object key) {
    if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);
  
    return null == entry ? null : entry.getValue();
}

final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }

    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}
  • 首先也是根据 key计算出 hashcode，然后定位到具体的桶中。
  • 判断该位置是否为链表。
  • 不是链表就根据 key、key 的 hashcode 是否相等来返回值。
  • 为链表则需要遍历直到 key 及 hashcode 相等时候就返回值。
  • 啥都没取到就直接返回 null 。

4. 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
void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {//最大容量为 1 << 30
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];//新建一个新表
    transfer(newTable, initHashSeedAsNeeded(newCapacity));//完成旧表到新表的转移
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

/**
 * Transfers all entries from current table to newTable.
 */
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;//引用next
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);//找到新表的桶位置;原桶数组中的某个桶上的同一链表中的Entry此刻可能被分散到不同的桶中去了，有效的缓解了哈希冲突。
            e.next = newTable[i];//头插法插入新表中
            newTable[i] = e;
            e = next;
        }
    }
}

这里很容易就想到多线程情况下，隐约感觉这个transfer方法在多线程环境下会乱套。事实上也是这样的，由于缺乏同步机制，当多个线程同时resize的时候，某个线程t所持有的引用next（参考上面代码next指向原桶数组中某个桶外挂单链表的下一个需要转移的Entry），可能已经被转移到了新桶数组中，那么最后该线程t实际上在对新的桶数组进行transfer操作。

如果有更多的线程出现这种情况，那很可能出现大量线程都在对新桶数组进行transfer，那么就会出现多个线程对同一链表无限进行链表反转的操作，极易造成死循环，数据丢失等等，因此HashMap不是线程安全的，考虑在多线程环境下使用并发工具包下的ConcurrentHashMap。

5. 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
/**
 * A randomizing value associated with this instance that is applied to
 * hash code of keys to make hash collisions harder to find. If 0 then
 * alternative hashing is disabled.
 */
transient int hashSeed = 0;

/**
 * 按需初始化哈希种子
 */
final boolean initHashSeedAsNeeded(int capacity) {
    // 如果hashSeed != 0，表示当前正在使用备用哈希
    boolean currentAltHashing = hashSeed != 0;
    // 如果vm启动了且map的容量大于阈值，使用备用哈希
    boolean useAltHashing = sun.misc.VM.isBooted() &&
            (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    // 异或操作，如果两值同时为false，或同时为true，都算是false。
    boolean switching = currentAltHashing ^ useAltHashing;
    if (switching) {
        // 把hashSeed设置成随机值
        hashSeed = useAltHashing
                ? sun.misc.Hashing.randomHashSeed(this)
                : 0;
    }
    return switching;
}

从hashSeed变量的注释可以看出，哈希种子一个随机值，在计算key的哈希码时会用到这个种子，目的是为了进一步减少哈希碰撞。如果hashSeed=0表示禁用备用哈希。

而Holder中维护的ALTERNATIVE_HASHING_THRESHOLD是触发启用备用哈希的阈值，该值表示，如果容器的容量（注意是容量，不是实际大小）达到了该值，容器应该启用备用哈希。

Holder会尝试读取JVM启动时传入的参数-Djdk.map.althashing.threshold并赋值给ALTERNATIVE_HASHING_THRESHOLD。它的值有如下含义：

  • ALTERNATIVE_HASHING_THRESHOLD = 1，总是使用备用哈希
  • ALTERNATIVE_HASHING_THRESHOLD = -1，禁用备用哈希

在initHashSeedAsNeeded(int capacity)方法中，会判断如果容器的容量>=ALTERNATIVE_HASHING_THRESHOLD，就会生成一个随机的哈希种子hashSeed，该种子会在put方法调用过程中的hash方法中使用到：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//这是一个神奇的函数，用了很多的异或，移位等运算，对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀
		final int hash(Object k) {
        int h = hashSeed;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }

        h ^= k.hashCode();

        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

		/**
     * 返回数组下标
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

解决的问题：不同的键的的hashcode仅仅只能通过低位来区分。高位的信息没有被充分利用。

HashMap它使用一个supplemental hash function对键的hashCode再进行了一个supplemental hash ，将最终的hash值作为键的hash值来进行桶的位置映射。这个过程叫做再哈希(rehash)。

经过一个supplemental hash过程后，能保证海明距离为常数的不同的hashcode有一个哈希冲突次数上界（装载因子为0.75的时候，大约是8次）。

JDK1.8 中的 HashMap

当 Hash 冲突严重时，在桶上形成的链表会变的越来越长，这样在查询时的效率就会越来越低；时间复杂度为 O(N)。

1. 数据结构

hashmap8

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
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30.
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

static final int TREEIFY_THRESHOLD = 8;
		
static final int UNTREEIFY_THRESHOLD = 6;

transient Node<K,V>[] table;

/**
 * Holds cached entrySet(). Note that AbstractMap fields are used
 * for keySet() and values().
 */
transient Set<Map.Entry<K,V>> entrySet;

/**
 * The number of key-value mappings contained in this map.
 */
transient int size;

和 1.7 大体上都差不多，还是有几个重要的区别：

  • TREEIFY_THRESHOLD 用于判断是否需要将链表转换为红黑树的阈值。
  • UNTREEIFY_THRESHOLD用于判断是否需要将红黑树转换为链表的阈值。
  • HashEntry 修改为 Node。

Node 的核心组成其实也是和 1.7 中的 HashEntry 一样，存放的都是 key value hashcode next 等数据。

2. 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
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)  // Step-1:初始化
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)  // Step-2：桶为空，直接新建桶
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k)))) // Step-3：与首节点相等
            e = p;
        else if (p instanceof TreeNode)  // Step-4：判断是树还是链表
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {  // Step-5：遍历链表
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  // Step-6：超过阈值转为rbt
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&  // Step-7：发现hash与key相等的节点
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key  // Step-8 赋值，并返回旧值
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)  // Step-9
        resize();
    afterNodeInsertion(evict);
    return null;
}

看似要比 1.7 的复杂，我们一步步拆解：

  1. 判断当前桶是否为空，空的就需要初始化（resize 中会判断是否进行初始化）。
  2. 根据当前 key 的 hashcode 定位到具体的桶中并判断是否为空，为空表明没有 Hash 冲突就直接在当前位置创建一个新桶即可。
  3. 如果当前桶有值（ Hash 冲突），那么就要比较当前桶中的 key、key 的hashcode 与写入的 key 是否相等，相等就赋值给 e,在第 8 步的时候会统一进行赋值及返回。
  4. 如果当前桶为红黑树，那就要按照红黑树的方式写入数据。
  5. 如果是个链表，就需要将当前的 key-value 封装成一个新节点写入到当前桶的后面（形成链表）。
  6. 接着判断当前链表的大小是否大于预设的阈值，大于时就要转换为红黑树。
  7. 如果在遍历过程中找到 key 相同时直接退出遍历。
  8. 如果 e != null 就相当于存在相同的 key，那就需要将值覆盖。
  9. 最后判断是否需要进行扩容。

链表转为红黑树的前提是整个数组的大小达到了64，如果没有达到，会先扩容。

3. 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

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;
}

get 方法看起来就要简单许多了。

  • 首先将 key hash 之后取得所定位的桶。
  • 如果桶为空则直接返回 null。
  • 否则判断桶的第一个位置(有可能是链表、红黑树)的key 是否为查询的 key，是就直接返回 value。
  • 如果第一个不匹配，则判断它的下一个是红黑树还是链表。
  • 红黑树就按照树的查找方式返回值。
  • 不然就按照链表的方式遍历匹配返回值。

从这两个核心方法（get/put）可以看出 1.8 中对大链表做了优化，修改为红黑树之后查询效率直接提高到了 O(logn)。

4. 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
final Node<K,V>[] resize() {
     //创建一个Node数组用于存放table中的元素，
     Node<K,V>[] oldTab = table;
     //获取旧table的长度
     int oldCap = (oldTab == null) ? 0 : oldTab.length;
     //获取旧的扩容阈值
     int oldThr = threshold;
     int newCap, newThr = 0;
     //如果旧的table中有元素
     if (oldCap > 0) {
         //如果旧table长度>=最大容量限制时不进行扩容，并将扩容阈值赋值为Integer.MAX_VALUE
         if (oldCap >= MAXIMUM_CAPACITY) {
             threshold = Integer.MAX_VALUE;
             return oldTab;
         }
         // 将新table长度赋值为旧table的2倍，
         // 判断旧table长度的二倍是否小于最大容量，且旧容量大于等于初始容量，
         // 以上判断成立则将新的扩容阀值赋值为旧的扩容阈值的二倍
         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                  oldCap >= DEFAULT_INITIAL_CAPACITY)
             newThr = oldThr << 1; // double threshold
     }
     else if (oldThr > 0) // initial capacity was placed in threshold
         newCap = oldThr;
     else {               // zero initial threshold signifies using defaults
         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"})
     //将旧table中的元素放到扩容后的newTable中
     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;
                 //如果数组对应下标位置只有一个元素，对hashCade取余并根据结果直接放到newTable相应的位置
                 if (e.next == null)
                     newTab[e.hash & (newCap - 1)] = e;
                     //如果数组对应下标位置的元素是一个红黑树,则拆分红黑树放到newTable中
                     // 如果拆分后的红黑树元素小于6，则转化为链表
                 else if (e instanceof TreeNode)
                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                 else { // preserve order
                 //数组对应下标位置的元素是一个链表的情况
                 //根据(e.hash & oldCap)条件对链表进行拆分并放到newTable
                     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;
                         }
                         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;
 }

5. hash函数

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

因为引入了红黑树，所以在hash这块进行了简化。

两个版本的HashMap的区别

HashMap 的实现在 JDK 1.7 和 JDK 1.8 差别较大，具体区别如下

JDK 1.8 的优化目的主要是：减少 Hash冲突 & 提高哈希表的存、取效率

数据结构

pic1

获取数据时（获取数据类似）

pic2

扩容机制

pic3

相关的疑问

JDK1.8为什么引入红黑🌲，而不选择其他的🌲？

红黑树既保证了插入效率，也保证了查询效率。

为什么容量必须为2的幂？

因为HashMap使用位运算来代替了取模运算（一个量级的差别），元素能够计算在0-15的范围内，必须要求数组长度为2的指数次幂。否则，有可能出现数组越界，以及大量的hash碰撞。

因为数组扩容，需要rehash，一旦数据量大，也就意味着性能瓶颈。所以采用位运算，也就对数组长度有要求。

扩容因子为什么定为0.75？

如果定为1，可能存在单个节点链表特别长，查询效率低。同时，hash碰撞会增多。

如果定为0.5，那么空间浪费太大了。

而0.75，是取的空间利用率和时间复杂度的均值来的，计算方法是利用牛顿二项式，结果为log2，取近似值0.75。