咱老百姓歌词,吸血鬼之路,白雪公主stoya
作为java开发人员，hashmap可谓是业务中的一把利器，9龙再次捡起这老生常谈的知识点，深入源码，细细品味。
首先，我们抛出几个关于hashmap的问题，带着问题去学习，就像捉迷藏一样有意思。
1、为什么要使用hashmap？hashmap有什么特性？
2、hashmap的主要参数有哪些？都有什么作用？
3、hashmap是基于什么数据结构实现的？
4、构造hashmap时传入的初始容量是如何处理的？为什么要这样做？
5、hashmap在什么时候扩容？扩容的时候都做了什么事？hash碰撞8次一定会转换为红黑树吗？
6、在foreach时对hashmap进行增删操作会发生什么？
我们在使用一种工具的时候，肯定是因为其的某种特性很符合我们的需求，能够快速准确的解决我们的问题。那我们为什么要使用hashmap呢？
this implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.
源码注释里有这样一句话，这就是我们使用hashmap的原因。
意为：hashmap为基本操作(get和put)提供了常数时间性能（即o(1)），假设散列函数将元素适当地分散到各个bucket中。
我们可以这样理解，如果当你需要快速存储并查询值，可以使用hashmap，它可以保证在o(1)的时间复杂度完成。前提是你键的hashcode要足够不同。
map还有一个特性就是key不允许重复。下面我们就来看看hashmap如何保证o(1)进行get和put。
我要评论 //默认的初始化桶容量，必须是2的幂次方（后面会说为什么）
static final int default_initial_capacity = 1 << 4;
//最大桶容量
static final int maximum_capacity = 1 << 30;
//默认的负载因子
static final float default_load_factor = 0.75f;
//判断是否将链表转化为树的阈值
static final int treeify_threshold = 8;
//判断是否将树转化为链表的阈值
static final int untreeify_threshold = 6;
//判断是否可以执行将链表转化为树，如果当前桶的容量小于此值，则进行resize()。避免表容量过小，较容易产生hash碰撞。
static final int min_treeify_capacity = 64;
//hash表
transient node<k,v>[] table;
//缓存的entryset，便与迭代使用
transient set<map.entry<k,v>> entryset;
//记录hashmap中键值对的数量
transient int size;
//当对hashmap进行一次结构上的变更，会进行加1。结构变更指的是对hash表的增删操作。
transient int modcount;
//判断是否扩容的阈值。threshold = capacity * load factor
int threshold;
//负载因子，用于计算threshold，可以在构造函数时指定。
final float loadfactor;
上面我们看到一个node<k,v>[] table的node数组。
为什么要使用数组呢？
答：为了能快速访问元素。哦，说的什么鬼，那我得追问，为什么数组能快速访问元素了？
让我们看看node的结构。
static class node<k,v> implements map.entry<k,v> {
final int hash; //key 的hash
final k key; //key对象
v value; //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;
}
}
我们看到，node节点内部保留了一个next节点的引用，太熟悉了，这不就是链表嘛。
到这，我们知道了hashmap的底层数据结构是基于数组+链表。但是，这就完了吗？在jdk1.7确实只是这样，jdk1.8为了提高hash碰撞时链表查询效率低的问题，在hash碰撞达到8次之后会将链表转化为红黑树，以至于将链表查询的时间复杂度从o(n)提高到o(logn)。
到这我们就可以明白，hashmap如果能够均匀的将node节点放置到table数组中，我们只要能够通过某种方式知道指定key的node所在数组中的索引，基于数组，我们就可以很快查找到所需的值。
接着我们就要看看如何定位到table数组中。
有了上面的基础知识，知道字段含义及数据结构，我们就有一点信心可以正式进入源码阅读。我觉得了解一个类，得从构造函数入手，知道构造对象的时候做了哪些初始化工作，其次再深入常用的方法，抽丝剥茧。
public hashmap(int initialcapacity) {
//如果只传入初始值，则负载因子使用默认的0.75
this(initialcapacity, default_load_factor);
}
public hashmap(int initialcapacity, float loadfactor) {
if (initialcapacity < 0)
throw new illegalargumentexception("illegal initial capacity: " +
initialcapacity);
//保证初始容量最大为2^30
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);
}
我们可以看到，构造函数主要是为了初始化负载因子及hash表的容量。可能大家会疑问，这不是初始化的是threshold吗？不要被表面所欺骗，这只是临时将hash表的容量存储在threshold上，我想是因为hashmap不想增加多余的字段来保存hash表的容量，因为数组的length就可以表示，只是暂时数组还未初始化，所以容量暂先保存在threshold。
我们看到将用户指定的initialcapacity传入tablesizefor方法返回了一个值，返回的值才是真正初始化的容量。？？？搞毛子这是？然我们揭开它神秘的面纱。
/**
* returns a power of two size for the given target capacity.
*/
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;
}
好吧， 我们还是把它盖上吧，9龙也没去推算过。我们从jdk给的方法注释看出，该方法返回一个目标值的2的幂次方，进一步9龙翻译为：返回大于或等于目标值的第一个数，该数必须是2的幂次方。
举例说一下：
如果输入10，大于等于10的第一个数，又是2的幂次方的数是16；
如果输入7，大于等于7的第一个数，又是2的幂次方的数是8；
如果输入20；大于等于20的第一个数，又是2的幂次方的是32；
到这我们又得问自己，为什么hash表的容量必须是2的幂次方呢？
当我们new出hashma的对象，都会调用put方法进行添加键值对。我跟那些直接贴代码的能一样吗？有啥不一样，哈哈哈。9龙会先读源码，再贴流程图，这样大家会更理解一点。
public v put(k key, v value) {
return putval(hash(key), key, value, false, true);
}
static final int hash(object key) {
int h;
//将key的高16位与低16位异或，减小hash碰撞的机率
return (key == null) ? 0 : (h = key.hashcode()) ^ (h >>> 16);
}
让我们看看putval干了什么。
/**
* 此方法用于将(k,v)键值对存储到hashmap中
*
* @param hash key的hash
* @param key key对象
* @param value key对应的value对象
* @param onlyifabsent 如果是true,则不覆盖原值。
* @param evict if false, the table is in creation mode.
* @return 返回旧值，如果没有，则返回null。
*/
final v putval(int hash, k key, v value, boolean onlyifabsent,
boolean evict) {
node<k,v>[] tab; node<k,v> p; int n, i;
//在第一次put的时候，此时node表还未初始化，上面我们已经知道，构造hashmap对象时只是初始化了负载因子及初始容量，但并没有初始化hash表。在这里会进行第一次的初始化操作。
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果得到了一个hash值，并且hash值在很少相同的情况下，如何均匀的分布到table数组里呢？最容易想到的就是用hash%n，n为table数组的长度。但是%运算是很慢的，我们知道位运算才是最快的，计算机识别的都是二进制。所以如果保证n为2的幂次方，hash%n 与 hash&(n-1)的结果就是相同的。这就是为什么初始容量要是2的幂次方的原因。
//当找到的hash桶位没有值时，直接构建一个node进行插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newnode(hash, key, value, null);
else {
//否则，表明hash碰撞产生。
node<k,v> e; k k;
//判断hash是否与桶槽的节点hash是否相同并且key的equals方法也为true,表明是重复的key，则记录下当前节点
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) {
//如果节点的next索引是null，表明后面没有节点，则使用尾插法进行插入
if ((e = p.next) == null) {
p.next = newnode(hash, key, value, null);
//此时链表长度为9，即hash碰撞8次，会将链表转化为红黑树
if (bincount >= treeify_threshold - 1) // -1 for 1st
treeifybin(tab, hash);
break;
}
//如果key是同一个key,则跳出循环链表
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//判断是否是重复的key
if (e != null) { // existing mapping for key
//拿到旧值
v oldvalue = e.value;
//因为put操作默认的onlyifabsent为false，所以，默认都是使用新值覆盖旧值
if (!onlyifabsent || oldvalue == null)
e.value = value;
afternodeaccess(e);
//返回旧值
return oldvalue;
}
}
//到这里，表明有新数据插入到hash表中，则将modcount进行自增
++modcount;
//判断当前键值对容量是否满足扩容条件，满足则进行扩容
if (++size > threshold)
resize();
afternodeinsertion(evict);
return null;
}
总结一下：
灵魂拷问：真的hash碰撞8次一定会转换为红黑树吗？？？
其实不然，在put中，如果hash碰撞8次会调用此方法将链表转换为红黑树，但不一定调用就会真正转换。需要tab.length大于等于64才会真正的执行转换操作。因为在表容量过小的时候，hash碰撞才会比较明显，但不是说表越大越好。
final void treeifybin(node<k,v>[] tab, int hash) {
int n, index; node<k,v> e;
//如果表的长度小于64，是先扩容
if (tab == null || (n = tab.length) < min_treeify_capacity)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
//只有大于等于64才会真正的转换
treenode<k,v> hd = null, tl = null;
do {
treenode<k,v> p = replacementtreenode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
put方法中用到了两次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;
//如果旧table中有数据
if (oldcap > 0) {
//当表的长度达到定义的最大值时，不再进行扩容，只是将判断扩容的阈值改为integer.max_value。
if (oldcap >= maximum_capacity) {
threshold = integer.max_value;
return oldtab;
}
//先将新容量为原来的2倍，如果结果小于maximum_capacity并且旧的容量大于等于默认值16，则也将新的阈值为原来的2倍
else if ((newcap = oldcap << 1) < maximum_capacity &&
oldcap >= default_initial_capacity)
newthr = oldthr << 1; // double threshold
}
//oldcap等于0 如果旧阈值大于0,则将旧阈值赋值给新容量。这一步对应于指定的容量构造器，指定容量时，赋值给了阈值
else if (oldthr > 0) // initial capacity was placed in threshold
newcap = oldthr;
//这一步对应于无参构造器，这时使用默认值
else { // zero initial threshold signifies using defaults
newcap = default_initial_capacity;
newthr = (int)(default_load_factor * default_initial_capacity);
}
//这里是因为在oldcap大于0但没有大于默认的16，不会更改newthr的值，还是0。这时候需要根据newcap的值计算newthr。
if (newthr == 0) {
float ft = (float)newcap * loadfactor;
newthr = (newcap < maximum_capacity && ft < (float)maximum_capacity ?
(int)ft : integer.max_value);
}
//将新阈值覆盖threshold
threshold = newthr;
@suppresswarnings({"rawtypes","unchecked"})
//使用newcap初始化新表。这里的newcap是oldcap的2倍
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;
//如果下标j对应的位置有值，拿到引用赋值给e
if ((e = oldtab[j]) != null) {
//因为已经有了引用e,可以将原数组的赋值为null, help gc
oldtab[j] = null;
//如果e.next没有指向，则证明当前槽位只有一个节点，直接计算在新表的位置赋值即可
if (e.next == null)
newtab[e.hash & (newcap - 1)] = e;
//证明当前槽位不止一个节点，判断e是否为treenode，如果是，则使用树的迁移方法
else if (e instanceof treenode)
((treenode<k,v>)e).split(this, newtab, j, oldcap);
else { // preserve order
//因为扩容后的节点不是在j处，就在j + oldcap处。
//lohead节点记录了j处的链表的头指针，lotail记录j处尾指针
//hihead节点记录了j+oldcap处链表的头指针，hitail记录了j+oldcap处的尾指针
node<k,v> lohead = null, lotail = null;
node<k,v> hihead = null, hitail = null;
node<k,v> next;
do {
next = e.next;
//判断是否还处于j处（后面会详细解释）
if ((e.hash & oldcap) == 0) {
if (lotail == null)
//记录j的头指针
lohead = e;
else
//链接节点
lotail.next = e;
lotail = e;
}
//否则在[j+oldcap]处
else {
if (hitail == null)
//记录j+oldcap的头指针
hihead = e;
else
//链接节点
hitail.next = e;
hitail = e;
}
} while ((e = next) != null);
if (lotail != null) {
lotail.next = null;
//将位置没变的链表放在j处
newtab[j] = lohead;
}
if (hitail != null) {
hitail.next = null;
//将位置改变的链表放在[j+oldcap]处
newtab[j + oldcap] = hihead;
}
}
}
}
}
//返回新链表
return newtab;
}
现在我们仔细分析e.hash & oldcap。二话不说，直接上图。
如此详细，是不是不点赞都有点过分了。
resize()中我们看到如果是树节点，调用了((treenode<k,v>)e).split(this, newtab, j, oldcap)方法。有了上面的知识，其实这个方法干的事情是一样的。将红黑树拆分为两棵子树，还是分别放置于原来位置和原来位置+oldcap位置。但要注意，这个方法在树的节点小于等于6的时候会将红黑树转换回链表。
final void split(hashmap<k,v> map, node<k,v>[] tab, int index, int bit) {
treenode<k,v> b = this;
// relink into lo and hi lists, preserving order
treenode<k,v> lohead = null, lotail = null;
treenode<k,v> hihead = null, hitail = null;
int lc = 0, hc = 0;
for (treenode<k,v> e = b, next; e != null; e = next) {
next = (treenode<k,v>)e.next;
e.next = null;
//判断位置是否更改
if ((e.hash & bit) == 0) {
if ((e.prev = lotail) == null)
lohead = e;
else
lotail.next = e;
lotail = e;
++lc;
}
else {
if ((e.prev = hitail) == null)
hihead = e;
else
hitail.next = e;
hitail = e;
++hc;
}
}
if (lohead != null) {
//数量小于等于6，转换回链表
if (lc <= untreeify_threshold)
tab[index] = lohead.untreeify(map);
else {
tab[index] = lohead;
if (hihead != null) // (else is already treeified)
lohead.treeify(tab);
}
}
if (hihead != null) {
if (hc <= untreeify_threshold)
tab[index + bit] = hihead.untreeify(map);
else {
tab[index + bit] = hihead;
if (lohead != null)
hihead.treeify(tab);
}
}
}
到此，resize()方法9龙啃完了，牙好疼啊。
知道了hashmap的数据结构及如何以常数时间将键值对put保存管理的，那get这不是很容易吗？请大家尝尝这道小菜。我们保存的是键值对，存储的时候都是以key作为条件存储的，所以在我们取值的时候也是通过key获取值。
public v get(object key) {
node<k,v> e;
//计算key的hash，用于定位桶的位置
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;
//如果hash桶有值，并且基于hash继续的桶位置也存在值
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;
//如果第一个不匹配，则判断next是否存在
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);
}
}
//没有找到，则返回null
return null;
}
总结一下get流程：
这个字段并不是map独有的，collection集合（list、set）也有。此字段用于迭代时的快速失败，也就是在迭代的过程中，如果调用了put、clear、remove等会对容器内部数据的数量产生增加或减少的操作时，抛出concurrentmodificationexception异常。
hashmap有三个迭代器，分别是keyiterator、valueiterator、entryiterator，它们分别对应于keyset、values、entryset内部类中，当用户调用其对应的iterator()方法时都会new一个对应的迭代器。
这里我就不贴代码了，太多，有兴趣的可以去看一看。这里主要讲解为什么快速失败。
final class keyiterator extends hashiterator
implements iterator<k> {
public final k next() { return nextnode().key; }
}
final class valueiterator extends hashiterator
implements iterator<v> {
public final v next() { return nextnode().value; }
}
final class entryiterator extends hashiterator
implements iterator<map.entry<k,v>> {
public final map.entry<k,v> next() { return nextnode(); }
}
使用者可以根据自己的需求选择使用的迭代器。每一个都继承自hashiterator，我们来看一看。
abstract class hashiterator {
node<k,v> next; // next entry to return
node<k,v> current; // current entry
int expectedmodcount; // for fast-fail
int index; // current slot
hashiterator() {
//关键在这里，当每一次使用迭代器的时候，会将modcount赋值给内部类的expectedmodcount
expectedmodcount = modcount;
node<k,v>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasnext() {
return next != null;
}
final node<k,v> nextnode() {
node<k,v>[] t;
node<k,v> e = next;
//每次取值之前会判断modcount和expectedmodcount是否相等，如果不等则表明在迭代过程中有其他线程或当前线程调用了put、remove等方法。
if (modcount != expectedmodcount)
throw new concurrentmodificationexception();
if (e == null)
throw new nosuchelementexception();
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
//如果想删除，只能调用迭代器自己的remove方法，但是，它删除的是调用nextnode()拿到的节点
public final void remove() {
node<k,v> p = current;
if (p == null)
throw new illegalstateexception();
//删除之前也会判断modcount是否被修改
if (modcount != expectedmodcount)
throw new concurrentmodificationexception();
current = null;
k key = p.key;
removenode(hash(key), key, null, false, false);
expectedmodcount = modcount;
}
}
所以，在迭代过程中对hashmap进行增删操作会抛出concurrentmodificationexception异常。还记得一开始提出的一个问题吗？对的，就是它。你可以去看看list等的源码，modcount也存在，而且实现都是一样的。
楼主花了很大的精力与时间与大家细嚼慢咽hashmap，我想现在大家都知道了最开始的问题的答案了，包括过程中楼主提出的一些问题，也都一一进行了详解。9龙没去讨论并发条件出现的问题，也不讨论1.7并发扩容时链表死循环问题，网上太多了。更重要是，hashmap本身就不支持并发操作，那你想到了什么呢？
9龙才疏学浅，文中如有错误，敬请指出，也欢迎大家有疑问可以提出，一起探讨进步。
如果觉得9龙本文对你有帮助，请帮忙点赞、分享以示支持，如果转载请注明出处。话不多说，点关注，不迷路。
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
浅析我对 String、StringBuilder、StringBuffer 的理解
使用IDEA搭建SSM框架的详细教程(spring + springMVC +MyBatis)
Springboot整合freemarker 404问题解决方案
引入mybatis-plus报 Invalid bound statement错误问题的解决方法
网友评论