Java集合HashMap

发表于 | 分类于 ，

https://rainmonth.github.io/posts/J180320.html

前言

本文分析的代码对应的JDK版本为1.8，采用的IDE环境为IntellJ IDEA，注意本文不做细致分析，所以不会对源码细节做过多说明，而是指出使用HashMap前需要了解哪些方面的内容，可能会发生什么问题，细节可以自己参考JDK源码。

基本数据结构

数组和链表的结合，

  • 数组用来存放每个链表的头节点（数组的元素俗称桶（Bucket））；
  • 链表用来存放hash值相同的节点；（存放位置由key的hashCode值决定；

数组说明

  1. 长度大小需为2^n^(n为整数，n>= 0)（默认为16），至于为什么有这个要求，后面说明；
  2. 有一个关联的加载因子loadFactor（默认为0.75），默认的可用的桶为12个，由一个threshold变量记录；长度大于数组length * loadFactor 会重新resize；

元素如何添加进HashMap的

添加元素，采用put方法，put方法实现如下：

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

调用之前，先通过hash()方法获取hash值，hash函数如下：

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

这里是HashMap支持Key为空的关键，Key值为空时，其对应的hashCode被置为0，也就放在了数组的第一个元素。

内部调用putVal方法：

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)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            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))))
                e = p;
            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);
                        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;
    }

依据putVal()函数的源码，来说明为什么需要2^n^的长度，看putVal()代码片段

1
2
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

以默认的数组容量16为例，n-1=15，对应二进制为00001111，那么：

  • hash>15，位运算后结果为hash和（n-1)后面三维位运算的结果其实就是%运算
  • hash<=15，位运算结果为hash本身。

这应该就是数组长度要求2^n^的原因，方便进行位运算（用空间换时间）

为什么说HashMap不是线程安全的

因为多线程都rehash时，可能会导致循环链表的形成，可能形成条件竞争。

为什么推荐使用String、Integer这样的类作为Key

因为这些类的对象是不可变的，也是final的，并且都自己实现了hashCode和equals方法，这就保证了同一个对象其HashCode不会发生改变，减少了hash碰撞发生的几率，可以提高HashMap的性能。

hash碰撞

当向HashMap中添加对象时，如果两次K对应的hashCode相同，就会发生hash碰撞，发生hash碰撞后，可能会发生如下操作：

  • 两次的hashCode相同，但K值不相等（调用equals()判断），就将后加入的添加到先加入的的尾部；
  • 两次hashCode相同，且K值相等（调用equals()判断），后加入的就取而代之。

顺便谈谈LinkedHashMap

LinkedHashMap其实就是HashMap和双向链表的综合体，其中：

  • 通过继承HashMap，保留了HashMap的特点
  • 通过双向链表，实现了功能的扩展（解决了HashMap不能保证有序的问题）
    • 可以记录插入顺序（默认）
    • 可以记录访问顺序， 重写removeEldestEntry(Map.Entry<K,V> eldest)方法还可以很好的实现LRU算法

有序性原理

在调用put和get方法时会分别调用afterNodeInsertion afterNodeAccess方法，这两个方法起着记录相关顺序的作用（插入顺序和访问顺序），本质上就是双向链表的操作。然后，就是通过重写迭代器将LinkedHashMap中的所有Entry按照记录的顺序迭代输出，所以迭代器的重写是关键