HashMap源码分析
HashMap源码分析
吐槽一下先
相信作为一名以Java为基础的开发者，在项目中使用HashMap还是很频繁的。但是仅仅会使用还是不够的，需要我们了解它的底层原理。都说面试是“面试造航母，入职拧螺丝”，但是我们至少得知道要选什么型号的螺丝、知道它的内部构造，才能把这颗螺丝拧紧、拧牢！
哈希表，数组链表？
众所周知，数据结构中有数组和链表两种结构来存储数据，它俩各有特点。
首先来提一下数组，它的存储空间是连续的，也是会一段连续的内存，因此它的空间复杂度很大。有利就有弊，它的时间复杂度却是很小，为O(1)。数组的特点就是：寻址易，查、删难；
相比于数据，链表的存储空间就比较散列了，占用内存比较宽松，因此空间复杂度比较小。但是它的时间复杂度可就悬了，为0(N)。链表的特点是：寻址难，查、删易，和数组刚好站在了对立面上。
于是，为了取其精华、去其糟粕，哈希表应运而生。既满足了数据查找，又对空间占用进行了优化。我想大家对上面这张图都十分熟悉了（请原谅我是个盗图党）。哈希表可以说是数组链表，是一种关联数组的数据查找。底层还是数组，但是数组的每一项都是一个链表，在数据快速查找方面被广泛应用。
插入HashMap中的元素位置，是用hash(key)%len来计算的。简单点说就是用key的hash值对数组长度取模，这样通过计算的出来的元素位置是非常准确的。对于碰撞问题，这里采用了链地址法通过next来解决。
举个栗子，index=hash(key)%len；如果A和B的index相同，会通过next解决。B.next = A,Entry[0] = B；这样，B就理所当然的插入到了该条链表中A的后面，也就是说数组存储的是最后插入的元素。
解决hash冲突
1、开放定址法
2、再哈希法
3、链地址法
4、建立一个公共溢出区
HashMap源码分析
hashmap实现了Map接口，继承AbstractMap。其中Map接口定义了键值对的映射规则，AbstractMap提供了Map接口的骨干实现。
Map接口源码
public interface Map<K, V> {
int size();
boolean isEmpty();
boolean containsKey(Object var1);
boolean containsValue(Object var1);
V get(Object var1);
V put(K var1, V var2);
V remove(Object var1);
void putAll(Map<? extends K, ? extends V> var1);
void clear();
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();
boolean equals(Object var1);
int hashCode();
default V getOrDefault(Object key, V defaultValue) {
throw new RuntimeException("Stub!");
}
default void forEach(BiConsumer<? super K, ? super V> action) {
throw new RuntimeException("Stub!");
}
default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
throw new RuntimeException("Stub!");
}
default V putIfAbsent(K key, V value) {
throw new RuntimeException("Stub!");
}
default boolean remove(Object key, Object value) {
throw new RuntimeException("Stub!");
}
default boolean replace(K key, V oldValue, V newValue) {
throw new RuntimeException("Stub!");
}
default V replace(K key, V value) {
throw new RuntimeException("Stub!");
}
default V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
throw new RuntimeException("Stub!");
}
default V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
throw new RuntimeException("Stub!");
}
default V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
throw new RuntimeException("Stub!");
}
default V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
throw new RuntimeException("Stub!");
}
public interface Entry<K, V> {
K getKey();
V getValue();
V setValue(V var1);
boolean equals(Object var1);
int hashCode();
static default <K extends Comparable<? super K>, V> Comparator<Map.Entry<K, V>> comparingByKey() {
throw new RuntimeException("Stub!");
}
static default <K, V extends Comparable<? super V>> Comparator<Map.Entry<K, V>> comparingByValue() {
throw new RuntimeException("Stub!");
}
static default <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
throw new RuntimeException("Stub!");
}
static default <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
throw new RuntimeException("Stub!");
}
}
这里我们着重关注keySet、values和Entry这三个。
keySet
所有key的集合，可以通过set的形式来设置，不可重复。
values
map中所有value的集合，以Collection的形式来保存，可重复。
Entry
Map接口中的静态内部接口，代表k-v键值对的映射。Map.entrySet可获取到一组Entry的集合，也不可重复。
HashMap成员变量
//***
private static final long serialVersionUID = 362498820763181265L;
//默认的初始容量
static final int DEFAULT_INITIAL_CAPACITY = 16;
//最大容量
static final int MAXIMUM_CAPACITY = 1073741824;
//加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75F;
//树形阈值 当使用 树 而不是列表来作为桶时使用。必须比2大
static final int TREEIFY_THRESHOLD = 8;
//非树形阈值：也是 1.8 新增的，扩容时分裂一个树形桶的阈值
static final int UNTREEIFY_THRESHOLD = 6;
//数的最小容量 避免冲突
static final int MIN_TREEIFY_CAPACITY = 64;
//链表数组
transient HashMap.Node<K, V>[] table;
//缓存的键值对集合
transient Set<Entry<K, V>> entrySet;
//键值对的数量
transient int size;
//修改次数
transient int modCount;
//这块是阈值 用于判断是否需要调整HashMap的容量（threshold = 容量*加载因子）
int threshold;
//哈希表的加载因子
final float loadFactor;
通过这些变量，我们可以清楚的看到默认初始容量以及加载因子的大小。其中，这个 loadFactor加载因子表示哈希表中元素的填满程度。loadFactor越大，表示我哈希表中放置的元素越多，空间利用的越充分，但是因此带来的冲突就越多。
当其中的元素填充到达一个临界值之后，就会触发扩容机制。
啥是扩容机制？
上面我们提到了，为了降低碰撞冲突，当hashmap中的数组长度到达一定长度就会触发扩容机制。当然，这是一个相当“耗时”的操作，需要把所有元素rehash来重新计算元素在数组中的位置并将内容复制到扩容后的新容器中。这其中的临界值取决于默认初始容量与加载因子的乘积，即16 * 0.75=12。
这里的Capacity代表的就是bucket大小，当bucket中的entries的数目大于capacity*load factor时就需要调整bucket的大小为当前的2倍。
HashMap构造函数
这里HashMap提供了3个构造函数。
HashMap()：构造一个具有默认初始容量16和默认加载因子0.75的空 HashMap。
HashMap(int initialCapacity)：构造一个带指定初始容量和默认加载因子0.75的空 HashMap。
HashMap(int initialCapacity, float loadFactor)：构造一个带指定初始容量和加载因子的空 HashMap。
public HashMap(int var1, float var2) {
//输入判断
if (var1 < 0) {
throw new IllegalArgumentException("Illegal initial capacity: " + var1);
} else {
if (var1 > 1073741824) {
var1 = 1073741824;
}
//输入判断
if (var2 > 0.0F && !Float.isNaN(var2)) {
this.loadFactor = var2;
this.threshold = tableSizeFor(var1);
} else {
throw new IllegalArgumentException("Illegal load factor: " + var2);
}
}
}
//指定的容量的哈希表，加载因子的0.75
public HashMap(int var1) {
this(var1, 0.75F);
}
//空的哈希表 初始容量是16 加载因子是0.75
public HashMap() {
this.loadFactor = 0.75F;
}
//创建一个内容为参数var1的哈希表
public HashMap(Map<? extends K, ? extends V> var1) {
this.loadFactor = 0.75F;
this.putMapEntries(var1, false);
}
其中当设置初始容量和加载因子的时候，会调用tableSizeFor(var1)这个方法。然后继续跟进到这个方法中：
static final int tableSizeFor(int var0) {
int var1 = var0 - 1;
var1 |= var1 >>> 1;
var1 |= var1 >>> 2;
var1 |= var1 >>> 4;
var1 |= var1 >>> 8;
var1 |= var1 >>> 16;
return var1 < 0 ? 1 : (var1 >= 1073741824 ? 1073741824 : var1 + 1);
}
根据指定容量设置阈值（默认阈值16），该方法经过若干次无符号右移求异运算，得到了2的N次方的容量。然而jdk版本不同，对阈值的计算方式也不尽相同。从下面这个resize函数中，我们可以看到各版本针对阈值的计算方式：
final HashMap.Node<K, V>[] resize() {
HashMap.Node[] var1 = this.table;
int var2 = var1 == null ? 0 : var1.length;
int var3 = this.threshold;
int var5 = 0;
int var4;
//如果有容量，表示map已经有元素了
if (var2 > 0) {
if (var2 >= 1073741824) {
this.threshold = 2147483647;
return var1;
}
//newCap = oldCap << 1，容量翻倍
if ((var4 = var2 << 1) < 1073741824 && var2 >= 16) {
var5 = var3 << 1;
}
} else if (var3 > 0) {
var4 = var3;
} else {
var4 = 16;
var5 = 12;
}
if (var5 == 0) {
float var6 = (float)var4 * this.loadFactor;
var5 = var4 < 1073741824 && var6 < 1.07374182E9F ? (int)var6 : 2147483647;
}
this.threshold = var5;
HashMap.Node[] var14 = (HashMap.Node[])(new HashMap.Node[var4]);
this.table = var14;
//最开始没往里面加东西的时候
//上面的操作就是如果你初始化的时候带了参数的时候HashMap(int initialCapacity, float loadFactor)）
//newCap就是你的initialCapacithreshold就是（int)(initialCapactiy * loadFactor)
//如果没带参数的话，按照默认的算initialCapacity = 16, threshold = 12
//如果有元素了，你们直接扩容2倍。如果oldCap>=DEFAULT_INITIAL_CAPACITY了，那么threshold也扩大2倍。
if (var1 != null) {
for(int var7 = 0; var7 < var2; ++var7) {
HashMap.Node var8;
if ((var8 = var1[var7]) != null) {
var1[var7] = null;
if (var8.next == null) {
var14[var8.hash & var4 - 1] = var8;
} else if (var8 instanceof HashMap.TreeNode) {
//原来的结点转换成红黑树
((HashMap.TreeNode)var8).split(this, var14, var7, var2);
} else {
HashMap.Node var9 = null;
HashMap.Node var10 = null;
HashMap.Node var11 = null;
HashMap.Node var12 = null;
HashMap.Node var13;
do {
var13 = var8.next;
if ((var8.hash & var2) == 0) {
if (var10 == null) {
var9 = var8;
} else {
var10.next = var8;
}
var10 = var8;
} else {
if (var12 == null) {
var11 = var8;
} else {
var12.next = var8;
}
var12 = var8;
}
var8 = var13;
} while(var13 != null);
if (var10 != null) {
var10.next = null;
var14[var7] = var9;
}
if (var12 != null) {
var12.next = null;
var14[var7 + var2] = var11;
}
}
}
}
}
return var14;
}
jdk1.6：超过默认初始容量*加载因子就会激发扩容机制
jdk1.7：当数量>容量时初次扩容，以后就数量>容量 * 加载因子再次扩容
jdk1.8：当发现现在的桶的占有量已经超过了容量 * 负载因子时候，进行扩容，直接扩容桶的数量为之前的2倍，并且重新调用hash方法，重新计算下标，然后再把之前的结点放到数组里面
集合添加到哈希表中
final void putMapEntries(Map<? extends K, ? extends V> var1, boolean var2) {
int var3 = var1.size();
if (var3 > 0) {
//如果数组为空的情况，初始化参数
if (this.table == null) {
float var4 = (float)var3 / this.loadFactor + 1.0F;
int var5 = var4 < 1.07374182E9F ? (int)var4 : 1073741824;
if (var5 > this.threshold) {
this.threshold = tableSizeFor(var5);
}
//数组不为空，超过阈值就扩容
} else if (var3 > this.threshold) {
this.resize();
}
Iterator var8 = var1.entrySet().iterator();
while(var8.hasNext()) {
Entry var9 = (Entry)var8.next();
Object var6 = var9.getKey();
Object var7 = var9.getValue();
//通过hash（）计算位置，然后复制
this.putVal(hash(var6), var6, var7, false, var2);
}
}
}
HashMap结点
static class Node<K, V> implements Entry<K, V> {
//哈希值，就是位置
final int hash;
//键
final K key;
//值
V value;
//下个结点指针
HashMap.Node<K, V> next;
Node(int var1, K var2, V var3, HashMap.Node<K, V> var4) {
this.hash = var1;
this.key = var2;
this.value = var3;
this.next = var4;
}
public final K getKey() {
return this.key;
}
public final V getValue() {
return this.value;
}
public final String toString() {
return this.key + "=" + this.value;
}
public final int hashCode() {
return Objects.hashCode(this.key) ^ Objects.hashCode(this.value);
}
public final V setValue(V var1) {
Object var2 = this.value;
this.value = var1;
return var2;
}
public final boolean equals(Object var1) {
if (var1 == this) {
return true;
} else {
if (var1 instanceof Entry) {
Entry var2 = (Entry)var1;
if (Objects.equals(this.key, var2.getKey()) && Objects.equals(this.value, var2.getValue())) {
return true;
}
}
return false;
}
}
}
这里面的next，是处理碰撞的关键！
put函数
public V put(K var1, V var2) {
//对key做hashCode（）做hash
return this.putVal(hash(var1), var1, var2, false, true);
}
final V putVal(int var1, K var2, V var3, boolean var4, boolean var5) {
HashMap.Node[] var6 = this.table;
int var8;
//如果当前哈希表为空，新建一个，var8指桶的最后一个位置
if (this.table == null || (var8 = var6.length) == 0) {
var8 = (var6 = this.resize()).length;
}
Object var7;
int var9;
//如果要插入的位置没有元素，新建一个结点
if ((var7 = var6[var9 = var8 - 1 & var1]) == null) {
var6[var9] = this.newNode(var1, var2, var3, (HashMap.Node)null);
} else {
//如果要插入的桶已经有元素，替换
Object var10;//被替换的元素
label79: {
Object var11;
if (((HashMap.Node)var7).hash == var1) {
var11 = ((HashMap.Node)var7).key;
if (((HashMap.Node)var7).key == var2 || var2 != null && var2.equals(var11)) {
var10 = var7;
break label79;
}
}
if (var7 instanceof HashMap.TreeNode) {
var10 = ((HashMap.TreeNode)var7).putTreeVal(this, var6, var1, var2, var3);
} else {
int var12 = 0;
while(true) {
var10 = ((HashMap.Node)var7).next;
if (((HashMap.Node)var7).next == null) {
((HashMap.Node)var7).next = this.newNode(var1, var2, var3, (HashMap.Node)null);
//如果这个桶的链表的个数大于等于8，树化
if (var12 >= 7) {
this.treeifyBin(var6, var1);
}
break;
}
//如果找到要替换的结点就停止
if (((HashMap.Node)var10).hash == var1) {
var11 = ((HashMap.Node)var10).key;
if (((HashMap.Node)var10).key == var2 || var2 != null && var2.equals(var11)) {
break;
}
}
var7 = var10;
++var12;
}
}
}
if (var10 != null) {
Object var13 = ((HashMap.Node)var10).value;
if (!var4 || var13 == null) {
((HashMap.Node)var10).value = var3;
}
this.afterNodeAccess((HashMap.Node)var10);
return var13;
}
}
//超出阈值，扩容
++this.modCount;
if (++this.size > this.threshold) {
this.resize();
}
this.afterNodeInsertion(var5);
return null;
}
总结以上过程分为以下步骤：
1、先hash(key)，借此来计算位置坐标。
2、若无碰撞就直接放进桶中。
3、若有碰撞就放在该位置链表的后面
4、如果链表中结点个数>7之后就转换为红黑树
5、如果结点存在，就替换旧值。
6、超出阈值，立即扩容。
get函数
public V get(Object key) {
Node<K,V> e;
//先计算hash值
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
//tab是hash表，n为hash的长度
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 第一个直接命中
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 未命中，挨个找
if ((e = first.next) != null) {
// 在树中get
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 在链表中get
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
在整个get的过程中，分为以下步骤：
1、跟put一样还是先计算key的hash值
2、查看能否在第一个桶中直接命中，判断条件中还用到了equals方法比较
3、如果有冲突就直接遍历
4、在桶的链表或树结构中找
HashMap的遍历
1.通过Map.keySet遍历key和value
for (String key : map.keySet()) {
System.out.println("key= "+ key + " and value= " + map.get(key));
}
2.通过Map.entrySet使用iterator遍历key和value
Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry<String, String> entry = it.next();
System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}
3.通过Map.entrySet遍历key和value。容量大时，推荐这种
for (Map.Entry<String, String> entry : map.entrySet()) {
System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}
4.通过Map.values()遍历所有的value，但不能遍历key
for (String v : map.values()) {
System.out.println("value= " + v);
}
汇总一些面试题
1、hashmap有啥特点，什么时候会用到？
hashmap实现了Map接口，继承AbstractMap。其中Map接口定义了键值对的映射规则，AbstractMap提供了Map接口的骨干实现。其中key不可重复，value可重复可null。hashmap里面存储Entry(hash, key, value, next)对象，并将其作为一个结点。
2、HashMap是否线程安全？
HashMap没有使用sychronized同步关键字，在put的时候，无法做到线程同步，当多个线程在插入数据时，如果发生了哈希碰撞，可能会造成数据的丢失。插入的元素超过了容量（由负载因子决定）的范围就会触发扩容操作，就是rehash，这个会重新将原数组的内容重新hash到新的扩容数组中，在多线程的环境下，可能造成闭环链表，导致在get时会出现死循环，所以HashMap是线程不安全的。
3、怎样保证HashMap线程安全？
可以从Hashtable，ConcurrentHashMap，Synchronized Map这3个方面回答
4、HashMap工作原理是什么？
主要说一下hash(key)对数组长度取模计算坐标位置、桶碰撞和扩容机制等。原理知道了就行，答案不是死的。
5、扩容机制？
分版本描述
6、HashMap中的红黑树？
桶链表中的结点数量>8的时候就会将链表结构转换为红黑树结构，查找效率更高…
7、为什么要重写hashcode和equals方法？
在HashMap的k存自定义对象，为啥一定要重写hashcode和equals两个方法？