引言:
-
Map双列集合大部分人都清楚,我们常用的容器集合也有HashMap,LinkedHashMap,CurrentHashMap等双列集合,使用都很简单但是他底层的数据结构是什么样的,他是如何实现的容器数据存储,以及他的存储过程是什么样的,可能都不是很清楚,今天我们单独挑出我们经常使用的HashMap来简单分析下.(JDK1.8的版本哦)
目录:
-
HashMap的简单使用 -
HashMap内部重要的成员变量以及构成的底层数据结构 -
HashMap的put过程 -
HashMap的resize过程 -
HashMap的问题
带着这些问题我们来一点点去玩懂HashMap
1.HashMap的简单使用
/**
* @author zhangchuang
* @date 2021-12-29 10:57:30
* 使用层面大家看看就好,简单的put和遍历
*/
public class HashMapTest {
public static final Integer INITIAL_TRAVERSAL_VALUE = 10;
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>(INITIAL_TRAVERSAL_VALUE);
for (int i = 0; i < INITIAL_TRAVERSAL_VALUE; i++) {
map.put("i" + i, i);
}
//keySet 方式遍历
Set<String> keys = map.keySet();
for (String key : keys) {
Integer value = map.get(key);
System.out.println("map keySet value:" + value);
}
//entrySet 方式遍历
for (Map.Entry<String, Integer> mapEntry : map.entrySet()) {
Integer value = mapEntry.getValue();
System.out.println("map entrySet value:" + value);
}
//entrySet stream方式遍历
map.forEach((key, value) -> {
System.out.println("map stream value:" + value);
});
}
}
熟悉的朋友应该知道了今天主要就是源码的分析 所以来吧!!!
2.HashMap内部重要的成员变量以及构成的底层数据结构
-
我们先简单看下HashMap 1.2的时候出现实现了Map接口双列集合,我把继承体系图也拿出来了可以看下.
-
然后来分析下他的成员变量以及构造方法
#看DEFAULT_INITIAL_CAPACITY的含义大概应该也能清楚,
#默认的数组初始容量二进制1左移4位的值就是初始容量16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
#二进制1左移30位最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million
#默认负载因子 put过程中达到DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR的值的时候会resize
#根据泊松分布统计学概率计算出来的
#可以理解为在hash桶单个节点hash碰撞出现链表长度达到8的概率已经非常小了
#因此每个碰撞位置的链表长度超过 8 个是几乎不可能的所以0.75比较合适
static final float DEFAULT_LOAD_FACTOR = 0.75f;
#1.8新加的当链表长度达到8的时候并且
static final int TREEIFY_THRESHOLD = 8;
#桶的数组长度大于64的时候会转换为红黑树
static final int MIN_TREEIFY_CAPACITY = 64;
#当链表长度小于6的时候红黑树转换为链表
static final int UNTREEIFY_THRESHOLD = 6;
#数组
transient Node<K,V>[] table;
#键值对集合
transient Set<Map.Entry<K,V>> entrySet;
#map中键值对的个数
transient int size;
#map操作次数(并发修改异常)
transient int modCount;
#下一个要调整大小的大小值（容量*负载系数）(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR)
int threshold;
#负载因子
final float loadFactor;
#构造方法
#initialCapacity 可以指定初始容量
#loadFactor 和初始的负载因子
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;
this.threshold = tableSizeFor(initialCapacity);
}
-
根据上面的成员变量我们可以分析出HashMap主要的底层数据结构(数组(默认容量为16,负载因子为0.75)+链表+链表达到一定阈值(8,64)之后会转换为红黑树) -
猜测HashMap底层数据结构是由(数组+链表+红黑树)的hash表的数据结构
3.HashMap的put过程
-
既然知道了HashMap的数据结构是hash表(数组链表红黑树的结构)那我们来看下他的数据是如何添加到hash表里的
#HashMap的put方法
public V put(K key, V value) {
#主要是通过putval这个方法去添加数据的
#hash(key) 是通过key 计算hash值
return putVal(hash(key), key, value, false, true);
}
#可以简单看下
static final int hash(Object key) {
int h;
#将key hashcode之后无符号右移16位之后进行的异或运算算出来的hash值
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* @param hash #hash值
* @param key #key
* @param value #value
* @param onlyIfAbsent #新值是否替换旧值
* @param evict #和put过程没大关系
**/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
#首先进来先判断这个table数组是否有创建过没有的话直接resize
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
#然后如果已经被创建了那么就判断hashcode之后的key值知否在当前hash表中的位置是null
if ((p = tab[i = (n - 1) & hash]) == null)
#如果是的话直接去新建节点添加数据.
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
#这里其实就是在计算要插入的key和之前的key是否相等是的话就直接吧p赋值给e后面会操作的
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
#此时说明p已经树化，调用红黑树的方法添加到指定位置
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
#key的hash值不相等 走到这里就证明发生了hash碰撞而且不是树节点就要往链表的尾节点中添加值了
#死循环
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
#这边的意思其实就是往链表尾节点中添加一个新的节点
p.next = newNode(hash, key, value, null);
#这是树化的操作,新增节点之后是否达到树化
#binCount是循环的长度从0递增循环,就代表了循环几次链表长度就是多少
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
#此时在链表找尾节点时，发现了和新插入节点完全一致的key,直接break 说明节点已经添加了
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
#这边就是赋值操作
if (e != null) { // existing mapping for key
V oldValue = e.value;
#onlyIfAbsent可以表示发生hash碰撞的时候执行替换操作
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
#然后操作次数加一
++modCount;
#查看添加数据后的数组长度是否大于当前的阈值是的话就直接resize
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
-
看完源码我们来通过流程图来捋一下思路,还是老样子我帮你拆代码对应流程图
-
进来先判断hashtable的值去决定扩容还是直接去插入值
#首先进来先判断这个table数组是否有创建过没有的话直接resize
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
-
然后如果hash之后的key值在数组中的节点数据是null的话去选择直接插入
#然后如果已经被创建了那么就判断hashcode之后的key值知否在当前hash表中的位置是null
if ((p = tab[i = (n - 1) & hash]) == null)
#如果是的话直接去新建节点添加数据.
tab[i] = newNode(hash, key, value, null);
-
然后走到下面说明已经发生了hash碰撞,判断是否是红黑树节点
#此时说明p已经树化，调用红黑树的方法添加到指定位置
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
-
如果既不是树结构也发生了hash碰撞的话那么我们该遍历链表,往链表中添加值了
#key的hash值不相等 走到这里就证明发生了hash碰撞而且不是树节点就要往链表的尾节点中添加值了
#死循环
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
#这边的意思其实就是往链表尾节点中添加一个新的节点
p.next = newNode(hash, key, value, null);
#这是树化的操作,新增节点之后是否达到树化
#binCount是循环的长度从0递增循环,就代表了循环几次链表长度就是多少
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
#此时在链表找尾节点时，发现了和新插入节点完全一致的key,直接break 说明节点已经添加了
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
-
最后根据是根据新建的节点还是之前的节点value覆盖进行赋值的操作
#这边就是赋值操作
if (e != null) { // existing mapping for key
V oldValue = e.value;
#onlyIfAbsent可以表示发生hash碰撞的时候执行替换操作
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
#然后操作次数加一
++modCount;
#查看添加数据后的数组长度是否大于当前的阈值是的话就直接resize
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
hashmap的拆分如此,总体上来说就是计算key的hash值判断数组中改hash位置是否有值,没有直接插入有的话判断value是否相等如果不想等的话就证明发生了hash碰撞,之后就判断节点是否为树节点最后如果都不是的话就会往链表的尾部插入数据,然后中途检测是否需要resize和转换红黑树!!!(简单理解下慢慢看,自己也去源码中跟着走一走)
4. HashMap的resize过程
-
还感觉行吗,行的话下面又是大范围的源码resize(扩容的过程) -
我都有点写不动了!!!! 但是影响看源码嘛? 不可能的 走着!!!!
-
来吧!! -
下面这一片代码主要是数组达到阈值之后resize(扩容的过程)在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;
#之后判断数组的长度是否是首次扩容
if (oldCap > 0) {
#不是首次扩容的话如果扩容的数组长度已经超过了设定的最大扩容长度就直接出去
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
#如果确认需要扩容数组的话就将之前的数组左移1位(等同于*2)就是新的数组长度
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
#若没有经历过初始化，并且在使用时通过构造函数指定了initialCapacity则table大小为threshold
#记得initialCapacity这个参数嘛,在构造方法的时候指定的,可以翻上去看下是否指定了这个初始容量如果指定了初始容量那么就用初始容量
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
#如果没有指定的话就是默认的容量*负载因子
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) {
#根据扩容后的数组长度遍历,ok开始了!!!!!!!!
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
#遍历 取出之前数组对应角标下的链表
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
#e.next代表链表的下一个节点,如果没有值就代表只有一个根节点,
#那么直接往数组中添加值就好了
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);
#将新链表丢到hash表(桶)中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
-
整体的resize过程就结束了,总结一下 -
首先判断桶是否被创建,没有的话看是否有指定桶的长度,然后resize -
如果桶已经被创建了,走到是扩容的话根据当前桶的长度和负载因子去扩容<<1 -
之后循环遍历old链表之后之后放到new链表中
5.HashMap的问题
-
remove并发修改异常 -
以及线程安全问题
原文始发于微信公众号（闯sir9）：HashMap 来剖析源码
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/20651.html
