HashMap相关面试题
HashMap相关面试题
- HashMap的实现原理
- HashMap中数组和链表的作用
- hash冲突的解决方法
- 可以用Linkedlist去替代数组吗?
- HashMap的扩容条件
- 为什么扩容是2的次幂
- HashMap的put元素过程
- HashMap的get元素过程
- 你知道哪些hash算法
- 说说String的hashcode的实现
- JDK1.8对HashMap的改进
- 为什么在解决hash冲突的时候,不直接用红黑树?而选择先用链表,再转红黑树?
- 可以使用二叉查找树来替换红黑树吗?
- 当链表转为红黑树后,什么时候退化为链表?
- HashMap在并发编程环境下有什么问题?
- 如何解决并发问题
- key可以为null值吗?
- 一般用什么作为HashMap的key
- 当使用可变类作为HashMap的key有什么问题?
- 如果让你实现一个自定义的class作为HashMap的key该如何实现?
- HashMap和Hashtable的区别
- HashMap多线程操作导致的死循环问题
- ConcurrentHashMap和HashTable的区别
HashMap的实现原理
HashMap底层采用的是数组+链表实现的。一个Entry数组存储键值对,每一个键值对就是一个Entry实体。而Entry类实际是一个单向链表。在jdk1.8中规定了链表长度大于8的时候,链表转换为红黑树。
HashMap中数组和链表的作用
- 数组用于确定桶的位置,获得桶位置的计算方式是元素的key的hash值对数组长度取模。
- 链表解决hash冲突的问题。当hash值一样的时候就在数组上形成链表,而且才用的是头插法。什么是头插法?就是后进来的直接插入在头部。为什么呢?因为创始人觉得后进来的被访问的可能性更大。
hash冲突的解决方法
- 开放定址法
- 链地址法
- 再哈希法
- 公共溢出区法
可以用Linkedlist去替代数组吗?
可以的。但是在得到hash值的情况下,通过数组去确定桶的位置更快。
HashMap的扩容条件
如果bucket超过了load factor * current capacity,
就要resizeload fator = 0.75
,为了最大可能的避免哈希冲突。current capacity
为当前数组大小
为什么扩容是2的次幂
- HashMap为了存取高效,要尽量较少碰撞,就是要尽量把数据分配均匀,每个链表长度大致相同,这个实现就在把数据存到哪个链表中的算法;这个算法实际就是取模
,hash%length
。
但是,这种运算不如位移运算快。
因此,源码中做了优化hash&(length-1)
。
也就是说hash%length==hash&(length-1)
所以,保证容积是2的n次方,是为了保证在做(length-1)
的时候,每一位都能&1
。
HashMap的put元素过程
- 对key的hashCode()经过扰动函数处理得到hash值,然后通过(n-1)&hash判断当前元素存储的位置。
- 如果没有碰撞,直接放入bucket里
- 如果碰撞了,就判断该元素与要存入的元素的hash值以及key是否相同。如果相同就更新value,保证key的唯一性。如果不同就通过拉链法解决冲突。以链表的形式存入bucket后。
- 如果链表中的元素达到了8个,就转为红黑色。
- 如果bucket满了就resize
HashMap的get元素过程
- 根据key的hashCode()进行hash运算,计算index
- 如果在bucket中第一个节点就命中了就返回;如果有冲突使用key.equal(k)去查找对应的Entry。
你知道哪些hash算法
- Hash函数是指把一个大范围映射到一个小范围。把大范围映射到一个小范围的目的往往是为了节省空间,使得数据容易保存。
- 比较出名的有MurmurHash、MD4、MD5
说说String的hashcode的实现
可见String的hashCode()的计算思想是:以31为权重,每一位为字符的ASCII值进行运算,用自然溢出来取等效值。
哈希计算公式可以计为s[0]31^(n-1) + s[1]31^(n-2) + … + s[n-1]
那为什么以31为质数呢?
主要是因为31是一个奇质数,所以31* i=32* i-i=(i<<5)-i,这种位移与减法结合的计算相比一般的运算快很多。
JDK1.8对HashMap的改进
- 增加了当链表的长度大于8的时候,链表转换为红黑树。
- 优化了高位运算hash算法:h^(h>>>16)
- 扩容后,元素要么是在原位置,要么在原位置再移动2次幂的位置,且链表顺序不发生改变。解决了HashMap死循环的问题
为什么在解决hash冲突的时候,不直接用红黑树?而选择先用链表,再转红黑树?
因为红黑树需要进行左旋,右旋,变色这些操作来保持平衡,而单链表不需要。
当元素小于8个当时候,此时做查询操作,链表结构已经能保证查询性能。当元素大于8个的时候,此时需要红黑树来加快查询速度,但是新增节点的效率变慢了。
因此,如果一开始就用红黑树结构,元素太少,新增效率又比较慢,无疑这是浪费性能的。
可以使用二叉查找树来替换红黑树吗?
可以,但是二叉查找树有可能退化为线性结构。遍历查找会变得很慢。
当链表转为红黑树后,什么时候退化为链表?
为6
的时候退转为链表。中间有个差值7可以防止链表和树之间频繁的转换。
HashMap在并发编程环境下有什么问题?
- (1.8之前存在的问题)多线程扩容,引起的死循环问题。并发的时候Rehash会造成元素之形成一个循环链表。
- 多线程put的时候可能导致元素丢失
- put非null元素后get出来的却是null
如何解决并发问题
使用concurrentHashMap,线程安全集合类。注意:Hashtable虽然是线程安全的,但是其实已经被废弃了,没有怎么使用了。
key可以为null值吗?
可以。key为null时,hash算法最后的值以0计算。放在数组第一个的位置。
一般用什么作为HashMap的key
一般用Integer,String这种不可变的类作为HashMap的key。String最为常用。
- 因为字符串是不可变的,所以在它创建的时候hashcode就被缓存了,不需要重新计算。这就使得字符串很适合作为Map中的键,字符串的处理速度要快过其它的键对象。这就是HashMap中的键往往都使用字符串。
- 因为获取对象的时候要用到equals()和hashCode()方法,那么键对象正确的重写这两个方法是非常重要的,这些类已经很规范的覆写了hashCode()以及equals()方法。
当使用可变类作为HashMap的key有什么问题?
hashCode可能发生变化,导致get不到。
如果让你实现一个自定义的class作为HashMap的key该如何实现?
两个重要的考点:
重写hashcode和equals方法
- 如何设计一个不变类
- 第一个问题的原则:
(1)两个对象相等,hashcode一定相等
(2)两个对象不等,hashcode不一定不等
(3)hashcode相等,两个对象不一定相等
(4)hashcode不等,两个对象一定不等 - 第二个问题的设计原则:
(1)类添加final修饰符,保证类不被继承。
(2)保证所有成员变量必须私有,并且加上final修饰
(3)不提供改变成员变量的方法,包括setter
(4)通过构造器初始化所有成员,进行深拷贝(deep copy)
错误的初始化方式:
这种方式不能保证不可变性,myArray和array指向同一块内存地址,用户可以在ImmutableDemo之外通过修改array对象的值来改变myArray内部的值。
正确的方式(深度拷贝):
(5)在getter方法中,不要直接返回对象本身,而是克隆对象,并返回对象的拷贝
这种做法也是防止对象外泄,防止通过getter获得内部可变成员对象后对成员变量直接操作,导致成员变量发生改变。
String类型重载了hashCode()以根据字符串的内容来返回HashCode值,所以相同内容的字符串具有相同的Hash Code
HashMap和Hashtable的区别
- 线程是否安全:HashMap的线程是不安全的,解决方法:使用ConcurrentHashMap。Hashtable线程安全,所有的方法都被
synchronized
修饰。 - 效率:由于Hashtable是线程安全的,因此效率低于HashMap。而且Hashtable基本已经没有使用了。
- Null key问题:HashMap中,可以有一个null且位于数组第一个,值可以有多个为null。而Hashtable中不能以null作为空值。
- 初始容量和大小不同:
- HashMap的初始默认容量为16,且每次扩容的时候,它的扩容是2的次幂的大小。即使是给定了HashMap的大小也是会将其扩容为2的次幂的大小。(HashMap的底层
tableSizefor
方法保证了其扩容的机制)。
至于为什么是2的次幂是因为为了减少碰撞使得存取高效。HashMap在使用之前还需要对数组长度去模运算(index = hash%length),得到的余数才是用以存放对应数组的下标。源码中的计算方式写法为:hash&(length-1)。 也就是说
hash%length==hash&(length-1)所以,保证容积是2的n次方,是为了保证在做
(length-1)的时候,每一位都能
&1`
(原本上面有,但是自己在写一次加深印象)
HashMap多线程操作导致的死循环问题
我们都知道在bucket里面的值大于load factor * current size的时候需要做一次resize。(resize是Rehash中的一个步骤,Rehash包括resize方法和transfer方法)
。
并发下的Rehash 会造成元素之间会形成一个循环链表。不过,jdk 1.8 后解决了这个问题
,但是还是不建议在多线程下使用 HashMap,因为多线程下使用 HashMap 还是会存在其他问题比如数据丢失。并发环境下推荐使用 ConcurrentHashMap 。
其实我有点懵。jdk1.8解决了这个问题吗?怎么解决的?官方说了吗?1.8变的就是链表长度超过8就变成红黑树,小于6就退化为链表。而红黑树的引入不是为了解决查询效率问题吗?而且有很多人也发现了1.8中仍然导致了rehash的死循环问题啊?
ps:我觉得官方的意思是:HashMap我没考虑并发问题,给你设计了ConcurrentHashMap自己去用。别老是傻乎乎的并发场景下使用HashMap。菜鸡の疑惑
ConcurrentHashMap和HashTable的区别
前面我们知道了HashMap不是同步的,官方建议使用ConcurrentHashMap去解决并发问题。同时也知道了Hashtable和HashMap很相似的这个数据结构,虽然很多地方不如HashMap但是却可以进行同步。
而两者的区别:
- 底层数据结构:
- 在JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现,而在jdk1.8中才采用了和HashMap一样的数据+链表/红黑树。其实这样说也不对,因为HashMap在7的时候也是数组+链表。
- Hashtable的底层数据结构采用也是数组+链表 的形式。(也就是说时代变了,大人还没变,所以现在Hashtable没进步,就被淘汰了)
- 实现线程安全的方式不同:
在JDK1.7的时候,ConcurrentHashMap(分段锁) 对整个桶数组进行了分割分段(Segment),每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率。 到了 JDK1.8 的时候已经摒弃了Segment的概念,而是直接用数组+链表+红黑树的数据结构来实现,并发控制使用 synchronized 和 CAS 来操作。(JDK1.6以后 对 synchronized锁做了很多优化) 整个看起来就像是优化过且线程安全的 HashMap,虽然在JDK1.8中还能看到 Segment 的数据结构,但是已经简化了属性,只是为了兼容旧版本;
Hashtable(同一把锁) :使用 synchronized 来保证线程安全,效率非常低下。当一个线程访问同步方法时,其他线程也访问同步方法,可能会进入阻塞或轮询状态,如使用 put 添加元素,另一个线程不能使用 put 添加元素,也不能使用 get,竞争会越来越激烈效率越低。
因此,虽然Hashtable的实现比concurrentHashMap的实现简单。但是效率上差很多,只是简单的锁住,在每次进行同步的操作上都很机械。
图片来源:http://www.cnblogs.com/chengxiao/p/6842045.html
内容来源:JavaGuide,微信公众号:孤独烟