游客您好
第三方账号登陆
  • 点击联系客服

    在线时间:8:00-16:00

    客服电话

    020-85534346

    电子邮件

    81058337@qq.com
  • 码云社APP

    随时掌握码云社动态

  • 扫描二维码

    关注砺锋微信公众号

容器类源码解析系列—— HashMap 源码分析(最新版)

发布时期:2019-5-24 15:52
阅读:1128 回复:19

前言本篇文章是《Java容器类源码解析》系列的第三篇文章,主要是对HashMap的源码实现进行分析。要点HashMap内部是基于数组加链表结构来实现数据存储,这句话在jdk1.8版本之后,就不准确了。因为在JDK1.8版本之后,Ha ...

前言

本篇文章是《Java容器类源码解析》系列的第三篇文章,主要是对HashMap的源码实现进行分析。

要点

  • HashMap 内部是基于数组加链表结构来实现数据存储,这句话在jdk1.8版本之后,就不准确了。因为在JDK1.8版本之后,HashMap内部加入了红黑树的数据结构来提高数据查找效率。所以现在应该改为数组加链表(红黑树)。
  • HashMap支持NULL 键(key)、NULL 值(value),HashTable不支持。
  • HasMap 是非线程安全的,所以在多线程并发场景下,需要加锁来保证同步操作;HashTable是线程安全的。
  • HashMap具有fai-fast机制的。
  • HashMap的树化条件是链表深度达到阀值8,同时数组长度(capacity)要达到64.

准备

先了解一下分析HashMap源码,需要知道的一些内容。

DEFAULT_INITIAL_CAPACITY = 1 << 4 默认的capacity(容量)大小

MAXIMUM_CAPACITY = 1 << 30 最大的capacity

DEFAULT_LOAD_FACTOR = 0.75f 默认的加载因子

TREEIFY_THRESHOLD = 8 链表树化阀值(链表长度)

UNTREEIFY_THRESHOLD = 6 反树化,TreeNode->Node

MIN_TREEIFY_CAPACITY = 64 链表树化阀值(capacity)

Node[] table 存储数据的容器

Node 类,当数据量不大,没有达到树化条件时,HashMap的存储节点结构。

static class Node implements Map.Entry {
final int hash;
final K key;
V value;
Node next;
Node(int hash, K key, V value, Node next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
...
...
}

TreeNode 存储数量较大,满足树化条件时,HashMap的存储节点结构。

static final class TreeNode extends LinkedHashMap.LinkedHashMapEntry {
TreeNode parent; // red-black tree links
TreeNode left;
TreeNode right;
TreeNode prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node next) {
super(hash, key, val, next);
}
...
...

}

树化前:

容器类源码解析系列—— HashMap 源码分析(最新版)

树化后:

红黑树直接拿的wiki上面的图,省事!

容器类源码解析系列—— HashMap 源码分析(最新版)

图可能画的不准确,大概就是这个意思,帮助理解的,don’t care little things!

构造

HashMap提供四种构造方法,可以分为两类,一类是单纯设置capacity和loadFactor这两个成员变量的,创建一个空的hashmap;一类是传递一个Map集合参数,来赋值的。 我们先看第一类构造方法。

/**
* Constructs an empty HashMap with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
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);
}
/**
* Constructs an empty HashMap with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs an empty HashMap with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

我们主要看第一个构造方法,第二个第三个比较简单,还有注释就不提了。在第一个构造方法中,可以看到先是对传进来的initialCapacity、loadFactor参数进行一个有效性判断,然后在赋值initialCapacity的时候对其值进行了一个处理,然后赋值给threshold变量,这个threshold是HashMap扩容时的阀值。在table数组没有初始化的时候这个threshold表示初始数组的capacity。 刚说了,对initialCapacity值做了一个处理,我们看看是什么处理;

	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;
}

上面的处理是对传进来的参数进行位操作处理,来实现return出去的数据是2的n次方。举个例子: 传进的值是11,减一后变成10;10的二进制表示是1010,进过位操作后,变成1111;1111+1 变成10000 转成10进制是16;是2的4次方。 一般来说通过这个方法实际赋的值都是大于等于传进来,期望的值的。 接着看第二类构造方法:

	public HashMap(Map m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}

它传进来一个Map容器,capacity和loadFactor都是用的默认值,分别是16和0.75f。这里提一嘴,默认的loadFactor值0.75f是经过测试比较合适的一个平衡点,如果传入的loadFactor值比较大,虽然可以减少内存空间的消耗但是会增加数据查找的复杂度。因为扩容操作是很耗性能的,所以在构造HashMap时,应该根据自己需要存储的数据量大小来设置合适的capacity,避免出现扩容操作。

	final void putMapEntries(Map m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
for (Map.Entry e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}

如果table数组没有初始化就先计算容量,然后在调用putVal方法,在执行putVal会有扩容判断处理,来对table进行初始化操作。这个在讲解put操作的时候在详解putVal方法的是实现逻辑。


扩容机制

final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;//得到table数组的长度
int oldThr = threshold;//如果table数组还没有初始化,threshold代表initial capacity,否则代表扩容阈值。
int newCap, newThr = 0;
if (oldCap > 0) {//table数组长度大于0
if (oldCap >= MAXIMUM_CAPACITY) {//table数组长度达到最大值,不做扩容处理,一般不会达到这个条件
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold 这种情况,扩容后的大小是之前大小的两倍
}
else if (oldThr > 0) // 这是通过构造方法设置了capacity,还没有初始化table数组时
newCap = oldThr;//注释一
else { // 用了无参的构造方法,还没初始化table数组呢
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {//通过上面的分析,可以看出来,只有在“注释一”的case下,没有给newThr赋值了
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
if (oldTab != null) {//表示非初始化情况下,所以需要进行数据拷贝
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) != null) {//表示该索引下有数据节点
oldTab[j] = null;
if (e.next == null)//该索引下只有一个节点,没成链呢
newTab[e.hash & (newCap - 1)] = e;//直接把节点赋值到新的数组索引下,新数组的新索引通过“e.hash & (newCap - 1)”这种“与操作”来确定。
else if (e instanceof TreeNode)//如果节点是树节点,走红黑树的扩容逻辑
((TreeNode)e).split(this, newTab, j, oldCap);
else { // 注释二
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {//等于0,扩容后索引的计算依然与扩容前一致
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { //不为0,扩容后的索引值是旧的索引值加旧的数组大小
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;
}

通过上面的代码,我们知道正常情况下,扩容后的Capacity是之前容量的两倍。

上面的扩容逻辑,在每行代码后面已经给了注释讲解,比较简单,接着我们看*"注释二”*,可能看到这里会比较疑惑,为什么会有个等于零的判断,而且出现这么多Node变量作用感觉很相似,重复。之所以出现等于0 的判断是因为HashMap在扩容的时候,有一个特点是,如果节点的hash值&扩容前数组大小的值等于0表示该节点在扩容后新数组下的index索引跟之前的数组索引一致;不等于则新的数组索引为旧的数组索引+oldCapacity。

为什么又会这个结论?这根HashMap的索引计算有关,HashMap 中,索引的计算方法为 (n - 1) & hash,n表示数组长度。假如有一个Node节点的hash值为111001,OldCapacity是16(默认值)。那么:

扩容前:

111001 & (16-1)—> 111001&1111 = 001001(9)

扩容后:(Capacity变成了之前的两倍为32)

111001&(32-1)—> 111001&11111 = 011001(25)

扩容后节点的索引变了。这里我们注意下16的二进制表示:10000

假如hash值是101001,再看下结果:

扩容前:

101001 & (16-1)—> 101001&1111 = 001001(9)

扩容后:(Capacity变成了之前的两倍为32)

101001&(32-1)—> 101001&11111 = 001001(9)

这次扩容后节点的索引还是之前的索引,原因体现在我上面加粗字体,我们记住数组长度的二进制表示中1的位置,如果hash值对应的位置是0的话表示扩容后索引不变,是1的话扩容后索引是原来的索引加上原数组长度。


常规操作

put操作

官方介绍HashMap的"put","get"操作,说是时间复杂度是O(1),其实这是不准确的,他是假设hash散列操作能完全均匀分散到容器中去,现实中很难达到。

public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

当调用put方法时,会进而调用内部的putVal方法,putVal接收四个参数。

Parameter1 是传进来的key的hash值;

Parameter4 fasle表示相同key的情况下替换value值,true的话就不改变原来的value

Parameter5 只有在初始化table数组的时候才是false,其他操作都是true。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)//如果table数组还没有创建,那就先通过resize创建,并记录数组长度与引用
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)//传进来的key对应的数组索引下没有数据
tab[i] = newNode(hash, key, value, null);//那就新创建节点数据存进去
else { //对应索引下存在节点数据
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;//如果key的hash值相同,key也相同,那么替换原来value即可。
else if (p instanceof TreeNode)//是树节点的话,说明已经树化了,要走红黑树的对应put逻辑。
e = ((TreeNode)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) // 达到树化条件,链的长度为8
treeifyBin(tab, hash);//进入这个方法后,还有一个树化条件判断,数组长度有没有到达阈值。
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;
if (!onlyIfAbsent || oldValue == null)//替换旧值
e.value = value;
afterNodeAccess(e);//LinkedHashMap重写了这个方法,感兴趣可以去看看
return oldValue;//返回旧值
}
}
++modCount;
if (++size > threshold)//判断是否需要扩容
resize();
afterNodeInsertion(evict);//LinkedHashMap重写了这个方法,感兴趣可以去看看
return null;
}

HashMap的默认put操作在遇到相同key,hash的时候,是会替换原来的value的,原因在onlyIfAbsent为false;

如果节点是普通节点则会把数据插入链尾,如果是树化节点TreeNode则会有树的相应插入逻辑。在作为普通节点插入数据至链尾的过程中会检测是否达到(可能)树化条件,达到的话会走树化逻辑。把普通Node节点变成TreeNode。

get操作

public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode)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;
}

代码比较少,首先先进行table数组有效性判断,获取目标索引下的头结点。如果头结点就满足key相等的要求,那自然是皆大欢喜,省事了。直接返回头结点即可。

不是头结点的话,它会接着判断是不是TreeNode,是TreeNode的话则走树对应的get操作;否则走普通节点的查找操作,即遍历寻找,找到后就返回对应的值没找到就返回null。

remove操作

public V remove(Object key) {
Node e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}

remove方法会返回删除节点的value。我们看removeNode的逻辑。

final Node removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node[] tab; Node p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {//table数组有效性判断,获取对应索引的头结点
Node node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))//巧了,头结点就是要找到节点O(∩_∩)O哈哈~
node = p;
else if ((e = p.next) != null) {//头节点不是要找到,那就接着看它的next节点
if (p instanceof TreeNode)//头结点是TreeNode,那就走树的查找目标节点逻辑
node = ((TreeNode)p).getTreeNode(hash, key);
else {//普通节点就遍历查找
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//如果找到了,再根据节点的类型,执行对应的逻辑
if (node instanceof TreeNode)
((TreeNode)node).removeTreeNode(this, tab, movable);
else if (node == p)//如果头结点就是要找到节点,直接把头节点的next节点指向index索引即可
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}

结语

在分析源码逻辑的时候,可以发现主要分为两部分,一种是如果节点是TreeNode要走红黑树的查找,添加等逻辑;另外一种是走普通的链表逻辑。

为什么要在新的JDK中添加红黑树的数据结构,是为了提交效率,当链表过长,会拖慢效率,而红黑树的性能很好,对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。时间复杂度是O(log n)。而链表是最坏情况下的时间复杂度是O(n)。

本文主要是对HashMap的源码进行整体的分析,对于红黑树的算法逻辑细节没有提及。如果对红黑树这种结构有兴趣研究的话可以自行研究。

迷失的青猫(未知职业)-本文作者
这个人很懒,什么也没有留下。
1128 19 2019-5-24 15:52
该文章已有19人参与评论

请发表评论

全部评论

查看全部评论>>

扫一扫关注官方微信号

最前沿的技术信息一手掌握

滚动新闻
CODESEEDING(码云社)一家致力于程序员成长、以内容为核心、以提问为引导的多元化成长社区。我们在线上为技术爱好者提供了一个优质的交流氛围环境,在线下同样和众多高校联合开办了技术沙龙品牌。
020-85534346
关注我们
  • 访问移动H5版
  • 官方微信公众号

码云社 - CODESEEDING 2.0© 2018-2019 码云社. TOOBUG ( 粤ICP备16114193号-3 )