-
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 +
- 不允许
FAQ-HashMap & ConcurrentHashMap
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 1.ConcurrentHashmap简介 在使用HashMap时在多线程情况下扩容会出现CPU接近100%的情况...
- 你也许经常听到闺蜜说某个护肤品好，推荐给你用，但是你用了过后并没有改善皮肤状态，甚至反而加重了皮肤负担。 其实适合...
