HashMap深度解析：一文让你彻底了解HashMap

前言

HashMap是Map族中最为常用的一种，也是 Java Collection Framework 的重要成员。本文首先给出了 HashMap 的实质并概述了其与 Map、HashSet 的关系，紧接着给出了 HashMap 在 JDK 中的定义，并结合源码分析了其四种构造方式。

最后，通过对 HashMap 的数据结构、实现原理、源码实现三个方面的剖析，深入到它底层 Hash 存储机制，解释了其底层数组长度总是 2 的 n 次方的原因，也揭示了其快速存取、扩容及扩容后的重哈希的原理与实现。

本文所有关于HashMap的源码都是基于JDK 1.6 的，不同 JDK 版本之间也许会有些许差异，但不影响我们对 HashMap 的数据结构、原理等整体的把握和了解。

HashMap 概述

Map 是 Key-Value 对映射的抽象接口，该映射不包括重复的键，即一个键对应一个值。HashMap 是 Java Collection Framework 的重要成员，也是Map族(如下图所示)中我们最为常用的一种。简单地说，HashMap 是基于哈希表的 Map 接口的实现，以 Key-Value 的形式存在，即存储的对象是 Entry (同时包含了 Key 和 Value) 。在HashMap中，其会根据hash算法来计算key-value的存储位置并进行快速存取。特别地，HashMap最多只允许一条Entry的键为Null(多条会覆盖)，但允许多条Entry的值为Null。此外，HashMap 是 Map 的一个非同步的实现。

虽然 HashMap 和 HashSet 实现的接口规范不同，但是它们底层的 Hash 存储机制完全相同。实际上，HashSet 本身就是在 HashMap 的基础上实现的

HashMap 在 JDK 中的定义

HashMap实现了Map接口，并继承 AbstractMap 抽象类，其中 Map 接口定义了键值映射规则。和 AbstractCollection抽象类在 Collection 族的作用类似， AbstractMap 抽象类提供了 Map 接口的骨干实现，以最大限度地减少实现Map接口所需的工作。HashMap 在JDK中的定义为：

1public class HashMap<K, V> extends AbstractMap<K, V>
2implements Map<K, V>, Cloneable, Serializable {
3    ...
4}

HashMap 的构造函数

HashMap 一共提供了四个构造函数，其中默认无参的构造函数和参数为Map的构造函数为 Java Collection Framework 规范的推荐实现，其余两个构造函数则是 HashMap 专门提供的。

1、HashMap(）

该构造函数意在构造一个具有> 默认初始容量 (16) 和默认负载因子(0.75) 的空 HashMap，是 Java Collection Framework 规范推荐提供的，其源码如下：

1/**
2 * Constructs an empty HashMap with the default initial capacity
3 * (16) and the default load factor (0.75).
4 */
5 public HashMap() {
6 //负载因子:用于衡量的是一个散列表的空间的使用程度
7 this.loadFactor = DEFAULT_LOAD_FACTOR; 
8 //HashMap进行扩容的阈值，它的值等于 HashMap 的容量乘以负载因子
9 threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
10 // HashMap的底层实现仍是数组，只是数组的每一项都是一条链
11 table = new Entry[DEFAULT_INITIAL_CAPACITY];
12 init();
13 }

2、HashMap(int initialCapacity, float loadFactor)

该构造函数意在构造一个指定初始容量和指定负载因子的空 HashMap，其源码如下：

1 /**
2 * Constructs an empty HashMap with the specified initial capacity and load factor.
3 */
4 public HashMap(int initialCapacity, float loadFactor) {
5 //初始容量不能小于 0
6 if (initialCapacity < 0)
7 throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
8 //初始容量不能超过 2^30
9 if (initialCapacity > MAXIMUM_CAPACITY)
10 initialCapacity = MAXIMUM_CAPACITY;
11 //负载因子不能小于 0 
12 if (loadFactor <= 0 || Float.isNaN(loadFactor))
13 throw new IllegalArgumentException("Illegal load factor: " +
14 loadFactor);
15 // HashMap 的容量必须是2的幂次方，超过 initialCapacity 的最小 2^n 
16 int capacity = 1;
17 while (capacity < initialCapacity)
18 capacity <<= 1; 
19 //负载因子
20 this.loadFactor = loadFactor;
21 //设置HashMap的容量极限，当HashMap的容量达到该极限时就会进行自动扩容操作
22 threshold = (int)(capacity * loadFactor);
23 // HashMap的底层实现仍是数组，只是数组的每一项都是一条链
24 table = new Entry[capacity];
25 init();
26 }

3、HashMap(int initialCapacity)

该构造函数意在构造一个指定初始容量和默认负载因子 (0.75)的空 HashMap，其源码如下：

1// Constructs an empty HashMap with the specified initial capacity and the default load factor (0.75)
2 public HashMap(int initialCapacity) {
3 this(initialCapacity, DEFAULT_LOAD_FACTOR); // 直接调用上述构造函数
4 }

4、HashMap(Map<? extends K, ? extends V> m)

该构造函数意在构造一个与指定 Map 具有相同映射的 HashMap，其初始容量不小于 16 (具体依赖于指定Map的大小)，负载因子是 0.75，是 Java Collection Framework 规范推荐提供的，其源码如下：

1// Constructs a new HashMap with the same mappings as the specified Map. 
2 // The HashMap is created with default load factor (0.75) and an initial capacity
3 // sufficient to hold the mappings in the specified Map.
4 public HashMap(Map<? extends K, ? extends V> m) {
5 // 初始容量不小于 16 
6 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
7 DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
8 putAllForCreate(m);
9 }

在这里，我们提到了两个非常重要的参数：初始容量和负载因子，这两个参数是影响HashMap性能的重要参数。其中，容量表示哈希表中桶的数量 (table 数组的大小)，初始容量是创建哈希表时桶的数量；负载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。

HashMap 的数据结构

哈希的相关概念

Hash 就是把任意长度的输入(又叫做预映射， pre-image)，通过哈希算法，变换成固定长度的输出(通常是整型)，该输出就是哈希值。这种转换是一种压缩映射，也就是说，散列值的空间通常远小于输入的空间。不同的输入可能会散列成相同的输出，从而不可能从散列值来唯一的确定输入值。简单的说，就是一种将任意长度的消息压缩到某一固定长度的息摘要函数。

哈希的应用：数据结构

我们知道，数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。那么我们能不能综合两者的特性，做出一种寻址容易，插入和删除也容易的数据结构呢？答案是肯定的，这就是我们要提起的哈希表。事实上，哈希表有多种不同的实现方法，我们接下来解释的是最经典的一种方法 —— 拉链法，我们可以将其理解为链表的数组，如下图所示：

我们可以从上图看到，左边很明显是个数组，数组的每个成员是一个链表。该数据结构所容纳的所有元素均包含一个指针，用于元素间的链接。我们根据元素的自身特征把元素分配到不同的链表中去，反过来我们也正是通过这些特征找到正确的链表，再从链表中找出正确的元素。其中，根据元素特征计算元素数组下标的方法就是哈希算法。

总的来说，哈希表适合用作快速查找、删除的基本数据结构，通常需要总数据量可以放入内存。在使用哈希表时，有以下几个关键点：

hash 函数（哈希算法）的选择：针对不同的对象(字符串、整数等)具体的哈希方法；
碰撞处理：常用的有两种方式，一种是open hashing，即 >拉链法；
另一种就是 closed hashing，即开地址法(opened addressing)。

HashMap 的数据结构

我们知道，在Java中最常用的两种结构是数组和链表，几乎所有的数据结构都可以利用这两种来组合实现，HashMap 就是这种应用的一个典型。实际上，HashMap 就是一个链表数组，如下是它数据结构：

从上图中，我们可以形象地看出HashMap底层实现还是数组，只是数组的每一项都是一条链。其中参数initialCapacity 就代表了该数组的长度，也就是桶的个数。在第三节我们已经了解了HashMap 的默认构造函数的源码：

1 /**
2 * Constructs an empty HashMap with the default initial capacity
3 * (16) and the default load factor (0.75).
4 */
5 public HashMap() {
6 //负载因子:用于衡量的是一个散列表的空间的使用程度
7 this.loadFactor = DEFAULT_LOAD_FACTOR; 
8 //HashMap进行扩容的阈值，它的值等于 HashMap 的容量乘以负载因子
9 threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
10 // HashMap的底层实现仍是数组，只是数组的每一项都是一条链
11 table = new Entry[DEFAULT_INITIAL_CAPACITY];
12 init();
13 }

从上述源码中我们可以看出，每次新建一个HashMap时，都会初始化一个Entry类型的table数组，其中 Entry类型的定义如下：

1static class Entry<K,V> implements Map.Entry<K,V> {
2 final K key; // 键值对的键
3 V value; // 键值对的值
4 Entry<K,V> next; // 下一个节点
5 final int hash; // hash(key.hashCode())方法的返回值
6 /**
7 * Creates new entry.
8 */
9 Entry(int h, K k, V v, Entry<K,V> n) { // Entry 的构造函数
10 value = v;
11 next = n;
12 key = k;
13 hash = h;
14 }
15 ......
16}

其中，Entry为HashMap的内部类，实现了 Map.Entry 接口，其包含了键key、值value、下一个节点next，以及hash值四个属性。事实上，Entry 是构成哈希表的基石，是哈希表所存储的元素的具体形式。

HashMap 的快速存取

下面我们结合JDK源码看HashMap 的存取实现。

HashMap 的存储实现

在 HashMap 中，键值对的存储是通过 put(key,vlaue) 方法来实现的，其源码如下：

1/**
2 * Associates the specified value with the specified key in this map.
3 * If the map previously contained a mapping for the key, the old
4 * value is replaced.
5 *
6 * @param key key with which the specified value is to be associated
7 * @param value value to be associated with the specified key
8 * @return the previous value associated with key, or null if there was no mapping for key.
9 * Note that a null return can also indicate that the map previously associated null with key.
10 */
11 public V put(K key, V value) {
12 //当key为null时，调用putForNullKey方法，并将该键值对保存到table的第一个位置 
13 if (key == null)
14 return putForNullKey(value); 
15 //根据key的hashCode计算hash值
16 int hash = hash(key.hashCode()); // ------- (1)
17 //计算该键值对在数组中的存储位置（哪个桶）
18 int i = indexFor(hash, table.length); // ------- (2)
19 //在table的第i个桶上进行迭代，寻找 key 保存的位置
20 for (Entry<K,V> e = table[i]; e != null; e = e.next) { // ------- (3)
21 Object k;
22 //判断该条链上是否存在hash值相同且key值相等的映射，若存在，则直接覆盖 value，并返回旧value
23 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
24 V oldValue = e.value;
25 e.value = value;
26 e.recordAccess(this);
27 return oldValue; // 返回旧值
28 }
29 }
30 modCount++; //修改次数增加1，快速失败机制
31 //原HashMap中无该映射，将该添加至该链的链头
32 addEntry(hash, key, value, i); 
33 return null;
34 }

对NULL键的特别处理：putForNullKey()

我们直接看其源码：

1/**
2 * Offloaded version of put for null keys
3 */
4 private V putForNullKey(V value) {
5 // 若key==null，则将其放入table的第一个桶，即 table[0]
6 for (Entry<K,V> e = table[0]; e != null; e = e.next) { 
7 if (e.key == null) { // 若已经存在key为null的键，则替换其值，并返回旧值
8 V oldValue = e.value;
9 e.value = value;
10 e.recordAccess(this);
11 return oldValue;
12 }
13 }
14 modCount++; // 快速失败
15 addEntry(0, null, value, 0); // 否则，将其添加到 table[0] 的桶中
16 return null;
17 }

HashMap 中的哈希策略（算法）

1/**
2
3* Applies a supplemental hash function to a given hashCode, which
4
5* defends against poor quality hash functions. This is critical
6
7* because HashMap uses power-of-two length hash tables, that
8
9* otherwise encounter collisions for hashCodes that do not differ
10
11* in lower bits.
12
13*
14
15* Note: Null keys always map to hash 0, thus index 0.
16
17*/
18
19static int hash(int h) {
20
21// This function ensures that hashCodes that differ only by
22
23// constant multiples at each bit position have a bounded
24
25// number of collisions (approximately 8 at default load factor).
26
27h ^= (h >>> 20) ^ (h >>> 12);
28
29return h ^ (h >>> 7) ^ (h >>> 4);
30}

正如JDK官方对该方法的描述那样，使用hash()方法对一个对象的hashCode进行重新计算是为了防止质量低下的hashCode()函数实现。由于hashMap的支撑数组长度总是 2 的幂次，通过右移可以使低位的数据尽量的不同，从而使hash值的分布尽量均匀。

通过上述hash()方法计算得到 Key 的 hash值后，怎么才能保证元素均匀分布到table的每个桶中呢？我们会想到取模，但是由于取模的效率较低，HashMap 是通过调用上面的indexFor()方法处理的，其不但简单而且效率很高，对应源码如下所示：

1/**
2 *
3 * Returns index for hash code h.
4 *
5 */
6static int indexFor( int h, int length )
7{
8    return(h & (length - 1) ); /* 作用等价于取模运算，但这种方式效率更高 */
9}

HashMap 中键值对的添加：addEntry()

我们直接看其源码：

1/**
2 * Adds a new entry with the specified key, value and hash code to
3 * the specified bucket. It is the responsibility of this
4 * method to resize the table if appropriate.
5 *
6 * Subclass overrides this to alter the behavior of put method.
7 * 
8 * 永远都是在链表的表头添加新元素
9 */
10 void addEntry(int hash, K key, V value, int bucketIndex) {
11 //获取bucketIndex处的链表
12 Entry<K,V> e = table[bucketIndex];
13 //将新创建的 Entry 链入 bucketIndex处的链表的表头 
14 table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
15 //若HashMap中元素的个数超过极限值 threshold，则容量扩大两倍
16 if (size++ >= threshold)
17 resize(2 * table.length);
18 }

HashMap 的扩容：resize()

随着HashMap中元素的数量越来越多，发生碰撞的概率将越来越大，所产生的子链长度就会越来越长，这样势必会影响HashMap的存取速度。为了保证HashMap的效率，系统必须要在某个临界点进行扩容处理，该临界点就是HashMap中元素的数量在数值上等于threshold（table数组长度_加载因子）。但是，不得不说，扩容是一个非常耗时的过程，因为它需要重新计算这些元素在新table数组中的位置并进行复制处理。_所以，如果我们能够提前预知HashMap 中元素的个数，那么在构造HashMap时预设元素的个数能够有效的提高HashMap的性能*。我们直接看其源码：

1/**
2 *
3 * Rehashes the contents of this map into a new array with a
4 *
5 * larger capacity. This method is called automatically when the
6 *
7 * number of keys in this map reaches its threshold.
8 *
9 *
10 *
11 * If current capacity is MAXIMUM_CAPACITY, this method does not
12 *
13 * resize the map, but sets threshold to Integer.MAX_VALUE.
14 *
15 * This has the effect of preventing future calls.
16 *
17 *
18 *
19 * @param newCapacity the new capacity, MUST be a power of two;
20 *
21 * must be greater than current capacity unless current
22 *
23 * capacity is MAXIMUM_CAPACITY (in which case value
24 *
25 * is irrelevant).
26 *
27 */
28void resize( int newCapacity )
29{
30    Entry[] oldTable = table;
31    int oldCapacity = oldTable.length;
32    /* 若 oldCapacity 已达到最大值，直接将 threshold 设为 Integer.MAX_VALUE */
33    if ( oldCapacity == MAXIMUM_CAPACITY )
34    {
35        threshold = Integer.MAX_VALUE;
36        return; /* 直接返回 */
37    }
38    /* 否则，创建一个更大的数组 */
39    Entry[] newTable = new Entry[newCapacity];
40    /* 将每条Entry重新哈希到新的数组中 */
41    transfer( newTable );
42    table = newTable;
43    threshold = (int) (newCapacity * loadFactor); /* 重新设定 threshold */
44}

HashMap 的重哈希：transfer()

重哈希的主要是一个重新计算原HashMap中的元素在新table数组中的位置并进行复制处理的过程，我们直接看其源码：

1/**
2*
3* Transfers all entries from current table to newTable.
4*
5*/
6void transfer( Entry[] newTable )
7{
8/* 将原数组 table 赋给数组 src */
9Entry[] src = table;
10int newCapacity = newTable.length;
11/* 将数组 src 中的每条链重新添加到 newTable 中 */
12for ( int j = 0; j < src.length; j++ )
13{
14Entry<K, V> e = src[j];
15if ( e != null )
16{
17src[j] = null; /* src 回收 */
18/* 将每条链的每个元素依次添加到 newTable 中相应的桶中 */
19do
20{
21Entry<K, V> next = e.next;
22/* e.hash指的是 hash(key.hashCode())的返回值; */
23/* 计算在newTable中的位置，注意原来在同一条子链上的元素可能被分配到不同的子链 */
24int i = indexFor( e.hash, newCapacity );
25e.next = newTable[i];
26newTable[i] = e;
27e = next;
28}
29while ( e != null );
30}
31}
32}

特别需要注意的是，在重哈希的过程中，原属于一个桶中的Entry对象可能被分到不同的桶，因为HashMap 的容量发生了变化，那么 h&(length - 1) 的值也会发生相应的变化。极端地说，如果重哈希后，原属于一个桶中的Entry对象仍属于同一桶，那么重哈希也就失去了意义。

HashMap 的读取实现

相对于HashMap的存储而言，读取就显得比较简单了。因为，HashMap只需通过key的hash值定位到table数组的某个特定的桶，然后查找并返回该key对应的value即可，源码如下：

1/**
2* Returns the value to which the specified key is mapped,
3* or {@code null} if this map contains no mapping for the key.
4* <p>More formally, if this map contains a mapping from a key
5* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
6* key.equals(k))}, then this method returns {@code v}; otherwise
7* it returns {@code null}. (There can be at most one such mapping.)
8* <p>A return value of {@code null} does not <i>necessarily</i>
9* indicate that the map contains no mapping for the key; it's also
10* possible that the map explicitly maps the key to {@code null}.
11* The {@link #containsKey containsKey} operation may be used to
12* distinguish these two cases.
13* @see #put(Object, Object)
14*/
15public V get( Object key )
16{
17/* 若为null，调用getForNullKey方法返回相对应的value */
18if ( key == null )
19/* 从table的第一个桶中寻找 key 为 null 的映射；若不存在，直接返回null */
20return(getForNullKey() );
21/* 根据该 key 的 hashCode 值计算它的 hash 码 */
22int hash = hash( key.hashCode() );
23/* 找出 table 数组中对应的桶 */
24for ( Entry<K, V> e = table[indexFor( hash, table.length )];
25e != null;
26e = e.next )
27{
28Object k;
29/* 若搜索的key与查找的key相同，则返回相对应的value */
30if ( e.hash == hash && ( (k = e.key) == key || key.equals( k ) ) )
31return(e.value);
32}
33return(null);
34}

针对键为NULL的键值对，HashMap 提供了专门的处理：getForNullKey() 其源码如下：

1/**
2 *
3 * Offloaded version of get() to look up null keys. Null keys map
4 *
5 * to index 0\. This null case is split out into separate methods
6 *
7 * for the sake of performance in the two most commonly used
8 *
9 * operations (get and put), but incorporated with conditionals in
10 *
11 * others.
12 *
13 */
14private V getForNullKey()
15{
16    /* 键为NULL的键值对若存在，则必定在第一个桶中 */
17    for ( Entry<K, V> e = table[0]; e != null; e = e.next )
18    {
19        if ( e.key == null )
20            return(e.value);
21    }
22    /* 键为NULL的键值对若不存在，则直接返回 null */
23    return(null);
24}

因此，调用HashMap的get(Object key)方法后，若返回值是 NULL，则存在如下两种可能：

该 key 对应的值就是 null;
HashMap 中不存在该 key。

如果您想第一时间看我的后期文章，可以关注关注helloworld开发者社区

HashMap深度解析：一文让你彻底了解HashMap

前言

HashMap 概述

HashMap 在 JDK 中的定义

HashMap 的构造函数

1、HashMap(）

2、HashMap(int initialCapacity, float loadFactor)

3、HashMap(int initialCapacity)

4、HashMap(Map<? extends K, ? extends V> m)

HashMap 的数据结构

哈希的相关概念

哈希的应用：数据结构

HashMap 的数据结构

HashMap 的快速存取

HashMap 的存储实现

对NULL键的特别处理：putForNullKey()

HashMap 中的哈希策略（算法）

HashMap 中键值对的添加：addEntry()

HashMap 的扩容：resize()

HashMap 的重哈希：transfer()

HashMap 的读取实现

评论区

相关推荐