JAVA学习——hashmap

面试 | Java8 HashMap原理​ mp.weixin.qq.com
美团技术团队：Java 8系列之重新认识HashMap​ zhuanlan.zhihu.com
JAVA集合：HashMap深度解析（版本对比） – 掘金​ juejin.im
HashMap? ConcurrentHashMap? 相信看完这篇没人能难住你！​ crossoverjie.top
Java面试重点Map篇(二)——图解HashMap(一)​ mp.weixin.qq.com
Java面试重点Map篇(三)——HashMap为何不安全​ mp.weixin.qq.com

java7 hashmap死链的形成

https://coolshell.cn/articles/9606.html​ coolshell.cn
疫苗：Java HashMap的死循环 | | 酷 壳 – CoolShell
疫苗：Java HashMap的死循环 | | 酷 壳 – CoolShell​ coolshell.cn

哈系类集合的三个基本存储概念

table：存储所有节点数据的数组

slot：哈希槽哦。即table[i]这个位置。

bucket:哈希桶。table[i]上所有元素形成的表或数的集合。

hashmap是线程安全的吗？

不是。

在高并发场景中，因为扩容过程中会发生

• 对象丢失
• 死链

扩容过程

使用一个容量更大的数组来代替已有的容量小的数组，将原有table数组的元素拷贝到新的table数组里。

1.8的优化

在JDK1.8及以后的版本中引入了红黑树结构，HashMap的实现就变成了数组+链表或数组+红黑树，链表的查询效率是O(n），红黑树的查询效率是O(logN)，性能得到提升。

put过程

1. 对key的hashCode()做hash，然后再计算桶的index;
2. 如果没碰撞直接放到桶bucket里；
3. 如果碰撞了，以链表的形式存在buckets后；
4. 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD=8)，就把链表转换成红黑树（若数组容量小于MIN_TREEIFY_CAPACITY=64，不进行转换而是进行resize操作）
5. 如果节点已经存在就替换old value，这里的相同指的是hashCode以及equals(保证key的唯一性)
6. 如果表中实际元素个数超过阈值(超过load factor*current capacity)，就要resize

查找过程

1，计算键的哈希值

2，根据hash找到table中的对应链表或红黑树

3，在链表或红黑树中遍历查找

4，逐个比较，先通过hash快速比较，hash相同再通过equals比较

containsKey方法的逻辑与get是类似的，节点不为null就表示存在

hashmap的key和value都可以是null