HashMap底层执行原理——数据结构
一:HashMap底层执行原理
1.HashMap的存储结构
数组、链表、红黑树(jdk1.8)
2. 特点
1.快速存储
2.快速查找(时间复杂度O(1))
3.可伸缩
3.hash算法
所有的对象都有hashCode(使用key的)
hash值的计算
(hashCode) ^ (hashCode >>> 16)
4.数组下标计算
数组默认大小:16
数组下标:hash&(16-1) = hash% 16
5.Hash冲突
不同的对象算出来数组下标是相同时
单向链表:用于解决Hash冲突的方案,加入一个next记录下一个节点
6.扩容
数组变长2倍 0.75
7.触发条件
数组存储比例达到75% --- 0.75
8.红黑树
一种二叉树,高效的检索效率
9.触发条件
在链表长度大于8的时候,将后面的数据存在红黑树中
## 二. HashTable 和 currentHashMap 是如何确保线程安全的
HashTable : 都在方法前面加了synchronized 关键字, 把整个数据都放到一个大桶里面, 只允许一个线程访问, 其他线程处于阻塞状态。效率低, 所以有了currentHashMap
currentHashMap :
JDK 1.7--> 分段锁思想, 将一个大桶分成若干个小桶(假设有1000个数据, 分成16 个桶), 不同线程可以拿不同桶里面的数据
JDK 1.8-->相比较与1.7 , 1.8 锁的粒度更小了, 如果有1000 个数据, 就有1000 个锁(桶)), 每个桶都有自己独立的说, 可并发的线程数变多