1 前言

该文章的内容是建立在读者对HashMap有初步了解的基础上的

HashMap中有很多知识点，比如哈希表、位运算、链表、红黑树等，HashMap 的源码也是很值得大家去学习的

2 哈希表

在讲源码之前首先了解一下什么是哈希表

Hash表也称为散列表，也有直接译作哈希表，Hash表是一种根据关键码值（key-value）而直接进行访问的数据结构。也就是说它通过把关键码值映射到表中的一个位置来访问记录，以此来加快查找的速度。

这个映射函数叫做

散列函数

，存放记录的数组叫做

散列表

。在链表、数组等数据结构中，查找某个关键字，通常要遍历整个数据结构，也就是O(N)的时间级，但是对于哈希表来说，只是O(1)的时间级。

Java集合源码解析之——HashMap1 前言2 哈希表3 HashMap4 字段属性5 构造函数6 扩容机制7 JDK1.8中扩容机制改进8 JDK1.8中hash()改进

① 存放在哈希表中的数据是

key-value键值对

，比如存放哈希表的数据为:

{Key1-Value1, Key2-Value2, Key3-Value3, Key4-Value4, Key5-Value5}
如果我们想查找是否存在键值对 Key3-Value3，首先通过 Key3 经过散列函数，得到值 k3，然后通过 k3 和散列表对应的值找到是 Value3。

② 当然也有可能存放哈希表的值只是 Value1,Value2,Value3这种类型：

{Value1, Value2, Value3, Value4, Value5}
这时候我们可以假设 Value1 是等于 Key1的，也就是{Value1-Value1, Value2-Value2, Value3-Value3, Value4-Value4, Value5-Value5}可以将 Value1经过散列函数转换成与散列表对应的值。

为了更好地理解Hash表，我们以汉语词典为例

汉语字典的优点是我们可以通过前面的拼音目录快速定位到所要查找的汉字。当给定我们某个汉字时，大脑会自动将汉字转换成拼音（如果我们认识，不认识可以通过偏旁部首），这个转换的过程我们可以看成是一个散列函数，之后在根据转换得到的拼音找到该字所在的页码，从而找到该汉字。

汉语字典是哈希表的典型实现，但是我们仔细思考，会发现如果多个 key 通过散列函数会得到相同的值，这时候怎么办？

对于这个问题，多个 key 通过散列函数得到相同的值，这其实也是哈希表最大的问题——

冲突

。

如何解决这个问题，我们先来看看汉语字典的方法：

① 开放地址法 。 当遇到冲突，此时通过另一种函数再计算一遍，得到相应的映射关系 。比如对于汉语字典，一个字 “余”，拼音是“yu”，我们将其放在页码为567(假设在该位置)，这时候又来了一个汉字“于”，拼音也是“yu”，那么这时候我们要是按照转换规则，也得将其放在页码为567的位置，但是我们发现这个页码已经被占用了，这时候怎么办？我们可以在通过另一种函数，得到的值加1。那么汉字"于"就会被放在576+1=577的位置。
② 链地址法 。 当遇到冲突，直接往当前冲突位置的子数组或者子链表里面填充即可 。比如对于汉语字典，我们可以将字典的每一页都看成是一个子数组或者子链表，当遇到冲突了，直接往当前页码的子数组或者子链表里面填充即可。那么我们进行同音字查找的时候，可能需要遍历其子数组或者子链表。如下图所示：

Java集合源码解析之——HashMap1 前言2 哈希表3 HashMap4 字段属性5 构造函数6 扩容机制7 JDK1.8中扩容机制改进8 JDK1.8中hash()改进

对于开放地址法，可能会遇到二次冲突，三次冲突，所以需要良好的散列函数，分布的越均匀越好。

对于链地址法，虽然不会造成二次冲突，但是如果一次冲突很多，那么会造成子数组或者子链表很长，那么我们查找所需遍历的时间也会很长。

3 HashMap

顾名思义，HashMap 是一个利用哈希表原理来存储元素的集合。遇到冲突时，HashMap 是采用的链地址法来解决。

3.1 HashMap定义

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射，而且 key 和 value 都可以为 null。

java.util.HashMap 继承 AbstractMap 抽象类，同时实现 Map、 Cloneable、 Serializable 接口

public class HashMap<K,V> extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable { 
            //... 
        }

3.2 关于实现 Map 接口

Map 接口定义了一组键值对映射通用的操作。储存一组成对的键-值对象，提供key（键）到value（值）的映射，Map中的key不要求有序，不允许重复。value同样不要求有序，但可以重复。

但是我们发现该接口方法有很多，我们设计某个键值对的集合有时候并不像实现那么多方法，那该怎么办？

JDK 还为我们提供了一个抽象类 AbstractMap ，该抽象类继承 Map 接口，所以如果我们不想实现所有的 Map 接口方法，就可以选择继承抽象类 AbstractMap 。

但是我们发现 HashMap 类即继承了 AbstractMap 接口，也实现了 Map 接口，这样做难道不是多此一举？LinkedHashSet 集合也有这样的写法。
据 java 集合框架的创始人Josh Bloch描述，这样的写法是一个失误。在java集合框架中，类似这样的写法很多，最开始写java集合框架的时候，他认为这样写，在某些地方可能是有价值的，直到他意识到错了。显然的，JDK的维护者，后来不认为这个小小的失误值得去修改，所以就这样存在下来了。

3.3 关于实现Cloneable 及 Serializable 接口

HashMap 集合还实现了 Cloneable 接口以及 Serializable 接口，分别用来进行对象克隆以及将对象进行序列化。

4 字段属性

//序列化和反序列化时，通过该字段进行版本一致性验证
private static final long serialVersionUID = 362498820763181265L;

//默认 HashMap 集合初始容量为16（必须是 2 的倍数）
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;

//当桶(bucket)上的结点数大于这个值时会转成红黑树(JDK1.8新增)
static final int TREEIFY_THRESHOLD = 8;

//当桶(bucket)上的节点数小于这个值时会转成链表(JDK1.8新增)
static final int UNTREEIFY_THRESHOLD = 6;

//(JDK1.8新增)当集合中的容量大于这个值时，表中的桶才能进行树形化 ，否则桶内元素太多时会扩容，而不是树形化,
//为了避免进行扩容、树形化选择的冲突，这个值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;

//初始化使用，长度总是2的幂
transient Node<K,V>[] table;

//保存缓存的entrySet()
transient Set<Map.Entry<K,V>> entrySet;

//此映射中包含的键值映射的数量。（集合存储键值对的数量）
transient int size;

//跟前面ArrayList和LinkedList集合中的字段modCount一样，记录集合被修改的次数
//主要用于迭代器中的快速失败
transient int modCount;

//调整大小的下一个大小值（容量*加载因子）。capacity * loadfactor
int threshold;

//散列表的加载因子
final float loadFactor;

4.1 字段属性讲解

①

Node<K,V>[ ] table

HashMap 是由数组+链表+红黑树组成，这里的数组就是 table 字段。后面对其进行初始化长度默认是 DEFAULT_INITIAL_CAPACITY= 16。而且 JDK 声明数组的长度总是 2的n次方(一定是合数)，为什么这里要求是合数，一般哈希算法为了避免冲突都要求长度是质数，这里为什么要求是合数，下面在介绍 HashMap 的hashCode() 方法(散列函数)，再进行讲解。

②

size

集合中存放key-value 的实时对数。

③

loadFactor

装载因子，是用来衡量 HashMap 满的程度，计算HashMap的实时装载因子的方法为：size/capacity，而不是占用桶的数量去除以capacity。capacity 是桶的总数，也就是 table 的长度length。

④

threshold

计算公式：capacity * loadFactor。这个值是当前已占用数组长度的最大值。过这个数目就重新resize(扩容)，扩容后的 HashMap 容量是之前容量的两倍

5 构造函数

① 默认无参构造函数

//默认构造函数，初始化加载因子loadFactor = 0.75
public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; 
    }

② 指定初始容量的构造函数

public HashMap(int initialCapacity, float loadFactor) {
        //初始化容量不能小于 0 ，否则抛出异常
        if (initialCapacity < 0) 
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);

        //如果初始化容量大于2的30次方，则初始化容量都为2的30次方
        if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY;

        //如果加载因子小于0，或者加载因子是一个非数值，抛出异常
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);

        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
}

//返回大于等于initialCapacity的最小的二次幂数值
//>>> 操作符表示无符号右移，高位取0
//| 按位或运算
static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

6 扩容机制

JDK1.7使用数组+链表；JDK1.8使用数组+链表+红黑树。

链表长度大于8转为红黑树，红黑树的节点数小于6转化为链表。

loadFactor装载因子（一般为0.75）：用来衡量 HashMap 满的程度。

loadFactor = size/capacity
threshold = capacity * loadFactor

装载因子非常重要，应严格限制在 0.7~0.8 以下，默认的负载因子0.75，是对空间和时间效率的一个平衡选择。超过 0.8 ，查表时的CPU缓存按照指数曲线上升。

如果内存空间很多而又对时间效率要求很高，可以降低负载因子loadFactor 的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子 loadFactor 的值，这个值可以大于1。

装载因子调小，这样比较容易触发扩容机制，扩容机制触发，占用更多的内存空间，但是可以减少桶内部的链表化和树形化，从而增加查找效率，也就是以空间换时间。

7 JDK1.8中扩容机制改进

扩容涉及到

rehash

、

复制数据

等操作，所以非常耗能。

相比于JDK1.7，JDK1.8使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动 2^n的位置。

resize() 1.7传参自定义newcap，1.8自动扩容2倍

JDK1.8在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。(深入了解请看这篇文章)

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

JDK1.8新增的优化点

。

//源码
//该语句判断是否落在“原索引”，还是落在“原索引+oldCap”
if ((e.hash & oldCap) == 0){} //原索引
else{} //原索引+oldCap

此外，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置（采用头插法），但JDK1.8不会倒置（采用尾插法）。

采用头插法，高并发容易引起循环链表

。

8 JDK1.8中hash()改进

重哈希

在 JDK1.8 中还有个高位参与运算，hashCode() 得到的是一个32位 int 类型的值，通过hashCode()的高16位异或低16位（将高16位渗透到低16位中）实现的：

(h = k.hashCode()) ^ (h >>> 16)

，主要是从速度、功效、质量来考虑的，

这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销

。

key.hashCode()是固定的，JDK1.8的hash()是加工后的key.hashCode()，而JDK1.7的hash()是直接用的 key。

加工过程：key.hashCode() ^ (h >>> 16)

加工后，key.hashCode()的低16位有更好的性能，减少碰撞率。

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}     
i = (table.length - 1) & hash;//这一步是在后面添加元素putVal()方法中进行位置的确定

下面举例说明一下，n为table的长度：

Java集合源码解析之——HashMap1 前言2 哈希表3 HashMap4 字段属性5 构造函数6 扩容机制7 JDK1.8中扩容机制改进8 JDK1.8中hash()改进

Java集合源码解析之——HashMap1 前言2 哈希表3 HashMap4 字段属性5 构造函数6 扩容机制7 JDK1.8中扩容机制改进8 JDK1.8中hash()改进

1 前言

2 哈希表

3 HashMap

3.1 HashMap定义

3.2 关于实现 Map 接口

3.3 关于实现Cloneable 及 Serializable 接口

4 字段属性

4.1 字段属性讲解

5 构造函数

6 扩容机制

7 JDK1.8中扩容机制改进

8 JDK1.8中hash()改进

继续阅读

Java小案例——随机数猜测随机数猜测

nginx location中斜线的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的简单使用

neo4j之cypher使用文档

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

spark/scala关于【资源文件】加载方法概述外部文件加载方案测试资源文件打包入jar包中小结

mybatis_入门程序Mybatis入门

AOP编程_Android优雅权限框架(1)概念基础，2021金三银四前言正文大纲正文

Effective Java 8:通用程序设计

OOM三种类型

工厂模式-三种类型

【递归】高效率求2的n次幂

win10本地scala和spark安装安装scala安装spark

JBoss,Geronimo和Glassfish初窥

scala (3) Function 和 Method