位置: IT常识 - 正文
HashMap面试相关(hashmap 面试)
编辑：rootadmin推荐整理分享HashMap面试相关(hashmap 面试)，希望有所帮助，仅作参考，欢迎阅读内容。
文章相关热门搜索词:hashmap工作原理面试,面试问hashmap的原理,应该怎么回答,hashmap数据结构面试,hashmap面试问题,面试问hashmap的原理,应该怎么回答,hashmap数据结构面试,hashmap工作原理面试,hashmap面试问题,内容如对您有帮助，希望把文章链接给更多的朋友！
get:
1)调用k的hashCode()计算出哈希值,并通过哈希算法转换成数组的下标.
2)通过上一步哈希算法转换成数组的下标后,通过数组快速定位到某个位置.如果这个位置上什么都没有,返回null如果有,则拿着K和单向链表上的每一个节点K进行equals,如果所有equals都返回false,则返回null若true,则返回该value.
resize方法: 两个职责,创建初始存储表格,或者在容量不满足需求的时候,进行扩容.
具体键值对在哈希表中的位置取决于该位运算: i = (n-1) & hash
热点问题:为什么HashMap要树化?本质上是因为安全问题.因为,在元素的存放过程中,如果一个对象哈希冲突,都被放到一个桶里,则会形成一个链表,而链表的查询是线性的会严重影响存取的性能.而现实情况中,构造哈希冲突的数据并不是非常复杂的事情,恶意代码就会利用这些数据与服务器大量交互,导致服务器端cpu大量占用,这就构成了哈希碰撞拒绝服务攻击.
ps:用哈希碰撞发起拒绝服务攻击(DOS，Denial-Of-Service attack),常见的场景是攻击者可以事先构造大量相同哈希值的数据，然后以JSON数据的形式发送给服务器，服务器端在将其构建成为Java对象过程中，通常以Hashtable或HashMap等形式存储，哈希碰撞将导致哈希表发生严重退化，算法复杂度可能上升一个数据级，进而耗费大量CPU资源。
HashMap,HashTable,TreeMap,LinkedHashMap的区别HashMap继承自AbstractMap类,而HashTable继承自Dictionary类,不过它们都同时实现了map,cloneable,serializable接口.存储的内容是基于 key-value的键值对映射,key不能重复,一个key只能映射一个value.HashSet的底层就是基于HashMap实现的.
HashTable的key,value都不能为nullHashMap key 和 value 都可以为null,但只能有一个key为null,可以有多个null的valueTreeMap 键值都不能为null
一般情况下,选用HashMap,因为HashMap的键值对在取出时是随机的,依据key的hashCode和键的equals方法来存取数据,具有很快的访问速度,所以在map中插入,删除及索引元素时效率较高.而TreeMap的键值对在取出时是排过序的,所以效率低一点.
TreeMap是基于红黑树的一种提供顺序访问的map,与HashMap不同的是它的get,put,remove之类的操作都是o(log(n))的时间复杂度,具体顺序可以由指定的Comparator来决定,或者根据键的自然顺序来判断.
LinkedHashMap适合需要输出的顺序和输入的顺序相同的情况
HashMap是线程不安全的,HashTable是线程安全的.所以HashTable的效率比不上HashMap
前者默认初始化数组大小为16,后者为11,扩容时,扩大两倍,后者扩大两倍+1
HashMap需要重新计算hash值,而hashTable直接使用对象的hashCode
HashMap在1.7和1.8之间的变化1.7中采用数组+链表,1.8采用数组+链表/红黑树1.7扩容时需要重新计算哈希值和索引位置,1.8并不重新计算哈希值,巧妙地采用和扩容后容量进行&操作来计算新的索引位置.1.7采用头插法: 扩容时会改变链表中元素的原本顺序,以至于在并发场景下导致链表成环的问1.8采用尾插法: 扩容时会保持链表原本的顺序,避免了链表成环的问题.
当两个对象的hashCode相同时会发生什么?
hashCode相同,equals不一定为true,所以两个对象所在数组的下标相同,"碰撞"就此发生.会存储在数组该位置的链表(红黑树)中.你知道hash的实现吗?为什么要这样实现?
1.8中,通过hashCode()的高16位异或低16位实现的
(h = k.hashCode()) ^ (h >>> 16)主要是从速度,功效和质量来考虑的,减少系统的开销,也不会因为高位没有参与下标的计算,从而引起碰撞
用异或运算符,保证了对象的hashCode的32位值只要有一位发生改变,整个hash()返回值就会改变,尽可能的减少碰撞
拉链法导致的链表过深问题为什么不用二叉树代替,而选择红黑树?为什么不一直使用红黑树?红黑树是为了解决二叉查找树的缺陷,二叉查找树在特殊情况下会变成一条线性结构(这就跟原来使用链表结构一样了,同样会造成很深的问题),遍历查找会非常慢.红黑树在插入新数据后会通过左旋,右旋或者变色操作来保持平衡,引入红黑树是为了查找数据快,解决链表查询深度的问题,红黑树属于平衡二叉树,尽管为了保持平衡会付出代价,但该代价损耗的资源相比遍历线性链表来说要少.所以,当长度大于8的时候,会使用红黑树.而为什么是8,是因为符合泊松分布,为8时资源损耗相对来说较少.HashMap和CuncurrentHashMap的区别?ConcurrentHashMap类是java并发包java.util.concurrent中提供的一个线程安全且高效的HashMap实现.1.7中ConcurrentHashMap采用分段锁(ReentrantLock + segment +hashEntry),相当于把一个HashMap分成多个段,每段分配一把锁,这样支持多线程访问.锁粒度:基于segment,包含多个HashEntry1.8中采用CAS + synchronized + Node + 红黑树.锁粒度: Node.锁粒度降低了HashTable则使用synchronized关键字加锁区别: ConcurrentHashMap键值对都不允许为nullConcurrentHashMap简单介绍一下?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改为NodeConcurrentHashMap的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获取到的值为nullConcurrentHashMap为什么不能解决二义性问题
因为ConcurrentHashMap是一个用在多线程并发的map容器,不能put null 是因为无法分辨是key没找到null,还是有key的值为null.这在多线程里没法保证会不会有其他线程修改为null键和null值的情况,所以不让put null.参考文档HashMap详解
面试:HashMap夺命二十一问
深入浅出ConcurrentHashMap
ConcurrentHashMap(1.8)讲解及常见面试题
