[Java知识库]Hashmap底层源码分析，万字心血

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

Hashmap在学习Java的过程中是很重要的容器，无论你是做acm，搞软件，还是去面试，理解Hashmap底层源码都是Java路上的重要节点。

文章多有不到之处，欢迎各位大佬批评指正。

一、Map接口介绍

1.Map接口特点

Map接口定义了双例集合的存储特征，它并不是Collection接口的子借口。双例集合的存储特征是以key与value结构为单位进行存储。提现的是数学中的函数y=f(x)概念。

2.Map的常用方法

二、HashMap容器类

HashMap是Map接口的接口实现类，它采用哈希算法实现，是Map接口最常用的实现类。由于底层采用了哈希表存储数据，所以要求键不能重复，如果发生重复，新的值会替换旧的值。HashMap在查找、删除、修改方面都有非常高的效率。

1.添加元素

代码如下（示例）：

public class HashMap{
	public static void main（String[] args）{
		Map<String,String> map = new HashMap<>();

		map.put("a","A");
		String value = map.put("a","B");
		System.out.println(value)l;
}

}

2.获取元素

//方式一
//通过get方法获取元素
String val = map.get（"a"）;
System.out.println(val);

//方式二
//通过keySet方法获取元素
Set<String> keys = map.keySet();
for(String key : keys){
String v1 = map.get(key);
System.out.println(key+"----------"+v1);

//方式三
//通过entrySet方法获取Map.Entry类型获取元素
Set<Map.Entry<String,String>> entrySet = map.entrySet();
for(Map.Entry<String,String> entry:entrySet){
String key = entry.getKey();
String v = entry.getValue();
System.out.println(key+" ---------- "+v);
}
}

3.Map容器的并集操作

Map<String,String> map2 = new HashMap<>();
map2.put("f","F");
map2.put("c","cc");
map2.putAll(map);
Set<String> keys2 = map2.keySet();
for(String key:keys2){
System.out.println("key: "+key+" Value: "+map2.get(key));
}

4.删除元素

String v = map.remove("e");
System.out.println(v);
Set<String> keys3 = map.keySet();
for(String key:keys3){
System.out.println("key: "+key+" Value: "+map.get(key));
}

5.判断key或value是否存在

//判断key是否存在
boolean flag = map.containsKey("a");
System.out.println(flag);

//判断value是否存在
boolean flag2 = map.containsValue("B");
System.out.println(flag2);

三、HashMap底层源码分析

1.底层存储介绍

HashMap 底层实现采用了哈希表，这是一种非常重要的数据结构。对于我们以后理解很多技术都非常有帮助，因此，非常有必要让大家详细的理解。

数据结构中由数组和链表来实现对数据的存储，他们各有特点。

(1) 数组：占用空间连续。 寻址容易，查询速度快。但是，增加和删除效率非常低。

(2) 链表：占用空间不连续。 寻址困难，查询速度慢。但是，增加和删除效率非常高。

那么，我们能不能结合数组和链表的优点（即查询快，增删效率也高）呢？ 答案就是

“哈希表”。 哈希表的本质就是“数组+链表”。

1.成员变量简介

//默认的初始化容量为16，为2的n次幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 

//最大容量为 2^30
static final int MAXIMUM_CAPACITY = 1 << 30;

//默认的加载因子0.75，乘以数组容量得到的值，用来表示元素个数达到多少时，需要扩容。
//设置0.75时应考虑到，加载因子如果过大，那么等到数组满了以后再去扩容那肯定就来不及的
//如果加载因子过小，那么数组还没存到一定量的元素时就去扩容，这会大大影响数组的空间利用率，浪费空间
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//当链表过长时（链表元素大于8个），链表就会转化为红黑树
static final int TREEIFY_THRESHOLD = 8;

//当红黑树上的元素少于6个时，红黑树会转化为链表
static final int UNTREEIFY_THRESHOLD = 6;

//当链表转化为红黑树，需要数组容量扩容到64，才会转化为红黑树。
static final int MIN_TREEIFY_CAPACITY = 64;

//存放Node节点的数组
transient Node<K,V>[] table;

//存放键值对
transient Set<Map.Entry<K,V>> entrySet;

//统计map中键值对的个数，或者说统计map中的元素个数
transient int size;

//数组扩容阈值
int threshold;

//加载因子
final float loadFactor;					

//普通单向链表节点类
static class Node<K,V> implements Map.Entry<K,V> {
	//key的hash值，put和get的时候都需要用到它来确定元素在数组中的位置
	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;
	}
}

//转化为红黑树的节点类
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
	//当前节点的父节点
	TreeNode<K,V> parent;  
	//左孩子节点
	TreeNode<K,V> left;
	//右孩子节点
	TreeNode<K,V> right;
	//指向前一个节点
	TreeNode<K,V> prev;    // needed to unlink next upon deletion
	//当前节点是红色或者黑色的标识
	boolean red;
	TreeNode(int hash, K key, V val, Node<K,V> next) {
		super(hash, key, val, next);
	}
}	

继承关系

2.数组初始化

在 JDK1.8 的 HashMap 中对于数组的初始化采用的是延迟初始化方式。通过 resize 方法
实现初始化处理。resize 方法既实现数组初始化，也实现数组扩容处理

final Node<K,V>[] resize() {
	Node<K,V>[] oldTab = table;
	int oldCap = (oldTab == null) ? 0 : oldTab.length;
	int oldThr = threshold;
	int newCap, newThr = 0;
	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; // double threshold
	}
	else if (oldThr > 0) 
		newCap = oldThr;
	else {              
		newCap = DEFAULT_INITIAL_CAPACITY;
		newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
	}
	//16*0.75 = 12 然后赋值给threshold
	if (newThr == 0) {
		float ft = (float)newCap * loadFactor;
		newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
				  (int)ft : Integer.MAX_VALUE);
	}
	//threshold = 12，所以当数组元素达到12时，就会令数组扩容
	threshold = newThr;
	@SuppressWarnings({"rawtypes","unchecked"})
		Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
	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)
					newTab[e.hash & (newCap - 1)] = e;
				else if (e instanceof TreeNode)
					((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
				else { // preserve order
					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;
}

3.计算Hash值

(1) 获得 key 对象的 hashcode
首先调用 key 对象的 hashcode()方法，获得 key 的 hashcode 值。

(2) 根据 hashcode 计算出 hash 值(要求在[0, 数组长度-1]区间)
hashcode 是一个整数，我们需要将它转化成[0, 数组长度-1]的范围。我们要
70

求转化后的 hash 值尽量均匀地分布在[0,数组长度-1]这个区间，减少“hash 冲突”

i. 一种极端简单和低下的算法是：
hash 值 = hashcode/hashcode;
也就是说，hash 值总是 1。意味着，键值对对象都会存储到数组索引 1
位置，这样就形成一个非常长的链表。相当于每存储一个对象都会发生“hash
冲突”，HashMap 也退化成了一个“链表”。

ii. 一种简单和常用的算法是（相除取余算法）：
hash 值 = hashcode%数组长度
这种算法可以让 hash 值均匀的分布在[0,数组长度-1]的区间。但是，这
种算法由于使用了“除法”，效率低下。JDK 后来改进了算法。首先约定数
组长度必须为 2 的整数幂，这样采用位运算即可实现取余的效果：hash 值 =
hashcode&(数组长度-1)。

可以看上面飘红的代码块：
计算Hash值主要通过两个部分
1.return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16）
这里是取异或操作 ^ ----异或
具体内容是，例如：
输入456789
看到456789的二进制如下，进行异或运算—相同为0，不同为1
用高16位和底16位进行异或后

2.if ( (p = tab[i = (n - 1) & hash]) == null)
数组长度和hash做与运算&------都为1时为1，其他为0

所以456789就会存入数组中3的位置

4.添加元素

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)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//这里判断一下传入的元素是否相同，主要比较hash值相不相同，对应的key相不相同
e = p;
//判断为true，说明这个节点已经有位置，继续往下走

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) {
//把新节点挂到上个节点上
p.next = newNode(hash, key, value, null);

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//链表转化为红黑树
//函数中还会判断数组容量是否大于64，只有大于64时才会化树
//当小于64时，直接数组扩容
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//e不为null
if (e != null) { // existing mapping for key
//value覆盖
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
//返回旧的value
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;

5.数组扩容

/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
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)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
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) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
75
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//判断数组是否需要扩容，元素个数大于阈值 = 16*0.75 =12 就会扩容 
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//需要扩容就会执行这里的if
if (oldCap > 0) {
//没有超过数组最大上限，就会扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//2倍，大于等于默认值2的4次方，小于最大上限值
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using
defaults
76
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR *
DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft <
(float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//创建新数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
//进行元素的copy，或者元素的移动
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
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;
}
77
} 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
}

总结

HashMap的底层源码并不难，仔仔细细的研究研究都能明白，尤其是刚有点基础的小白，最适合去阅读这种难度没那么大的源码，对提升自己很有帮助。
Hashmap同样也是面试常问的问题，深度掌握底层源码分析还怕hashmap给你拖后腿吗？
看到这里了，点个赞再走吧！！！