1. HashMap的结构

在HashMap中Key-Value数据的存储采用哈希表的方式实现也就是基本的数组 + 链表结构。

图1 HashMap的存储结构

在HashMap中定义了一个Node数组存储所有的key-value关系，Node的定义如下。

static class Node<K,V> implements Map.Entry<K,V> {
	final int hash;
	final K key;
	V value;
	Node<K,V> next;

	Node(int hash, K key, V value, Node<K,V> next) 

	public final K getKey() 
	public final V getValue() 
	public final String toString() 

	public final int hashCode()

	public final V setValue(V newValue)

	public final boolean equals(Object o)
}

Node是一个内部类，实现了Map.Entry的接口，本质上是一个(键值对)。在上图中每个黑点表示一个Node对象。

在了解HashMap我们先来了解一下HashMap实现时候的存储结构，也就是HashMap当中定义了哪些属性字段:

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;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;

DEFAULT_INITIAL_CAPACITY: 表示默认的初始化容量，必须是2的指数
DEFAULT_INITIAL_CAPACITY：最大容量，如果两个代参构造函数指定了该值并且大于这个值的话，就使用这个值，表示HashMap的最大容量。
DEFAULT_LOAD_FACTOR: 在构造函数中没有指定装载系数的时候，默认使用该装载系数。
TREEIFY_THRESHOLD: 在HashMap中将链表转化成红黑树的阈值。当链表的长度大于8的时候链表转换成红黑树。
UNTREEIFY_THRESHOLD:
MIN_TREEIFY_CAPACITY:
table: table定义了HashMap的hash表结构。在HashMap第一次使用的时候进行初始化，数组大小根据需要调整大小，分配的时候长度总是2的幂。(在某些操作中，允许大小为0)
entrySet: 所有map记录的集合
size: 表示所有mapping映射中key-value键值对的个数。
modCount: 这个散列表被结构性修改的次数。
threshold: 接下来做resize()操作的阈值。
loadFactor: 哈希表的加载因子。

在HashMap中数据通过Hash表来存储，Hash表为了解决数据的冲突可以采取两种方式来解决问题。一种是开放地址法，另外一种是链地址法。在Java中采用链地址法，也就是数组 + 链表的方式。

在HashMap中通过将”key”值进行hashCode()得到哈希编码，然后通过高位运算和取模运算来确定键值对的存储位置。当两个key定位到相同的位置的时候，表示发生了Hash冲撞。

Hash算法的结果越分散均匀，Hash碰撞的概率越小，Map存取的效率会越高

Hash桶数组越大，Hash数组越分散，如果哈希桶数组很小，即使好的Hash算法也会出现碰撞，所以HashMap的操作需要在空间成本和时间成本之间进行权衡。也就是根据实际情况确定HashMap中数组分桶的大小。

怎么样能够使得HashMap访问的效率更高，同时数组的分桶又占用更少的空间，就是采用好的Hash算法和扩容机制

2. HashMap如何扩容

在确定hashMap如何扩容的时候，我们先了解以下几个字段:

int threshold;             // 所能容纳的key-value对极限 
final float loadFactor;    // 负载因子
int modCount;  
int size;  

Node[] table初始化的长度length(默认长度是16)， threshold表示HashMap所能够容纳的最大的键值对的个数。 threshold = length * load fractor 当数组定义好之后，加载因子越大能够存储的键值个数越多。

默认0.75的加载因子是对空间和时间效率的平衡选择，建议不要进行修改。

在HashMap中键值对的个数操作阈值之后，通过resize进行扩容，扩容后HashMap的容量是原来的两倍。

size是HashMap中实际键值对存在的数量和table length以及threshold还是有区别的。 modCount是用来记录HashMap内部结构发生变化的次数，主要用于迭代的快速失败。 put新建键值对的时候，HashMap的结构发生变化，但是如果key的值被新的值覆盖，不属于HashMap的结构发生变化。

在哈希桶数组中，一般将table的长度length设置为素数。相对来说素数导致冲突的概率要小于合数。 HashMap采用这种非常规的设计主要是为了取模和扩容时做优化，同时为了减少冲突。

3. 链表转红黑树

在HashMap中，除了通过合理的桶大小和哈希数组设置来减少查找时间，还采用另外一种方式，来避免桶链表过长导致对HashMap性能的影响。

在JDK1.8中引入了红黑树，当链表长度太长(默认超过8)时，链表转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能。

4. 功能实现

在第四个小章节中，我们主要介绍一下Hash表的基本功能的定义。

4.1 确定Hash桶数组索引位置

不增加、删除、查找键值对，定位到哈希数组的位置都是很关键的一步。

HashMap的数据结构是数组和链表的结合，这个时候我们希望HashMap里面的元素尽量分布得均匀些，尽量使每个位置只有一个。那么这种情况下，我们需要使用hash算法来求得这个索引位置，这样能够快速知道想要的元素减少遍历，优化查询效率。

HashMap定位数组索引位置，直接决定了hash方法的离散性能。具体的源码实现如下:

方法一：
static final int hash(Object key) {   //jdk1.8 & jdk1.7
     int h;
     // h = key.hashCode() 为第一步 取hashCode值
     // h ^ (h >>> 16)  为第二步 高位参与运算
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
方法二：
static int indexFor(int h, int length) {  //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
     return h & (length-1);  //第三步 取模运算
}

在通过哈希算法求索引的操作中本质上包含三个步骤:

取key的hashCode
高位运算
取模运算

对于给定的任意对象，只要hashCode()返回值相同，程序调用的方法所计算得到的Hash编码都相同。那么我们首先想到的是将hash值对应的数组长度取模运算，这样一来，元素分布相对来说比较均匀。

可是取模运算的计算开销比较大，在HashMap中通常调用方法二来计算该对象应该保存在table数组的哪一个索引位置。

在方法二中通过h&(table.length -1)来得到对象的保存位，而HashMap底层数组的长度总是2的$n$次方，这是HashMap在速度上的优化。当Length总是2次方的时候， h&(table.length -1)运算等价于对length取模，也就是h%length。

在JDK1.8中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现:(h = k.hashCode()) ^ (h >>> 16)

4.2 分析HashMap的put方法

在美团技术团队的文章中，给出HashMap中put方法的执行流程，对应如下图2。

图2 HashMap put流程

4.3 扩容机制

扩容(resize)就是重新计算容量。当我们向HashMap对象中不断添加元素，而HashMap对象内部的数组没有办法装载更多的元素的时候，对象就需要扩大数组的长度，以便能够装入更多的元素。

在java里的数组没有办法自动扩容，方法是采用新的数组代替掉已有的小数组。

HashMap相关常见的问题

December 21, 2020