java 7及之前版本
在java 7及之前的版本中，hashmap的底层数据结构主要是数组加链表。具体实现如下：
- 数组：hashmap的核心是一个entry数组（
entry），这个数组的大小总是2的幂。每个数组元素是一个单一的entry节点，或者是一个链表的头节点。
- 链表：当两个或更多的键经过哈希运算后映射到数组的同一个索引上时，就会形成链表。entry节点包含了键值对以及指向下一个entry的引用，以此来解决哈希冲突。
java 8及之后版本
从java 8开始，hashmap的底层结构除了数组加链表之外，还引入了红黑树，以优化在链表过长时的查找性能。结构变为数组加链表加红黑树：
- 数组：同样是一个entry数组（java 8中称为node），大小仍然是2的幂，用于快速定位。
- 链表：在哈希冲突时，键值对仍会以链表形式链接在一起。但与java 7不同的是，java 8对链表的处理增加了转换为红黑树的条件。
- 红黑树：当一个桶中的链表长度超过8且hashmap的容量大于64时（不大于64会先对数组进行扩容
resize()），链表会被转换成红黑树。这种转换提高了在大量哈希冲突情况下的查找效率，因为红黑树的查找时间复杂度为o(log n)，相较于链表的o(n)有显著提升。
在jdk1.7的时候，采用的是头插法
在jdk1.8改成了尾插法，这是因为头插法在多线程环境下扩容时可能会产生循环链表问题
线程不安全
无论是jdk1.7还是1.8都是线程不安全的，下图是1.8中的put方法
tab是就是hashmap的数组table，第一个if判断时做了赋值。框起来的部分表示如果没有hash冲突就直接在数组上插入元素，但是如果两个线程hash一样且都进入到了这个if下，线程1先执行的插入数据，线程2会覆盖1插入的数据。
那么什么是循环链表问题呢？这就不得不介绍一下hashmap的扩容机制了。
首先讲几个hashmap的属性
- table：数组，存放链表或红黑树的头节点
- node：节点，属性有hash、key、value、next（下一个节点）
- size：元素个数，即节点node个数，非数组长度
- capacity：当前数组长度
- loadfactor：加载因子，默认为0.75f，简称loadfactor
- threshold：扩容门槛，值为capacity*loadfactor，size达到这个门槛就扩容
当size大于threshold时，就会进行扩容resize()。
扩容分为两步
- 创建一个新的数组，长度为原数组的两倍
- 遍历所有node节点，重新计算index值（java8首先会重新计算hash值），放到新数组里，存在hash冲突的就放到链表或红黑树
为什么要重新计算index值，直接把张三这条链表复制到新的数组中不行吗？
答案是不行的，因为index规则是根据数组长度来的，如图
所以index 的计算公式是这样的：
- index = hashcode(key) & (length - 1)
循环链表问题理解起来比较麻烦，如果理解不了就知道jdk1.7hashmap扩容的时候有这么回事就行。但是可能是我自己太笨了万一大家一看就懂了呢
我们来看一下java1.7扩容的源码
void resize(int newcapacity) {
entry[] oldtable = table;
int oldcapacity = oldtable.length;
if (oldcapacity == maximum_capacity) {
threshold = integer.max_value;
return;
}
entry[] newtable = new entry[newcapacity];
transfer(newtable);
table = newtable;
threshold = (int)(newcapacity * loadfactor);
}
void transfer(entry[] newtable) {
entry[] src = table;
int newcapacity = newtable.length;
for (int j = 0; j < src.length; j ) {
entry e = src[j];
if (e != null) {
src[j] = null;
do {
entry next = e.next;
//重新计算元素在数组中的索引
int i = indexfor(e.hash, newcapacity);
e.next = newtable[i];
newtable[i] = e;
e = next;
} while (e != null);
}
}
}
重点在于transfer方法，作用是重新计算index值然后将旧数组中的数据迁移到新数组
循环链表的产生：
原因：
假设我们有两个thread都在执行resize方法，thread1第一步刚执行完第23行entry就卡住了，这时thread2执行完了resize方法。
过程：
- thread1第一次执行完entry
- thread2执行完resize后，李四的next变成了张三
- 此时又回到thread1，第二次执行entry
由此我们知道了循环链表产生的关键在于头部插入元素a时，元素a的next元素b的next是元素a本身，所以java8采用了尾插法，避免了循环链表。
求赞！求关注！！以后会更新更多有用的内容！！！꒰⑅•ᴗ•⑅꒱
保佑大家代码永无bug ╰(´︶`)╯
