HashMap源码:
- 加载因子:loadFactory -- 默认 0.75f
- 初始容量大小: capacity 默认 16, 最大限制 1>> 16)[/code]主要是从速度,功效和质量来考虑的,减少系统的开销,也不会因为高位没有参与下标的计算,从而引起碰撞
- 用异或运算符,保证了对象的hashCode的32位值只要有一位发生改变,整个hash()返回值就会改变,尽可能的减少碰撞
拉链法导致的链表过深问题为什么不用二叉树代替,而选择红黑树?为什么不一直使用红黑树?
- 红黑树是为了解决二叉查找树的缺陷,二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了,同样会造成很深的问题),遍历查找会非常慢.
- 红黑树在插入新数据后会通过左旋,右旋或者变色操作来保持平衡,引入红黑树是为了查找数据快,解决链表查询深度的问题,红黑树属于平衡二叉树,尽管为了保持平衡会付出代价,但该代价损耗的资源相比遍历线性链表来说要少.所以,当长度大于8的时候,会使用红黑树.而为什么是8,是因为符合泊松分布,为8时资源损耗相对来说较少.
HashMap和CuncurrentHashMap的区别?
- ConcurrentHashMap类是java并发包java.util.concurrent中提供的一个线程安全且高效的HashMap实现.
- 1.7中ConcurrentHashMap采用分段锁(ReentrantLock + segment +hashEntry),相当于把一个HashMap分成多个段,每段分配一把锁,这样支持多线程访问.锁粒度:基于segment,包含多个HashEntry
- 1.8中采用CAS + synchronized + Node + 红黑树.锁粒度: Node.锁粒度降低了
- HashTable则使用synchronized关键字加锁
- 区别: ConcurrentHashMap键值对都不允许为null
ConcurrentHashMap简单介绍一下?
- java.util.concurrent.ConcurrentHashMap属于JUC包下的一个集合类,可以实现线程安全.
- 1.8之前:
- 由多个Segment组合而成,Segment本身就相当于一个HashMap对象.同HashMap一样,Segment包含一个HashEntry数组,数组中的每一个HashEntry既是一个键值对,也是一个链表的头节点.
- Put: 首先,会尝试获取锁,若获取失败,则利用scanAndLockForPut()自旋获取锁.如果重试的次数达到了MAX_SCAN_RETRIES则改为阻塞锁获取,保证能获取成功.接着,遍历该HashEntry,如果不为空则判断传入的key和当前遍历的key是否相等,相等则覆盖旧的value.为空,则需要新建一个HashEntry并加入到Segment中,同时会先判断是否需要扩容.
- Get: key通过hash之后定位到具体的segment,再通过一次hash定位到具体元素上.
由于HashEntry中的value属性是用volatile关键字修饰的,保证了内存可见性,所以每次获取时都是最新值. 整个过程非常搞笑,不需要加锁.
- 1.8之后:
- 数组+链表 改为 数组+链表/红黑树,HashEntry改为Node
ConcurrentHashMap的key,value是否可以为null,为什么?
- 都不可以为null,为null时会抛出空指针异常.
ConcurrentHashMap是一个用于多线程并发场景下的并发容器(map),在多线程环境下执行增删改查方法要保证线程安全性.
- 不能为null,因为会产生二义性问题: 当我们用get方法去获取一个value为null的时候,可能会没有这个key,也可能会有这个key,只不过value为null.
- HashMap如何解决二义性问题
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
- 如果存在key为null的元素(key = null对应的hash值为0),getNode获取到值不为null
- 如果不存在key为null的元素,此时hash值=0对应的下标元素为null,即getNode获取到的值为null
- ConcurrentHashMap为什么不能解决二义性问题
- 因为ConcurrentHashMap是一个用在多线程并发的map容器,不能put null 是因为无法分辨是key没找到null,还是有key的值为null.这在多线程里没法保证会不会有其他线程修改为null键和null值的情况,所以不让put null.
参考文档
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
