【Java基础干货】HashMap源码剖析
2021/5/16 1:25:31
本文主要是介绍【Java基础干货】HashMap源码剖析，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
微信公众号：Duffy说码
如果你觉得这篇文章对你你有帮助，欢迎关注：）
本文所有源码来自JDK1.8
Hashmap简介
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
Hashmap继承AbstractMap,现实了Map、Cloneable、Serializable接口,此实现提供所有可选的映射操作，并允许key为null和value为null。
假设散列函数在桶之间均匀地散列元素，该实现为基本操作（get和put）提供了恒定时间复杂度O(1)。对Collection的遍历的时间与HashMap实例的“容量”（桶的数量）加上其大小（键 - 值映射的数量）有关，因此，如果迭代性能看的很重要，则不要将初始容量设置得太高（或负载因子太低）。
HashMap有两个影响其性能的参数：初始容量和负载因子。容量是哈希表中的桶数，初始容量只是创建哈希表时的容量。加载因子是在自动增加容量之前允许哈希表获取的最大程度数量的度量。当哈希表中的条目数超过加载因子和当前容量的乘积时，哈希表将被扩容（即重建内部数据结构），以便哈希表具有大约两倍的桶数。
作为一般规则，默认加载因子（0.75）在时间和空间成本之间提供了良好的权衡。较高的值会减少空间开销，但会增加查找成本（反映在HashMap类的大多数操作中，包括get和put）。在设置其初始容量时，应考虑映射中的预期条目数及其加载因子，以便最小化重散列操作的数量。
JDK1.8HashMap底层结构为为数组+链表/红黑树，而之前版本为数组+链表的结构。
核心特征：
- 自动扩容：put方法里有resize()方法。
- 初始化与懒加载：默认大小是16，第一次put时才分配内存空间，加载因子默认为0.75。
- 哈希计算：1.8版本hashode由原hashcode高低位相与构成，扰动函数以减少冲突。
- 位运算：（2的幂次方-1）&&hashcode ，减少计算复杂度。
- 并发处理：1.7版本是采用头插法，多线程会出现值错乱，死循环（扩容前A->B，扩容后A<->B），1.8采用尾插法。
常用方法函数
面试常见问题
1.HashMap与Hashtable、ConcurrentHashMap区别
2.key可以为null吗？若为null如何存储呢
3.是如何扩容的，扩容时会出现哪些问题？
4.put、get详细过程
5.HashMap是线程安全的吗？如何保证线程安全？
6.HashMap如何初始化？
7.负载因子默认是多少？小了或大了会怎么样
8.hash冲突如何处理？
9.如何遍历的？有哪几种方法
一般面试都会考察基础知识，而HashMap正是基础知识中常用的数据结构，上面这些问题的答案都可以从源代码中找到，吃透源代码，不仅可以更好理解运用，而且面试也不用担心了。
源码分析
/**
* 默认初始容量为16，必须为2的整数幂
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 允许的最大容量为1<<30
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认负载因子为0.75，当负载因子过大，对空间利用更充分，然而查找效率降低；当负载
* 因子过小，hashMap的数据过于稀疏，空间造成浪费
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* jdk1.8新增，链表中元素个数大于8后变为红黑树
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 这个值应该小于TREEIFY_THRESHOLD，默认红黑树中元素个数小于6后变为链表
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 当桶中bin变为红黑树时最小的数组长度.
* (Otherwise the table is resized if too many nodes in a bin.)
* 至少是 TREEIFY_THRESHOLD 的4倍以避免冲突
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
*数组表在第一次使用的时候进行初始化，必要的时候进行扩容，数组大小都是2的整数幂
*Node为存储的数据类型
*/
transient Node<K,V>[] table;
/**
* 每一对(key,Value)相当于一个Entry,为Entry集合
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* map中（Key,Value）对个数
*/
transient int size;
/**
* 指已经结构性改动的次数。结构性改动是指HashMap中元素数量的改变，或者内在结构的
* 改变，如rehash.具有fail-fast机制,遍历的时候发生结构性改动就会抛出
* ConcurrentModificationException，使其他线程不能修改正在被iterator遍历的
* HashMap
*/
transient int modCount;
/**
* The next size value at which to resize (capacity * load factor).
* 元素个数到达这个阈值时进行扩容，即数组长度*负载因子
*/
int threshold;
/**
* 负载因子
* @serial
*/
final float loadFactor;
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;//hash值 final
final K key;//key值 为final，可以为null
V value;//value值 ,可以为null
Node<K,V> next;//指向下一个元素
public final int hashCode() {
//每个键值对的hashCode计算是key的hashCode与value的hashCode异或
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
......
}
以上是HashMap的定义的默认参数和字段
HashMap构造函数
有四种方式
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0) /**指定初始容量 < 0抛出IllegalArgumentException */
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
/**指定初始容量*/
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
/**负载因子小于0或不是数字时，抛出IllegalArgumentException*/
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
/**输入容量大小*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**无参构造函数*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
/**构造一个和指定Map有相同映射的HashMap，负载因子为0.75*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/**主要功能是返回一个比给定整数大且最接近的2的幂次方整数，**/
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;
}
-----------------------------------------------------------------------
/*JDK1.7*/
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
......
}
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
在JDK1.7和JDK 1.8中，HashMap初始化这个容量的时机不同。JDK1.8中，在调用HashMap的构造函数定义HashMap的时候，就会进行容量的设定。而在JDK 1.7中，要等到第一次put操作时才进行这一操作。
hash计算
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
计算key的hash值，不是简单地使用key.hashCode,而是key.hashCode()与自己右移16位相异或得到结果，好处是可以将hashcode高位和低位的值进行混合做异或运算，而且混合后，低位的信息中加入了高位的信息，这样高位的信息被变相的保留下来。下表举例展示
可以看到异或结果是高位和低位共同作用得到的，得出的值更均匀全面，那么生成的hash值的随机性会增大，减少hash冲突
put操作
/**
* 调用putVal,
*
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* hash key的hash值
* key 将要put的key
* value 将要put的key的value
* onlyIfAbsent 若是true,不会改变已存在的value值，默认是false
* evict 如果false, 则数组正在创建，默认为true
* return 返回原先的值, 如果原先没有值则返回null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab;
Node<K,V> p; //插入到table下标i处的Node
int n;//底层table长度
int i;//插入到table的下标
//如果table为空或长度为0，进行resize，table长度为n
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);
//否则在table[i]发生碰撞
else {
Node<K,V> e; //Node中间变量
K k;//key中间变量
//table[i]位置的元素key与将put的元素key是一致的，e为原先的Node将返回
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) {
//链表中没有找到相同key值的元素，链表尾插入新建的Node
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
// 如果链表中Node个数大于等于7则链表变为红黑树，跳出循环
treeifyBin(tab, hash);
break;
}
//链表中找到相同key值的元素，跳出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//
if (e != null) {
// 记录原先的Node中对应的value
V oldValue = e.value;
//当onlyIfAbsent为false或原先value为null时，可替换掉
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
//put方法结束，替换原有value
return oldValue;
}
}
//改动次数+1
++modCount;
// 新添加了Node,判断是否需要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
//put方法结束，添加了新节点
return null;
}
注1：
Key的hash值与n-1相与（n一直是2的幂，如16，那么n-1的二进制为1111 与hash值 低四位相与，得到的结果范围0~15正是table大小范围，快速找到在table 中的index），相当于取余操作如果为空,说明此槽还没有Node，添加此Node
get操作
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//table不为空且table大小大于0，且table[i]处存在Node,否则说明HashMap中不
//存在此key的Node，返回null结束
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//table[i]处正是要找的Node，返回此Node结束
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//在红黑树或链表结构中寻找对应Node,找到则返回Node，结束；直到遍历完此
//table[i]上所有Node也没有找到，返回null,结束
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
resize操作
扩容resize就把原先map中的所有元素放到更大容量的新数组中，当map中key的数量达到阈值时自动执行，jdk1.7和jdk1.8中resize方法有很大不同，效率也提高了很多，来一起阅读源码~
JDK1.7
void resize(int newCapacity) {
//保存旧的table
Entry[] oldTable = table;
//保存旧table的长度
int oldCapacity = oldTable.length;
//当旧长度已经达到最大容量了，设阈值为Integer.MAX_VALUE，结束
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//构建newCapacity大小的的新table
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
//避免扩容后超过最大容量
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//遍历table中每一个桶
for (Entry<K,V> e : table) {
while(null != e) {
//单链表通过保存下一节点转移头指针，不然转移后链表就丢了
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
//e要插入带链表的头部所以先用e.next指向新的第一个元素
e.next = newTable[i];
//新表的头指针任然指向e没转移前的第一个元素，需要将新表头指针指向e
newTable[i] = e;
//转移e的下一个节点
e = next;
}
}
}
对transfer函数做进一步说明
1.对table数组中元素遍历
2.对链表上每一个节点遍历，用next取得要取得要转移那个元素的下一个，将e转移到新的Hash头部，使用头插法插入节点
3.循环2，直到链表中所有节点全部转移
4.循环1，直到table中所有数组全部转移
JDK1.7中rehash的时候，由于采用的是头插法，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置，如1->2->3变成3->2->1，且多线程同时进行put操作发生扩容可能会产生死循环；同时而JDK1.8采用尾插法，不会产生倒置和死链情况，以下是JDK1.8源码分析
JDK1.8
final Node<K,V>[] resize() {
//保存当前table
Node<K,V>[] oldTab = table;
//保存当前table的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//保存当前阈值
int oldThr = threshold;
int newCap, newThr = 0;
//resize()是在size > threshold时被调用
if (oldCap > 0) {
//当前容量大于最大容量，则阈值设为Integer.MAX_VALUE
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//新容量翻倍，且小于最大容量，在大于初始容量前提下
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//阈值也翻倍
newThr = oldThr << 1;
}
//resize()在table为空时调用，oldCap不大于0且oldThr大于0
else if (oldThr > 0)
newCap = oldThr;
//resize()在table为空时调用，oldCap不大于0且oldThr不大于0
else {
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) {
//遍历整个old table，将old table上Node reHash到new table上
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//old table[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);
//链表结构，与jdk1.7不同
else { // 保持顺序，初始化为null
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//Node的e.hash & oldCap为0或1进行分成两个链表,省去了重新计算hash值得消耗，采用尾插法
do {
next = e.next;
//最高位为0，在下标不变的链表上增加Node
if ((e.hash & oldCap) == 0) {
//添加链表第一个Node
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//最高位为1，在下标改变的链表上增加Node
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//链表中不为空Node后面得添加null，且链表头指针放在新桶的相同下标j
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//链表中不为空Node后面得添加null，且链表头指针放在新桶的原先下标j+oldCap的位置
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
//返回新table,结束
return newTab;
}
举例说明JDK1.8是如何扩容的，见下表。
如上表扩容之后，n会翻倍，（n-1）的mask为会多出一个高位bit1，这个bit来决定新下标位置，插入图解释
因此，我们在HashMap扩容的时候，不需要像JDK1.7的实现那样重新计算每个key的hash值，只需要看看原来的hash值新增的高位bit与（n-1）相与是1还是0就好了，若为0则放在newTable相同下标中，为1则新下标为原下标+oldCap位置。
遍历操作
HashMap<Integer, String> hashMap = new HashMap<>();
hashMap.put(1,"1");
hashMap.put(2,"2");
hashMap.put(3,"3");
//1 遍历key集合
for (Object key : hashMap.keySet()) {
System.out.println(key);
}
//2 遍历value集合
for (String value : hashMap.values()) {
System.out.println(value);
}
//3 entry集合
for (Map.Entry<Integer, String> entry : hashMap.entrySet()) {
System.out.println(entry.getKey()+" "+entry.getValue());
}
//4 entrySet迭代器
Iterator<Map.Entry<Integer, String>> iterator = hashMap.entrySet().iterator();
while (iterator.hasNext()){
Map.Entry<Integer, String> entry = iterator.next();
System.out.println(entry.getKey()+" "+entry.getValue());
}
与HashTable比较
1.HashMap与HashTable都实现了Map、Cloneable、Serialiable接口，HashMap继承的是AbstractMap类，而HashTable继承的是Dictionary类。
2.HashMap的key和value可以为null,而HashTable不可以。
3.HashMap是非synchronized的，而HashTable是synchronized,即是线程安全的，单线程环境下较慢，此时更适合使用HashMap。可通过Collection.sychronizeMap(hashMap)的方式强加synchronize锁，或者选择使用并发包中ConcurrHashMap(以后详讲)实现线程安全。
4.HashMap默认舒适大小为16，扩容将会创建比原来HashMap大两倍数组大小,；而HashTable默认大小为11，扩容方式为2*old+1 。
5.HashMap的迭代器（Iterator）是fail-fast,而HashTabled的迭代器是enumeration（列举）
官方文档：
https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html
这篇关于【Java基础干货】HashMap源码剖析的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-11-27消息中间件底层原理资料详解
- 2024-11-27RocketMQ底层原理资料详解：新手入门教程
- 2024-11-27MQ底层原理资料详解：新手入门教程
- 2024-11-27MQ项目开发资料入门教程
- 2024-11-27RocketMQ源码资料详解：新手入门教程
- 2024-11-27本地多文件上传简易教程
- 2024-11-26消息中间件源码剖析教程
- 2024-11-26JAVA语音识别项目资料的收集与应用
- 2024-11-26Java语音识别项目资料：入门级教程与实战指南
- 2024-11-26SpringAI：Java 开发的智能新利器
