1. HashMap数据结构是什么
Java1.7 | Java1.8 | |
---|---|---|
数据结构 | 数组+ (单向)链表 | 数组+链表+红黑树(空间换时间) |
类(称呼) | Entry | Node |
插入元素顺序不同 | 头插法: 用单链表进行的纵向延伸,当采用头插法时会容易出现逆序且环形链表死循环问题 | 尾插法 |
Java1.8插入元素为什么采用尾插法?
因为使用头插会改变链表的上的顺序,但是如果使用尾插,在扩容时会保持链表元素原本的顺序,就不会出现链表成环的问题了。具体原因如下:
头插法的插入顺序和链表原顺序相反;
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冲突?
链地址法(HashMap使用)
HashMap的解决方式是使用【链地址法】,即使用链表的方式解决。key一样的时候才会覆盖,否则就把元素放到链表的下一个位置【开放】定址法
开放定址法就是从冲突的位置再接着往下找,给冲突元素找个空位。有以下两个方法:
线行探查法: 从冲突的位置开始,依次判断下一个位置是否空闲,直至找到空闲位置
平方探查法: 从冲突的位置x开始,第一次增加12个位置,第二次增加22…,直至找到空闲的位置再哈希法
换种哈希函数,重新计算冲突元素的地址建立公共溢出区
再建一个数组,把冲突的元素放进去
3. HashMap的默认初始化长度是多少?
16
为什么是16?
作者认为16这个初始容量是能符合常用而已
同时16是2的次幂,方便位运算,位与运算比算数计算的效率高了很多
之所以选择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在线程安全的场景?
ConcurrentHashMap
使用Collections.synchronizedMap(Map)创建线程安全的map集合
Hashtable
Hashtable和HashMap的不同点
Hashtable | HashMap | 其他 | |
---|---|---|---|
键值 | 不允许键或值为null | 键值则都可以为null | |
实现方式不同 | 继承了 Dictionary类 (Dictionary 是 JDK 1.0 添加的, 貌似没人用过这个,我也没用过。) | 继承的是 AbstractMap 类 | |
初始化容量不同 | Hashtable 初始容量为:11 | HashMap 的初始容量为:16 | 两者的负载因子默认都是:0.75 |
扩容机制不同:当现有容量大于总容量 * 负载因子时 | Hashtable 扩容规则为当前容量翻倍 + 1 | HashMap 扩容规则为当前容量翻倍 | |
迭代器不同 | Hashtable 的 Enumerator 不是 fail-fast 的 | HashMap 中的 Iterator 迭代器是 fail-fast 的 | 所以,当其他线程改变了HashMap 的结构,如:增加、删除元素,将会抛出ConcurrentModificationException 异常,而 Hashtable 则不会。 |
为什么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异常
优缺点
由于对集合进行了拷贝,避免了 ConcurrentModificationException 异常,但拷贝时产生大量的无效对象,开销大。
无法保证读取到的数据是原集合中最新的数据,即迭代器进行遍历的是拷贝的集合,在遍历期间原集合发生的修改,迭代器是检测不到的。
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 中的⽅法。