ToB企服应用市场:ToB评测及商务社交产业平台

标题: HashMap面试相关 [打印本页]

---

作者: 反转基因福娃    时间: 2022-9-16 17:24
标题: HashMap面试相关
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.
    
  
  

参考文档

• HashMap详解
  
• 面试:HashMap夺命二十一问
  
• 深入浅出ConcurrentHashMap
  
• ConcurrentHashMap(1.8)讲解及常见面试题
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4