HashMap底层原理源码

HashMap底层原理源码

简介

HashMap是基于哈希表的Map接口的实现，是以key-value存储形式存在，即主要用来存放键值对，HashMap的实现不是同步的，这也就意味着它不是线程安全的。它的key、value值都可以为null。此外，HashMap中的映射不是有序的

JDK1.8之前的HashMap是由数组+链表组成的，数组是HashMap的主体，链表则主要是为了解决哈希冲突(两个对象调用的HashCode方法计算的哈希码表一直导致计算的索引值相同)而存在的（拉链法解决冲突）。JDK1.8之后在解决哈希冲突有很大的变化，当链表长度大于阙值（或者红黑树的边界值，默认为8）并且当前的数组长度大于64时，此时索引位置上的所有数据改为使用红黑树存储
PS：将链表转化为红黑树会判断，即使阙值大于8，若数组的长度小于64，则不会将链表转化为红黑树，而是进行数组扩容

当创建HashMap集合对象的时候，再jdk8之前，构造方法中创建一个长度为16的Entry[] table用来存储键值对数据。再jdk8之后就不是HashMap的构造方法底层创建数组，是在第一次调用put方法时创建的数组，Node[] table用来存储键值对的

源码解析

部分常量

1、成员变量DEFAULT_INITIAL_CAPACITY，那句英语翻译过来就是默认的初始容量-必须是2的幂，默认初始容量是16，1<<4相当于1*(2的四次方)

2.创建集合时指定的容器初始量不为2的n次幂，结果如何了？
如果初始容量<0,则抛出异常
如果初始容量大于常数MAXIMUM_CAPACITY，则初始容量为MAXIMUM_CAPACITY
loadFactor表示的时负载因子,如果负载因子<=0或者loadFactor不是loadFactor（isNaN方法）则也会抛出异常

进入方法tableSizeFor()方法,可以看到，在实例化中，如果给定了initialCapacity，由于HashMap的capacity必须是2的二次幂，因此这个方法用于找到>=initialCapacity的最小的二次幂(initialCapacity)如果就是2的二次幂，返回的就是这个数

1、解释下为什么cap要减1
这是为了防止cap已经是2的二次幂，在执行以下操作，最后就返回的就是cap的两倍。如果这时n为0，经过n-1后变成了-1，经过以下操作后就变成了0，最后返回的就是1
2、|（按位或运算）：运算规则:相同的二进制数位上，都是0的时候，结果为0，否则为1，简单示例下计算过程

3、负载因子

4、当链表的值超过8才会转化为红黑树

5、当桶上的节点数小于6时就从红黑树转变为链表

6、用来调整大小下一个容量的值计算方式为(容量乘以加载因子)
临界值 当实际大小(容量*加载因子)超过临界值时就会进行扩容

PS：

构造方法

1、无参构造方法
默认初始容量为16，加载因子是0.75

2、指定初始容量的构造方法
默认加载因子是0.75，如果初始化容量是负数则抛出异常

3、指定初始化容量和加载因子构造方法

4、包含另一个Map的构造函数

这里用到了putMapEntries方法，可以看一下

增加方法

就一个put方法，但有点复杂，一个个来解析

先不急着看putVal方法，先看hash方法，看是怎么计算哈希值的
可以看到hash方法首先会判断key是否为null，若key为null则赋值哈希值为0（这也间接回答了HashMap的key可以为null的情况)。若key不为null，则会先计算出key类型的hashCode方法计算出哈希值，然后赋值给key，最后在与h无符号右移16位后的二进制进行按位异或计算的到最后的哈希值(^是java中的与或运算符)

现在来看putVal方法


resize()方法是初始化并扩容
treeifyBin()：将链表转换成二叉树

/**
        * 添加键值对到HashMap中
        *
        * @param hash         key所对应的哈希值
        * @param key          键值对中的键（key）
        * @param value        键值对中的值（value）
        * @param onlyIfAbsent 如果存在相同的值，是否替换已有的值，true表示替换，false表示不替换
        * @param evict        表是否在创建模式，如果为false，则表是在创建模式
        * @return 返回旧值或者null
    */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        HashMap.Node<K, V>[] tab;
        HashMap.Node<K, V> p;
        int n, i;
        //检查数组table是否为空或者长度是否为0
        if ((tab = table) == null || (n = tab.length) == 0)
            //如果为空，则初始化并扩容,然后返回新链表的数组长度,将长度赋值给n
            n = (tab = resize()).length;
        //(n-1)&hash这条语句就是得到该对象存放在数组中的索引
        if ((p = tab[i = (n - 1) & hash]) == null)
            //若该位置没数据就添加元素节点,该节点是链表的头节点
            tab[i] = newNode(hash, key, value, null);
        else {
            //若该位置有数据,就发生哈希冲突
            HashMap.Node<K, V> e;
            K k;
            //判断待添加的元素的hash值和key值是否同已经冲突的元素的hash值和key值同时相同
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                //如果相等表示两个元素重复了,就用变量e来临时存储这个重复元素
                e = p;
                //如果不相同，说明没重复，并且判断p是否是树节点
            else if (p instanceof HashMap.TreeNode)
                //如果是树节点，就将该键值对存储到树节点
                e = ((HashMap.TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
                //不相等且节点类型不是树，那么就是链表，用拉链法解决哈希冲突
            else {
                // 遍历链表中所有结点，这是一个死循环，需要通过break跳出循环
                for (int binCount = 0; ; ++binCount) {
                    //如果p的下一个节点位置为null
                    if ((e = p.next) == null) {
                        //就新建一个节点连接再p的后面
                        p.next = newNode(hash, key, value, null);
                        //binCount还可以作为计数器，计算有多少节点了
                        //TREEIFY_THRESHOLD常量，表示阙值，值为8
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //binCount如果超过了8，就组键红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
                    //还在for循环中
                    //判断待添加元素的hash值和key值是否同链表中已有元素的hash值和key值同时相等
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        //相同就退出循环
                        break;
                    //将下一个节点赋值给当前节点，继续往下遍历链表
                    p = e;
                }
            }
            //如果e不为空，说明存在重复值，即存在hash值和key值相等的元素
            if (e != null) { // existing mapping for key
                //保存旧值
                V oldValue = e.value;
                //然后替换为新值
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                // 此函数会将链表中最近使用的Node节点放到链表末端，因为未使用的节点下次使用的概率较低
                afterNodeAccess(e);
                //返回旧值
                return oldValue;
            }
        }
        // 记录修改次数
        ++modCount;
        // 如果添加元素后，超过阈值
        if (++size > threshold)
            // 则对HashMap进行扩容
            resize();
        // 给LinkedHashMap使用
        afterNodeInsertion(evict);
        return null;
    }
}
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

将链表转红黑树treeifyBin()方法

/**
*Replaces all linked nodes in bin at index for given hash unless 
*table is too small, in which case resizes instead.
*替换指定的哈希表的索引处桶中的所有连接节点，除非链表太小，否则将修改大小
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        /**
        *如果当前数组为空或者数组长度小于树形化的阙值(MIN_TREEIFY_CAPACITY=64)
        *就去扩容，而不是将节点转化为红黑树
        *目的,如果数组很小,那么遍历效率就会低一些.这时进行扩容,那么重新计算哈希表
        *链表长度可能就变短了，数据就会放在数组中，这样效率就高一些
        */
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        //扩容方法
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
        //这里进行树形化
        //hd红黑树头节点,tl红黑树尾节点
            TreeNode<K,V> hd = null, tl = null;
            do {
            //新建一个节点，内容与当前链表值一致
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                //将新创建的p节点赋值给头节点
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
                //e=e.next将当前的下一个节点赋值给e。如果下一个节点不为null
                //则返回到上面继续取出红黑树节点
            } while ((e = e.next) != null);
            //让桶中的第一个元素即数组中元素指向新建的红黑树节点，
            //以后这个桶里的元素就是红黑树，而不是链表数据结构了
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }
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

该方法做了以下几件事
1、根据哈希表中元素个数确定是扩容还是树形化
2、如果是树形化遍历桶中的元素，创建相同的个数的树节点，复制内容，建立起联系
3、然后让桶中的第一个元素指向新创建的根节点，替换桶的链表内容为树形内容

扩容方法

当HashMap的元素个数超过数组大小(数组长度)*loadFactor(负载因子)时,就会进行扩容
扩容也是乘以2

HashMap和HahsTable的区别

二者都是基于哈希表实现的key-value结构的集合

• HashTable是JDK1.0引入的线程安全型的集合，因为HashTable所有数据访问的方法都加入了synchronizied的同步锁，HashTable数据结构用的是数据+链表，链表用来解决哈希表的哈希冲突的问题
• HashMap是JDK1.2引入的线程不安全的集合类。再JDK1.8之前底层数据结果都是使用数组+链表的方式，再JDK1.8版本之后底层数据结构则变成了数组+链表+红黑树。只有数组长度大于64，且链表的阙值大于8，就会把链表转化为红黑树，提升数据查找的性能
• HashMap默认的容量大小是16；扩容时，每次将容量变为“原始容量x2”。
  Hashtable默认的容量大小是11；增加容量时，每次将容量变为“原始容量x2 + 1”。
• HashMap可以使用null作为键值，因为HashMap会将null转化为0进行存储，但这样的键值只能有一个。而HashTable则不允许
• 两个散列值计算不相同，HahsTable直接使用key的HashCode对数组长度做取模，而HahsMap则是对HashCode做了二次散列，从而避免key的分布不均匀的问题影响到查询性能
• 继承父类不同，但都实现了Map接口。 HashMap继承AbstractMap实现Map接口；Hashtable继承Dictionary实现Map接口