HashMap扩容机制，put()，get()和源码分析全都有，让你不再怕HashMap的面试题

HashMap扩容机制，put()，get()和源码分析全都有，让你不再怕HashMap的面试题

今天抽时间来把HashMap源码来给大家分享下，好久没和大家分享技术知识点了，手速和脑速感觉都有点跟不上了，今天就简单的和大家来分享下HashMap源码；记住哦，直接分享源码，可能会比较枯燥，比较乏味，但是干货和知识点还是非常多，收益将会大大滴，来吧，老规矩，废话少说，撸起袖子，直接上干货，开干！

1、HashMap简介

java在数据结构中映射接口中定义了一个java.util.Map接口，Map接口主要有四个实现类，分别是HashMap、linkedHashMap、HashTable和TreeMap，它们之间关系如下图所示：

1.1、下面来简单介绍下HashMap、HashTable、linkedHashMap和TreeMap各自特点

1、HashMap：HashMap作为Map中最为常用的一种，它是根据键的hashcode值对数组长度取模来存储数据；一般情况下可以直接定位到所要查找的值，因此查找速度非常快，但遍历的数据顺序不一定；HashMap存储的键只允许有一条为null，但是记录的值允许多条为null，且存储的键必须唯一，不可重复；HashMap非线程安全，即任意时刻允许多个线程同时写HashMap，可能出现数据不一致问题，如果需要使用线程安全的话，则可以使用Collections.synchronizedMap()方法或者使用ConcurrentHashMap。

2、HashTable：HashTable很多功能与HashMap功能相似，在代码编写中几乎不怎么使用HashTable，它是线程安全的，为了线程安全问题，它只能抛弃查找效率问题，查找效率比较慢；并发性不如ConcurrentHashMap，因为ConcurentHashMap采用分段锁去保证其安全性。建议：在不需要线程安全性问题时，使用HashMap，在需要线程安全性问题时，使用ConcurrentHashMap。

3、linkedHashMap：linkedHashMap继承了HashMap，换言之HashMap是其父类，它保存了记录插入顺序在使用迭代器iterator遍历时，输出的顺序就是插入的顺序。

4、TreeMap：TreeMap实现SortedMap接口，可以把保存的记录的key进行排序，其默认是key的升序进行排列，当然也可以使用自定义的排序器进行排序，当使用iterator遍历时，得到的顺序是已经排过序的；使用TreeMap时，key必须是实现compareTo接口，否则会报不知道如何排序异常，这点注意。

四个类对比：

类名安全性顺序问题HashMap不安全无序HashTable安全无序linkedHashMap不安全有序（记录添加顺序）TreeMap不安全有序（key进行排序）

注意：key值唯一，且最多只有一个为null，但是value可以有多个null值。

在以上四种类中，HashMap使用频率最高，因此在接下来中我将围绕HashMap源码来深入讲解HashMap存储结构、常用方法、扩容和安全性。

2、内部实现

为了弄清HashMap，首先要知道HashMap是什么？也就是它的存储结构，其次要知道它能做什么？也不是它的功能实现。

2.1、存储结构

从结构上来进行分析，HashMap就是数组+链表+红黑树来实现的（jdk1.8版本）。

PS：jdk1.8的时候引进红黑树，以前版本就是数组+链表。

存储结构如下图所示：

看了上图，我们要思考两个问题：1、数据底层到底存储的是什么？2、这样存储有什么优点？

1）从jdk源码中得知，HashMap有个非常重要的手段，就是Node[] table，即哈希桶数组，下面我们来看下源码：

Node是HashMap的一个内部类，其实现了Map.Entry接口，本质就是一个映射（键值对），上图中的每一个五角星就是代表一个Node对象。

2）、HashMap就是使用哈希表来进行存储；哈希表为了解决哈希冲突，可以采用开放地址法或者链地址法，java中的HashMap就是采用后者链地址法来解决哈希冲突。链地址法就是采用数组+链表的形式，当添加的元素算出hsah后，就会将该数据放到对应的数组下表元素后面的对应的链表上。例如下面代码；

Map map = new HashMap<>();
map.put("china","中国");

先将key值china计算出该hashcode值，然后再通过hash算法的后两步高位运算和取模运算来定位该key值应该存放数组位置，如果该数组位置已经存放了其他元素，也就是不为空，那么此时就是发生了哈希碰撞；hash算法越好，计算出结果越均匀，发生哈希碰撞概率越小，Map的存取效率越高；否则相反。

如果哈希桶数组很大，那么即使较差的hash算法也会分散比较均匀；否则哈希桶数组较小，那么较好的hash算法也会发生多次hash碰撞，因此就需要时间和空间成本之间权衡，其实就是根据实际情况来决定哈希桶数组大小，并拥有较好的hash算法来减少哈希碰撞。拥有较好的Hash算法和扩容机制，那么能够来降低Map的hash碰撞，且减少哈希桶数组占用内存。

我们先来看下HashMap源码中部分重要属性字段：

1、Capacity数组长度：HashMap中Node[] table初始化长度为16，哈希桶数组的长度必须为2的n次方，之所以这样设计是为了在取模和扩容时做了优化（提高计算index索引效率），同时为了减少冲突，HashMap定位哈希桶索引位置时，也加入了高位参与的过程。

2、loadFactor：负载因子，默认值为0.75，0.75是对时间和空间效率的一个平衡选择，建议大家一般不要修改，除非在特殊情况下，比如在时间与空间特殊情况下。比如对内存空间很多，对时间要求效率高，那么可以选择降低加载因子；相反对内存空间少，时间效率没有太大要求，那么可以增大加载因子。

3、threshold：阈值，这个我们暂且叫它阈值，它的值为table数组长度 * 加载因子 (threshold = capacity * loadFactor)，当插入到Node[]元素个数大于该阈值时，那么HashMap将调用resize()方法扩容，扩容后的HashMap是是原来容量的2倍，注意哈，我这里说的版本是jdk1.8的，1.8之前的版本可不是以这种方式进行扩容。

4、size：是HashMap中实际存在的键值对数量，注意：Node[] table数组长度为capacity，容纳最大键值对阈值threshold区别。

5、modCount：用来记录HashMap内部结构发生变化次数，注意：内部结构发生变化是指内部结构，例如当put一个新键值对时是结构发生变化；当更改一个已经存在的key所对应value值时，那么不称为结构发生改变，这点要注意。

6、 TREEIFY_THRESHOLD 和 MIN_TREEIFY_THRESHOLD：即使hash算法和负载因子设计的再好，也避免不了链表过长的问题，那就导致效率变慢，影响HashMap性能，于是在JDK1.8时引入了红黑树，来增加HashMap性能；当链表长度大于TREEIFY_THRESHOL（TREEIFY_THRESHOL值为8），且Node[] table数组长度大于MIN_TREEIFY_THRESHOLD（MIN_TREEIFY_THRESHOLD为64）时，将会触发链表转化为红黑树。利用红黑树快速增删改查的特点来增加HashMap性能。注意：触发链表转换红黑树机制条件必须满足两个，链表长度大于8且Node[] table数组长度大于64，两者缺一不可。

2.2、构造方法源码分析

接下来我列出构造函数方法：

1、无参构造

无参构造时只是将默认加载因子赋值给该加载因子。

2、有参构造——只传Node[] table数组长度

3、有参构造——传值Node[] table数组长度initialCapacity，和加载因子。

PS：注意第2个和第3个有参构造中tableSizeFor(initialCapacity)方法，该方法你无论传何种数值，那么都会将数组长度变为最近的2^n 次方；简言之该方法根据容量计算出扩容的临界值，比如容量是3，3<2^2 =4，所以临界值是2^2 =4，再比如容量是60，60<2^6=64，所以临界值是64。

4、有参构造——传值为Map对象

2.3、功能实现-方法

在接下来的文章中将主要围绕根据key获取哈希桶数组索引位置、put、get等方法和HashMap如何扩容来进行深入讲解。

2.3.1、确定哈希桶数组（table）索引位置

增加、删除和查找键值对需要定位到哈希桶数组索引位置，这是非常关键的一步，HashMap的数据存储是数组+链表的方式来进行存储，因此我们希望HashMap里的元素尽量分布均匀些，使得每个哈希桶数组上只有一个元素，那么当我们在定位键值对的时候，直接知道该元素所在哈希桶索引位置即可，不需要进行去遍历链表，那么这样查询效率大大的提高了。HashMap定位数组索引位置，直接决定hash方法的离散性能。下面我来分析下定位哈希桶数组位置的源码：

注意哈，这个只计算出key的hash值，还没有定位key所在的哈希桶数组位置。定位Key所在哈希桶位置在1.8之前通过indexFor()方法，但是1.8版本的时候删除了该方法，该方法的功能在其它方法完善了。比如put()方法，部分源码如下：

我这里拿1.7版本来列出完整的定位哈希桶数组位置的三步，第一步：对key进行hash运算，取出hashCode值；第二步：对hashCode高位运算；第三步：取模运算。源码如下：

static final hash(Object key){
    int h;
    // h = key.hashCode() 第一步：取hashCode值
    // h ^ (h >>> 16) 第二步：高位运算
    return (key == null ? 0 :(h = key.hashCode()) ^ (h >>> 16));
}

//注意，该方法是1.7版本的，在1.8版本中，该方法已经舍弃
static int indexFor(int h, int length){ //第三步：取模运算
    return h & (length-1);
}

这里的第三步取模运算设计方法是非常巧妙的，取模运算本来是非常消耗性能的，但是HashMap中运用hash & (length - 1)来获得该对象在哈希桶数组中所在位置，而HashMap底层数组长度总是2的n次方（这里即使你在创建HashMap的时候给定长度不是2的n次方，但是在底层源码中会将长度更改成2的n次方），当length是2的n次方的时候，h & (length-1)的结果是等于h%length（对length取模运算），&运算要比%运算有更高的效率。

2.3.2、put()方法

put()方法这里就直接给大家讲解源码吧，直接在源码注解中进行讲解。

put()方法源码：

public V put(K key, V value) {
    //hash(key)：计算出key的hash值
    return putVal(hash(key), key, value, false, true);
}

putVal()方法源码：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        //如果table的数组为空，那么直接进行resize()扩容
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
    
       //计算出该元素要插入到table数组的位置，且该位置为null，没有插入任何元素
        if ((p = tab[i = (n - 1) & hash]) == null)
            //该下标位置没有对象，直接创建新Node()
            tab[i] = newNode(hash, key, value, null);
    	
        else {
            Node e; K k;
            //table要插入位置中，该key存在，那么直接将该key的value值进行替换为新的value
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //红黑树处理
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
            //链表处理
            else {
                //遍历链表
                for (int binCount = 0; ; ++binCount) {
                    //下一个节点是否为null
                    if ((e = p.next) == null) {
                        //直接创建新node节点
                        p.next = newNode(hash, key, value, null);
                        //如果链表长度大于8
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //执行红黑树处理逻辑
                            treeifyBin(tab, hash);
                        break;
                    }
                    //链表中已经存在该key的节点，那么结束循环，返回该节点
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    //指向下一节点
                    p = e;
                }
            }
            //覆盖存在key的值
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                //返回旧的value值
                return oldValue;
            }
        }
    	//map被修改次数，注意是结构更改才会+1，也就是新增才会+1
        ++modCount;
    	//键值对个数大于阈值，进行resize()扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

下面我来给大家展示下put方法逻辑展示图：

2.3.3、get()方法

在使用HashMap中除了使用比较多put()方法之外就是常用的get()方法，下面我来给大家讲解下get()方法源码：

get()方法：

getNode()方法：

2.3.4、HashMap扩容机制

HashMap扩容(resize)就是重新计算HashMap的容量，向HashMap中源源不断的添加元素，当HashMap内部内部数组中无法承受其数组对象时，那么就会对其扩容。

触发扩容机制有三个条件：

1、当往HashMap中添加第一个元素时，HashMap的table数组为空，那么将会触发扩容机制。如果是空构造，不传容量大小，那么将会使用默认容量大小(DEFAULT_INITIAL_CAPACITY = 16)，如果在构造时指定了HashMap长度，如果指定长度是2的n次幂，那么其长度就是指定的长度；如果不是2的n次幂，那么会将长度更改为比它大的最近的2的n次幂。

2、当HashMap中对象超过起阈值(threshold = 容量 * 加载因子)，将会触发扩容机制。

3、当链表长度 > 8 时，且HashMap的table数组 < 64，那么就会触发扩容机制。

在HashMap扩展中有个最重要的问题，就是扩展后原来对象如何存放进扩展后的HashMap中。

在jdk1.7的时候，采用的是当扩展后将重新计算存放的索引位置，且总是将元素放进头部，也就是头插法。

下面举个例子说明扩容的过程，假设了我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。其中的哈希桶数组table的size=2， 所以key = 3、7、5，put顺序依次为 5、7、3。在mod 2以后都冲突在table[1]这里了。这里假设负载因子 loadFactor=1，即当键值对的实际大小size 大于 table的实际大小时进行扩容。接下来的三个步骤是哈希桶数组 resize成4，然后所有的Node重新rehash的过程。

在1.8版本中对其进行改进，经过检测发现，因为HashMap每次扩展是2的n次幂，那么原来元素的要么存放在原位置中，要么在原位置上再移动2的n次幂位置，看下图就明白了。

因为在重新计算hash之后，因为n变为了原来2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

这个设计非常的巧妙，即省去了重新计算hash值的时间，而且同时，由于新增的 1 bit 是0还是1可以认为是随机的，因此 resize 的过程，均匀的把之前的冲突的节点分散到新的 bucket 了，这就是JDK1.8新增的优化点。

总结：

1、扩容是个非常消耗性能的 *** 作，所以在构造HashMap的时候要正确给出一个大小值，避免经常进行扩容，这样能减小内存开销。

2、HashMap是非线程安全的。在并发情况下建议使用ConcurrentHashMap，它是分段锁。

3、jdk1.8中引入了红黑树，大大增加了其性能。

4、当链表大于8时，并不是直接转换成红黑树，它只有将table的长度大于64时才会进行转换成红黑树，否则将触发扩容机制，转换成原来长度的2倍，这个要非常注意。

好了，今天的分享就到此结束吧，这篇文章写了好久好久，可把我恶心死了，如有哪些不懂的地方或者那里有错的，希望大家给我指出，好了，我们下期见，拜拜。