HashMap底层实现原理

发表于 | 分类于 ， ， | 阅读次数
字数统计 | 阅读时长
HashMap底层实现原理

HashMap初始化和元素的添加

       先来看看HashMap在Map中的位置：

HashMap在Map中的位置

       上图中，白色部分是接口，黄色部分是要重点了解的，绿色部分已经过时，不常用了，但是面试中可能会问到。先简单的说一下这几个Map，TreeMap是基于树的实现，HashMap，HashTable，ConcurrentHashMap是基于hash表的实现。HashTable和HashMap在代码实现上基本是一样的，和Vector与Arraylist的区别大体上差不多，一个是线程安全的，一个非线程安全，ConcurrentHashMap也是线程安全的，但性能比HashTable好很多，HashTable是锁整个Map对象，而ConcurrentHashMap是锁Map的部分结构。

Map的key和value

       Map其实很简单，就是一个key，对应一个value。看如下代码：

1
2
3
4
5
6
7
8
public static void main(String[] args) {
    List<Person> perList = new LinkedList<>();
    perList.add(new Person("张三", 21));
    perList.add(new Person("李四", 19));
    perList.add(new Person("王五", 25));
    perList.add(new Person("赵六", 24));
    System.out.println("perList.size()" + perList.size());
}

       构造函数如下：

1
2
3
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

       初始化了一个负载因子，默认为0.75f：

1
static final float DEFAULT_LOAD_FACTOR = 0.75f;

       同样有一个数组，数组里原对象是Node：

1
transient Node<K, V>[] table;

       看一下Node源码：

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

    Node(int var1, K var2, V var3, HashMap.Node<K, V> var4) {
        this.hash = var1;
        this.key = var2;
        this.value = var3;
        this.next = var4;
    }
    ...
}

       一个key，一个value，用来保存往Map里put的数据，next用来标记Node节点的下一个元素。有如下两个成员变量：

1
2
transient int size;
transient int modCount;

       一个是逻辑长度，一个是修改次数，ArrayList，LinkedList也有这两个属性，初始化如下图：

初始化HashMap

       HashMap初始化好了，成员变量table数组默认为null，size默认为0，负载因子为0.75f，初始化完成，往里添加元素，来看一下put的源码：

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

       调用了putVal方法，其中key是传进来的“张三”这个字符串对象，value是“张三”这个Person对象，调用了一个方法hash()，再看一下：

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

       key是基于hashCode来处理的。继续看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;//放入第一个元素时table为空，触发resize方法
    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)
                        treeifyBin(tab, hash);
                    break;
                    }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

       resize方法比较复杂，当放入第一个元素时，会触发resize方法的以下关键代码：

1
newCap = DEFAULT_INITIAL_CAPACITY;

       DEFAULT_INITIAL_CAPACITY如下：

1
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认初始容量 (必须是2的幂，用左移动)

       移位运算符，1 << 4 其实就是相当于16。

1
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];

       当放入第一个元素时，如果底层数组还是null，系统会初始化一个长度为16的Node数组，像ArrayList的初始化。最后返回new出来的数组，由于篇幅有限，下图中省略了部分数组内容，注意，虽然数组长度为16，但逻辑长度size依然是0：

HashMap底层实现原理

       继续执行putVal方法里的如下内容：

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

       上面代码和下面代码是等同的：

1
2
3
4
5
i = (n - 1) & hash;//hash是传过来的，其中n是底层数组的长度，用&运算符计算出i的值
p = tab[i];//用计算出来的i的值作为下标从数组中取元素
if(p == null){//如果这个元素为null，用key、value构造一个Node对象放入数组下标为i的位置
     tab[i] = newNode(hash, key, value, null);
}

       这个hash值是字符串“张三”这个对象的hashCode方法与hashMap提供hash()方法共同计算出来的结果，其中n是数组的长度，目前数组长度为16，不管这个hash的值是多少，经过(n - 1) & hash计算出来的i的值一定在n-1之间。刚好是底层数组的合法下标，用i这个下标值去底层数组里去取值，如果为null，创建一个Node放到数组下标为i的位置。这里的“张三”计算出来的i的值为2，如下图：

HashMap添加第一个元素

       继续添加元素“李四”、“王五”、“赵六”，一切正常，key：“李四”经过(n - 1) & hash算出来在数组下标位置为1，“王五”为7，“赵六”为9，添加完成后如下图：

HashMap里添加元素1

       上图更趋近于堆内存中的样子，但看起来比较复杂，简化一下：

HashMap里添加元素2

       上图是简化后的堆内存图。继续往里添加“孙七”，通过(n - 1) & hash计算“孙七”这个key时计算出来的下标值是1，而数组下标1这个位置目前已经被“李四”给占了，产生了冲突。看一看HashMap的putVal是怎么解决冲突的：

1
2
3
4
5
6
7
8
9
for (int binCount = 0; ; ++binCount) {
    if ((e = p.next) == null) {
        p.next = newNode(hash, key, value, null);
        if (binCount >= TREEIFY_THRESHOLD - 1)
            treeifyBin(tab, hash);
        break;
        }
    ...
}

       这一句是关键：

1
p.next = newNode(hash, key, value, null);

       也就是说new一个新的Node对象并把当前Node的next引用指向该对象，也就是说原来该位置上只有一个元素对象，现在转成了单向链表，如下图：

HashMap里添加元素3

       继续添加其它元素，添加完成后如下：

HashMap里添加元素4

       debug看一下：

debugHashMap里添加元素

       大框里的内容是链表的体现，小框里的内容是单元素的体现。还有两行比较重要的代码：

1
2
if (binCount >= TREEIFY_THRESHOLD - 1) //当binCount>=TREEIFY_THRESHOLD-1
      treeifyBin(tab, hash);//把链表转化为红黑树

       再看看TREEIFY_THRESHOLD的值：

1
static final int TREEIFY_THRESHOLD = 8;//（链表转树的阈值）

       当链表长度到8时，将链表转化为红黑树来处理，树在内存中的样子如下：

HashMap里的树

       在JDK1.7及以前的版本中，HashMap里是没有红黑树的实现的，在JDK1.8中加入了红黑树是为了防止哈希表碰撞攻击，当链表链长度为8时，及时转成红黑树，提高map的效率。

       先做一个小结：

  • HashMap的最底层是数组来实现的，数组里的元素可能为null，也有可能是单个对象，还有可能是单向链表或是红黑树。
  • resize在底层数组为null的时候会初始化一个数组，不为null的情况下会去扩容底层数组，并会重排底层数组里的元素。

HashMap元素的替换

       在Map中，一个key，对应了一个value，如果key的值已经存在，Map会直接替换value的内容，看以下代码：

1
2
3
4
5
6
Person oldPerson1 = personMap.put("张三", new Person("新张三", 21));
Person oldPerson2 = personMap.put("孙七", new Person("新孙七", 32));

System.out.println("oldPerson1.getName() ：" + oldPerson1.getName());
System.out.println("oldPerson2.getName() : " + oldPerson2.getName());
System.out.println("personMap.size() : " + personMap.size());

       new了一个Person“新张三”，注意，key依然是张三，将上面的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
43
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    ...

    //******************* 1 从底层数组取值
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    //*******************
    else {
        Node<K,V> e; K k;
        //******************* 2 底层数组元素匹配成功，赋值给e
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //******************* 3 如果是树，放到树中
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //******************* 4 如果底层数组元素第一个没有匹配上，循环链表，直到匹配成功为止
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                    }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))//这段代码和2一样
                    break;
                p = e;
            }
        }
        //******************* 5 用新的value替换旧的value并返回旧的value
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ...
}

       放入“新张三”时，会执行以上代码1、2、5。代码1中，由于p不为null，执行else里的逻辑。代码2中，key的值相等，条件成立，把值赋值给e。（如果key的值不相等，就比较equals方法，也就是说，就算key是一个新new出来的对象，只要满足equals，也视为key相同）。下面是代码5的解释：

1
2
3
4
5
6
7
if (e != null) {
    V oldValue = e.value;//定义一个变量来存旧值
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;//把value的值赋值为新的值
    afterNodeAccess(e);
    return oldValue;//返回的值
}

       上面代码用新的value替换旧value并返回旧的value。如下图：

HashMap里替换元素1

       再new一个Person“新孙七”并put到personMap中，注意，key依然是“孙七”，会执行putVal里的1、2、3、4、5，由于2、3不满足条件，实际执行的是1、4、5，重点说一下4：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (int binCount = 0; ; ++binCount) {//循环
    if ((e = p.next) == null) {//如果循环到最后也没找到，把元素放到最后
        p.next = newNode(hash, key, value, null);//把元素放到最后
        if (binCount >= TREEIFY_THRESHOLD - 1) //如果长度超>=8，转换成红黑树
            treeifyBin(tab, hash);//转换成红黑树
            break;
        }
        if (e.hash == hash && //这段代码和第2步一样
            ((k = e.key) == key || (key != null && key.equals(k))))
            break;
            p = e;//如果hash值相等，key也相等或者equals相等，赋值给e
        }
    }
}

       其实就是循环链表的节点，直到找到”孙七”这个key，然后执行putVal里的第5步，如果找不到，就添加到最后，这里我们key是“孙七”，在链表中找到元素替换value即可，如下图：

HashMap里替换元素2

       在hashMap中放入（put）元素，有以下重要步骤：

  1. 计算key的hash值，算出元素在底层数组中的下标位置；
  2. 通过下标位置定位到底层数组里的元素（也有可能是链表也有可能是树）；
  3. 取到元素，判断放入元素的key是否==或equals当前位置的key，成立则替换value值，返回旧值；
  4. 如果是树，循环树中的节点，判断放入元素的key是否==或equals节点的key，成立则替换树里的value，并返回旧值，不成立就添加到树里；
  5. 否则就顺着元素的链表结构循环节点，判断放入元素的key是否==或equals节点的key，成立则替换链表里value，并返回旧值，找不到就添加到链表的最后；

       精简一下，判断放入HashMap中的元素要不要替换当前节点的元素，key满足以下两个条件即可替换：

  1. hash值相等。
  2. ==或equals的结果为true。

       由于hash算法依赖于对象本身的hashCode方法，所以对于HashMap里的元素来说，hashCode方法与equals方法非常的重要，这也是在Java中的==与equals中强调重写对象的equals方法一定要重写hashCode方法的原因，不重写的话，放到HashMap中可能会得不到想要的结果。本示例中放入的key是String类型的，String这个类已经重写了hashCode方法。

参考资料：
清浅池塘 HashMap底层实现原理（上）、HashMap底层实现原理（下）

Fork me on GitHub