目录
- 1 一般数据结构及特点
- 2 HashMap基本属性说明
-
3 HashMap 数据结构
- 3.1构造函数
- 3.2 Node<k,v>分析
-
4 put过程分析
- 4.1 扩容方法resize()分析
- 4.2 put方法分析
-
5 关于HashMap
- 5.1 HashMap如何实现put、get操作时间复杂度为O(1)~O(n)?
- 5.2 HashMap什么时候从单节点转成链表又是什么时候从链表转成红黑树？
- 5.3 HashMap初始化时为什么要给自定义的初始容量？
- 5.4 HashMap如何保证容量始终是2的幂？
- 5.5 HashMap为何要保证容量始终是2的幂
-
5.6 HashMap计算hash值
- 5.6.1 key的hash值>>>16，为什么要这样做呢？
- 5.7 HashMap为什么是线程不安全的？
- 6 get 过程分析
特别：下文的“容量”、“数组长度”，“capacity” 都是指底层数组长度，即 table.length
1 一般数据结构及特点
- 数组：占用连续内存的数据结构，查找容易[O(1)]，插入困难[O(n)]
- 链表：由一组指向（单向或者双向）的节点连接的数据结构，内存不连续，查找困难，但插入删除容易
- 哈希表：插入删除查找都容易的数据结构
- 数组下标是通过：（Node<K, V>[] 的容量-1）&（hash(key)）的出来的
本章要解决的问题：
- HashMap的数据结构实现方式
- HashMap是怎么做到为get、put操作提供稳定的时间复杂度的
- HashMap什么时候从单节点转成链表又是什么时候从链表转成红黑树
- HashMap初始化时为什么要给自定义的初始容量。
- HashMap如何保证容量始终是2的幂
- HashMap为何要保证容量始终是2的幂
- HashMap的hash值如何计算
- HashMap为什么是线程不安全的
2 HashMap基本属性说明
常量部分：
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认初始容量 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 int size; //HashMap的元素个数
- default_initial_capacity：初始容量=16
- maximum_capacity：最大容量=1<<30。
- default_load_factor：负载因子=0.75。
- threshold：下一个触发扩容操作的阈值，threshold = capacity * load_factor。当元素数量(size值)超过阈值时触发扩容，新容量是旧容量2倍。
- treeify_threshold：链表转红黑树时链表长度阈值=8
- untreeify_threshold： 红黑树转链表阈值=6，红黑树节点小于6就会转成链表。
- Node<K, V> implements Map.Entry<K, V> ：HashMap存放数据的基本单位，里面存有hash值、key、value、next。
- Node<K, V>[] table：存放Node节点的数组，HashMap底层数组，数组元素可以为单节点Node、多节点链表、多节点红黑树。
- size：成员变量，表示当前Map的键值对数量，在put、remove、clear操作，会修改该值。扩容也是通过阈值跟size进行比较决定
3 HashMap 数据结构
-
HashMap是一个Node类型的数组，每个元素可以为单节点、链表、红黑树。
-
Java8之前，HashMap的数据结构如下：
数组+链表：链表是为了解决hash冲突
- Java8，HashMap的数据结构如下：
数组+链表+红黑树
3.1构造函数
Tips：
- 确定加载因子
- 根据初始容量参数重新计算扩容阈值（大于或等于初始容量且一定等于2的幂的那个数）
tableSizeFor(initialCapacity):确定扩容阈值：大于或等于初始容量且一定等于2的幂的那个数；比如cap=8则返回8；cap=9则返回16
源码分析如下：
//构造函数一：无参构造函数：加载因子（0.75）和初始容量（16）分别使用默认值
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
//构造函数二：
//指定初始容量，调用HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//构造函数三：同时指定初始容量和加载因子
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;//初始容量不能超过最大容量：
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +loadFactor);
this.loadFactor = loadFactor;
// 确定扩容阈值：大于或等于初始容量且一定等于2的幂的那个数；比如cap=8则返回8；cap=9则返回16
this.threshold = tableSizeFor(initialCapacity);
}
//构造函数三：创建一个跟参数有相同结构的map
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
3.2 Node<k,v>分析
tips：一个简单的K-V模型的数据体，提供对key value的set get操作
源码如下：
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
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) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value); // key value 的hash值再做异或运算
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
4 put过程分析
4.1 扩容方法resize()分析
HashMap的容量变化通常存在以下几种情况：
-
空参数的构造函数：实例化的HashMap默认内部数组是null，即没有实例化。第一次调用put方法时，则会开始第一次初始化扩容，长度为16。【懒加载】
-
有参构造函数：用于指定容量。根据阈值计算方式【大于或等于初始容量且一定等于2的幂的那个数】，将这个数设置赋值给阈值。第一次调用put方法时，会将阈值赋值给容量（第一步），然后让 阈值=负载因子X容量（第二步）
。（因此并不是我们手动指定了容量就一定不会触发扩容，超过阈值后一样会扩容！！） -
如果不是第一次扩容，则容量变为原来的2倍，阈值也变为原来的2倍。（负载因子还是不变）
-
首次put时，先会触发扩容（底层table初始化），然后存入数据，然后判断是否需要扩容；不是首次put，则不再初始化，直接存入数据，然后再判断是否需要扩容；
参看源码：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;//当前数组
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//非首次put，扩容阈值变为原来2倍；容量变为原来的2倍
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;//达到最大值，不能扩容，返回当前数组
}
//数组容量扩大为原来2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 将扩容阈值变为原来2倍
}
//第一次 put 的时候，【对应使用 new HashMap(int initialCapacity) 初始化后】
else if (oldThr > 0)
newCap = oldThr; //如果初始化Map时指定了初始容量，则数组容量=扩容阈值（参照阈值的计算）
//第一次 put 的时候 ，【对应使用 new HashMap() 初始化后】
else {
newCap = DEFAULT_INITIAL_CAPACITY;//没有指定初始容量，则数组容量=默认初始容量
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//扩容阈值=加载因子*默认初始容量=12
}
//第一次put且有指定初始容量时 ：重新计算扩容阈值：新扩容阈值=加载因子*新数组长度
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//计算好容量初始化一个新的数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//如果第一次put，这里就直接返回newTab，扩容过程结束；
table = newTab;
if (oldTab != null) {
// 开始遍历原数组，进行数据迁移。
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)//数组当前位置不存在链表或者红黑树，则直接put到该位置
newTab[e.hash & (newCap - 1)] = e; //返回单节点的Node数组
else if (e instanceof TreeNode)
//红黑树
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
//链表
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
4.2 put方法分析
源码分析：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* @param hash：key的hash值
* @param onlyIfAbsent ：false表示key存在时，覆盖value
* @param evict if false, the table is in creation mode. 待补充
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
//第一次put，先执行数组初始化操作
n = (tab = resize()).length;
//当前key对应的数组下标没有元素，则直接初始化新的Node到该数组位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null); //注意此时Node没有Next
else {
//当前key对应的数组下标已经存在元素
Node<K,V> e; K k;
// 情况一：//该位置的元素跟新put进来的数据key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //注意这里是引用的赋值，因此后面e.value=value可以实现value覆盖
//情况二：当前位置是红黑树结构
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//情况三：当前位置是链表结构
for (int binCount = 0; ; ++binCount) {
//遍历到达链表末端
if ((e = p.next) == null) {
//创建新的Node并放在链表的末端
p.next = newNode(hash, key, value, null);
// treeify_threshold 为 8，所以，如果新插入的值是链表中的第 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; //这里break，代码后面统一对e进行value的覆盖处理
//此时既未遍历到链表末端，也没有发现key相等，则继续链表遍历
p = e; //这个赋值，相当于链表的遍历，尾部指向下一个节点的头部，实现链表遍历
}
}
if (e != null) { // existing mapping for key key相等时
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value; //新的value覆盖旧的value值
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
//每次put操作完成后，size自增；
//如果size超过阈值，则在put完成后，再次执行扩容
resize();
afterNodeInsertion(evict);//父类抽象方法的实现，HashMap不做任何实现
return null;
}
- 第一次put时扩容过程如下：
容量：C
加载因子：F
扩容阈值：T
------ 1、无参初始化：
F=0.75
C=0
T=0
------ 2、有参初始化：容量参数=7
F=0.75
C=0
T=tableSizeFor(7)=8 //1、2、4、8 。。。大于7 所以取8
------ 3、第一次put && 无参初始化时
F=0.75
C=16（默认容量）
T=16*0.75=12
------ 4、第一次put && 有参初始化时
F=0.75
C=T=8 // 容量=阈值
T=8*0.75=6 // 阈值更新：容量*加载因子
5 关于HashMap
5.1 HashMap如何实现put、get操作时间复杂度为O(1)~O(n)?
- 首先，对于数组的元素，如果知道index，那查找的复杂度就是O(1)级别
- 对于get操作，首先根据key计算出hash值，而这个hash值 执行操作hash&(n-1)就是它所在的index，在最好的情况下，该index只有一个节点且hash值与key的hash值相等，那么时间的复杂度就是O(1)。当该节点为链表或者红黑树时，时间复杂度会上升，但是由于HashMap的优化（链表长度、红黑树长度相对HashMap容量不会过长，过长会触发resize操作），所以 最坏的情况也就是O(n) ,可能还会小于这个值。【链表的查询时间复杂度是：O (n)，红黑树是 O(logN)，比O (n)更小】
- 对于put操作，我们知道，数组插入元素的成本是高昂的，HashMap巧妙的 使用链表和红黑树代替了数组插入元素需要移动后续元素的消耗，这样在最好的情况下，插入一个元素，该index位置恰好没有元素的话，时间复杂度就是O(1),当该位置有元素且为链表或者红黑树的情况下，时间复杂度会上升，但是最坏的情况下也就是O(n)。
5.2 HashMap什么时候从单节点转成链表又是什么时候从链表转成红黑树？
- 单节点转链表：当计算出来的index处有元素，且元素是单节点时，则该节点变为链表；
- 链表转红黑树有两个条件：
- 链表长度大于TREEIFY_THRESHOLD，默认阈值是8；
- HashMap长度大于64
5.3 HashMap初始化时为什么要给自定义的初始容量？
- 不指定初始容量时，HashMap底层数组的在第一次put值时，数组长度为默认初始长度即16，加载因子为0.75，扩容阈值为16*0.75=12；当元素数量大于12时，底层数组进行扩容，长度翻倍为32，扩容阈值翻倍为24，依次类推；
- 指定初始容量时，假设初始容量为C=1000。HashMap底层数组的在第一次put值时，数组长度初始化为 1024，扩容阈值为1024*0.75=768；当元素数量大于768时，底层数组进行扩容，长度和阈值同时翻倍。
- 因此，当HashMap元素足够多时，不指定初始容量要比指定初始容量进行更多次的扩容，扩容涉及数组拷贝、链表或红黑树重建，消耗更多性能。
- 根据要使用的HashMap大小确定初始容量，这也不是说为了避免扩容初始容量给的越大越好， 越大申请的内存就越大，如果你没有这么多数据去存，又会造成hash值过于离散，增加查询或修改的时间复杂度。
5.4 HashMap如何保证容量始终是2的幂？
HashMap使用方法tableSizeFor()来保证无论你给值是什么，返回的一定是2的幂
/**
* Returns a power of two size for the given target capacity.
*/
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;
}
5.5 HashMap为何要保证容量始终是2的幂
- HashMap在定位元素在数组的index时，运算公式是 (n-1)&hash ,n为数组的长度。如果容量始终是2的次幂，例如 0000 0000 0000 0000 0000 0000 1000 0000，则n-1的二进制形式为：0000 0000 0000 0000 0000 0000 0111 1111 ，低位区一定是1，在进行 (n-1)&hash，hash低位区的0、1特征能够保留
- 因此，容量始终是2的幂，这样 下标index值的取值范围更广，减少hash碰撞。
5.6 HashMap计算hash值
1、带着疑问：
key的hashCode为什么右移16位后再进行异或运算？
2、关于 | & ^ 三种运算的特征说明：
- ^按位异或运算：位相同返回0，不同返回1；可推导出：任何数跟0异或返回任何数，任何数跟1异或返回对应的取反
- 异或运算能更好的保留各部分的特征，如果采用逻辑与&运算计算出来的值会向0靠拢（00得0，01得0，11得1 因此0的概率2/3），采用逻辑或|运算计算出来的值会向1靠拢 (00得0，01得1，11得1，因此1的概率为2/3)
3、hash()源码：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//key.hashCode() ;hashCode是Object对象的一个native方法，由操作系统实现，跟内存地址存在某种映射关系
4、进入分析：
5.6.1 key的hash值>>>16，为什么要这样做呢？
- h值右移16后，高16位都为0，这样h^(h>>>16)时，高16位的值不会有任何变化，但是低16位的值混杂了key的高16位的值，从而增加了hash值的复杂度，进一步减少了hash值一样的概率。
- 计算数组下标公式：(n-1)&hash，n-1的结果：高位趋于0；&运算的结果：高16位向0靠拢，hash的高位特征丢失
- 因此，如果我们不做hash值的移位和异或运算，那么在计算数组index时将丢失高区特征
简单点：
因为：(n-1)&hash中，hash的高位数将被数组长度的二进制码锁屏蔽，为确保hash的高位尽可能利用，就先对hash值先右移16位，再跟原hash值进行异或运算，同时保留高位和低位特征。
数组长度二进制码屏蔽是什么意思？
数组长度的数据类型int转化为32位的二进制，因为长度值对比最大值（2的32位）总是比较小的，所以它的高位趋向0，与其他数进行&运算后，结果值的高位趋向0，那么其他数的高位特征就丢失了
下面用例子分析：
### 计算hash
hashCode： 0000 0000 0101 0000 0000 0000 1111 1010
hashCode>>>16: 0000 0000 0000 0000 0000 0000 0101 0000
hashCode^hashCode>>>16: 0000 0000 0101 0000 0000 0000 0110 1010
hash=hashCode^hashCode>>>16 0000 0000 0101 0000 0000 0000 0110 1010
### 计算index时：
(n-1) (假设n=16) 0000 0000 0000 0000 0000 0000 0000 1111
(n-1)&hash 0000 0000 0000 0000 0000 0000 0000 1010
仔细观察上文不难发现，高16位很有可能会被数组长度的二进制码锁屏蔽，
如果我们不做移位异或运算，那么在计算数组index时将丢失高区特征
5.7 HashMap为什么是线程不安全的？
- 它没有任何的锁或者同步等多线程处理机制，无法控制并发下导致的线程冲突。
- 如果想要线程安全的使用基于hash表的map，可以使用ConcurrentHashMap，该实现get操作是无锁的，put操作也是分段锁，性能很好
6 get 过程分析
- 计算 key 的 hash 值，根据 hash 值找到对应数组下标: hash & (length-1)
- 判断数组该位置处的元素是否刚好就是我们要找的，如果不是，走第三步
- 判断该元素类型是否是 TreeNode，如果是，用红黑树的方法取数据，如果不是，走第四步
- 遍历链表，直到找到相等(==或equals)的 key
参考资料：
- [良许-HashMap源码实现分析]：https://www.cnblogs.com/yychuyu/p/13357218.html