网站停止运营通知
HashMap | 特别重要,面试一般都会聊
IT面试
683 ·
0 ·
2023-02-08 16:45:19
最新编辑原因:

1. HashMap数据结构是什么

Java1.7Java1.8
数据结构数组+ (单向)链表数组+链表+红黑树(空间换时间)
类(称呼)EntryNode
插入元素顺序不同头插法: 用单链表进行的纵向延伸,当采用头插法时会容易出现逆序且环形链表死循环问题尾插法

Java1.8插入元素为什么采用尾插法?
因为使用头插会改变链表的上的顺序,但是如果使用尾插,在扩容时会保持链表元素原本的顺序,就不会出现链表成环的问题了。具体原因如下:

  1. 头插法的插入顺序和链表原顺序相反;

  2. table是线程间共享的,每次操作都会修改table元素的next;

    Java7在多线程操作HashMap时可能引起死循环,原因是扩容转移后前后链表顺序倒置,在转移过程中修改了原来链表中节点的引用关系。
    Java8在同样的前提下并不会引起死循环,原因是扩容转移后前后链表顺序不变,保持之前节点的引用关系

HashMap的数据结构为什么使用[数组+链表]?
组成HashMap的基本结构是数组和链表,数组里面每个地方都存了Key-Value这样的实例。那为什么需要链表呢?因为数组长度是有限制的

HashMap中的链表大小超过8个时会自动转化为红黑树,当删除小于六时重新变为链表,为啥呢?
根据泊松分布,在负载因子默认为0.75的时候,单个hash槽内元素个数为8的概率小于百万分之一,所以将7作为一个分水岭,等于7的时候不转换,大于等于8的时候才进行转换,小于等于6的时候就化为链表

是8仅仅是因为是统计学的结果

细问: 红黑树转回链表的阈值为什么是6,而不是8?
因为如果这个阈值也设置成8,假如发生碰撞,节点增减刚好在8附近,会发生链表和红黑树的不断转换,导致资源浪费

链表是什么样子?

2. HashMap如何解决Hash冲突?

为什么会发生Hash冲突

当put的时候需要计算hash和下标,这个时候计算出来的值可能存在一样的,那么存到数组中的相同位置,就会发生hash冲突

如何解决Hash冲突?
  1. 链地址法(HashMap使用)
    HashMap的解决方式是使用【链地址法】,即使用链表的方式解决。key一样的时候才会覆盖,否则就把元素放到链表的下一个位置

  2. 【开放】定址法
    开放定址法就是从冲突的位置再接着往下找,给冲突元素找个空位。有以下两个方法:
    线行探查法: 从冲突的位置开始,依次判断下一个位置是否空闲,直至找到空闲位置
    平方探查法: 从冲突的位置x开始,第一次增加12个位置,第二次增加22…,直至找到空闲的位置

  3. 再哈希法
    换种哈希函数,重新计算冲突元素的地址

  4. 建立公共溢出区
    再建一个数组,把冲突的元素放进去

3. HashMap的默认初始化长度是多少?

16

为什么是16?

  1. 作者认为16这个初始容量是能符合常用而已

  2. 同时16是2的次幂,方便位运算,位与运算比算数计算的效率高了很多

  3. 之所以选择16,是为了服务将Key映射到index的算法。index = HashCode(Key)&(Length- 1)

4. 怎么尽可能得到一个均匀分布的hash?

只要输入的HashCode本身分布均匀,Hash算法的结果就是均匀的。

5. 为啥我们重写equals方法的时候需要重写hashCode方法呢?

在未重写equals方法我们是继承了object的equals方法,那里的 equals是比较两个对象的内存地址,但是我们需要比较值,所以需要重写,
重写完equals方法后,在对hashCode进行重写,保证相同的对象返回相同的hash值,不同的对象返回不同的hash值。

6. 怎么处理HashMap在线程安全的场景?

  1. ConcurrentHashMap

  2. 使用Collections.synchronizedMap(Map)创建线程安全的map集合

  3. Hashtable

    1. Hashtable和HashMap的不同点

 

HashtableHashMap其他
键值不允许键或值为null键值则都可以为null
实现方式不同继承了 Dictionary类
(Dictionary 是 JDK 1.0 添加的,
貌似没人用过这个,我也没用过。)
继承的是 AbstractMap 类
初始化容量不同Hashtable 初始容量为:11HashMap 的初始容量为:16两者的负载因子默认都是:0.75
扩容机制不同:当现有容量大于总容量 * 负载因子时Hashtable 扩容规则为当前容量翻倍 + 1HashMap 扩容规则为当前容量翻倍
迭代器不同Hashtable 的 Enumerator 不是 fail-fast 的HashMap 中的 Iterator 迭代器是 fail-fast 的所以,当其他线程改变了HashMap 的结构,如:增加、删除元素,将会抛出ConcurrentModificationException 异常,而 Hashtable 则不会。
  1. 为什么Hashtable不允许键或值为null,而HashMap的键值则都可以为null?
    因为Hashtable使用的是安全失败机制(fail-safe),这种机制会使你此次读到的数据不一定是最新的数据(因为遍历的是拷贝的数据)。
    如果你使用null值,就会使得其无法判断对应的key是不存在还是为空,因为你无法再调用一次contain(key)来对key是否存在进行判断,ConcurrentHashMap同理。

 


在介绍怎么处理HashMap在线程安全的场景?时,有介绍到fail-safe和fail-fast 2个概念,它们具体是什么

安全失败(fail—safe)—— 并发度很低,是直接使用synchronized

采用安全失败机制的集合容器,使用迭代器进行遍历时不是直接在集合内容上访问的,而是将原有集合内容进行【拷贝】,在拷贝的集合上进行遍历。

原理
迭代器在遍历时访问的是【拷贝的集合】,所以在遍历过程中对原集合所作的修改并不能被迭代器检测到,所以不会触发 ConcurrentModificationException 异常。

应用场景
java.util.concurrent包下的容器都是安全失败,可以在多线程下并发使用,并发修改。不会报ConcurrentModificationException异常

优缺点

  1. 由于对集合进行了拷贝,避免了 ConcurrentModificationException 异常,但拷贝时产生大量的无效对象,开销大。

  2. 无法保证读取到的数据是原集合中最新的数据,即迭代器进行遍历的是拷贝的集合,在遍历期间原集合发生的修改,迭代器是检测不到的。

 

fail-fast是啥?

快速失败(fail—fast)是java集合中的一种机制, 在用迭代器遍历一个集合对象时,如果遍历过程中对集合对象的内容进行了修改(增加、删除、修改),则会抛出ConcurrentModification Exception

fail-fast原理
迭代器在遍历时直接访问集合中的内容,并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化,就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前,都会检测modCount变量是否为expectedmodCount值,是的话就返回遍历;否则抛出异常,终止遍历

注意:这里异常的抛出条件是检测到 modCount!=expectedmodCount 这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值,则异常不会抛出。 因此,不能依赖于这个异常是否抛出而进行并发操作的编程

哪些集合是fail-fast的?
java.util包下的集合类都是快速失败,不能在多线程下发生并发修改(迭代过程中被修改)

7. 有序Map

HashMap是无序的,根据 hash 值随机插入。如果想使用有序的Map,可以使用LinkedHashMap 或者 TreeMap

LinkedHashMap 怎么实现有序的?
LinkedHashMap维护了一个双向链表,有头尾节点,同时 LinkedHashMap 节点 Entry 内部除了继承 HashMap 的 Node 属性,还有 before 和 after 用于标识前置节点和后置节点。

TreeMap 怎么实现有序的?
TreeMap 是按照 Key 的自然顺序或者 Comprator 的顺序进行排序,内部是通过红黑树来实现。所以要么 key 所属的类实现 Comparable 接口,或者自定义一个实现了 Comparator 接口的比较器,传给 TreeMap 用于 key 的比较

8. HashSet

HashSet 底层就是基于 HashMap 实现的。HashSet 的源码⾮常⾮常少,因为除了 clone() 、 writeObject() 、 readObject() 是 HashSet⾃⼰不得不实现之外,其他⽅法都是直接调⽤ HashMap 中的⽅法。


本作品系原创,采用《署名-非商业性使用-禁止演绎4.0 国际》许可协议.转载请说明出处
本文链接:https://www.upupor.com/u/MMvJlWA 复制

无内容

推荐阅读