-
HashMap
-
数组+链表
-
非同步,可使用 Collections.synchronizedMap 构造同步 HashMap
-
通过“拉链法”实现的哈希表
-
默认容量 16,必须为 2 的幂
-
table ,一个 Entry 数组(Entry 实际为单项链表)
-
size,键值对数量
-
threshold,阈值 = 容量 × 加载因子,用于判断是否需要调整容量
-
loadFactor,加载因子,默认 0.75,时间与空间上的一种折中
- 哈希冲撞
-
modCount -> fail-fast 机制
-
hash() 计算 key 的 hash 值,供寻找索引使用
-
indexFor() 返回数组索引 hash & (length - 1)
-
resize() 重新调整大小,重新将元素添加到新数组
-
put 元素放在链表表头
-
Entry implements Map.Entry ; key, value, next, hash
-
HashIterator implements Iterator
- current, next
- expectedModCount
- hasNext(), nextEntry(), remove()
-
keySet, entrySet;Set不包含重复元素
-
values 为 Collection,可重复
1.8 中使用了红黑树,在某个桶中链表长度达到 8 时,链表会转化为红黑树,提升查找性能 (
O(N)
->O(logn)
)-
ConcurrentHashMap
- 不允许
key
/value
为空 - 1.7
- 分段锁
Segment
继承ReentrantLock
,分段只在使用时才会创建- 一个分段锁定不影响其他分段的访问,提升高并发环境下的处理能力
- 每个分段其实也是一个表
- 默认容量 16,默认并发度 16,默认负载因子 0.75
-
put
时会进行tryLock
一定次数后,若仍无法获取锁,则通过lock
申请- 获得锁后对链表进行遍历查找,无相同节点则将新的
HashEntry
做为链表头 - 如果容量达到阈值,则对
Segment
进行rehash
扩容
- 获得锁后对链表进行遍历查找,无相同节点则将新的
- 弱一致性:
get
,containsKey
没有使用锁,而是通过Unsafe
的getObjectVolatile()
提供原子语义 -
size
,containsValue
- 进行两次操作,如果连续两次所有
Segment
的modcount
和相等,则说明未发生其他修改,返回获得的值 - 应避免在多线程情况下使用
- 进行两次操作,如果连续两次所有
- 分段锁
- 1.8
- 放弃分段锁,使用 CAS +
synchronized
头节点 - 与 HashMap 类似,使用 数组+链表+红黑树 实现
-
Node<K,V> implements Map.Entry<K,V>
用于存储键值对 -
TreeNode<K,V> extends Node<K,V>
用于放入TreeBin
完成红黑树的转换
- 放弃分段锁,使用 CAS +
- 不允许
-
网友评论