2022年java（集合HashMap）面试题

77 阅读 0 评论 51 点赞

我是靠谱客的博主文艺跳跳糖，最近开发中收集的这篇文章主要介绍2022年java（集合HashMap）面试题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

HashMap的底层结构变化：
HashMap在jdk1.7版本的时候，底层是一个数组+链表的数据结构，在jdk1.8的时候，底层是一个数组+链表+红黑树的数据结构。关于链表和红黑树之间的转换，当链表上的数据个数大于8，且哈希桶容量大于等于64的时候，node数组所在的索引位置上的链表将会转换为红黑树存储，当红黑树的节点小于等于6的时候，红黑树将会转换为链表的形式存储，这是他底层结构的一个变化。满足大于8的时候，调用treeifyBin()方法转换为红黑树。

HashMap的扩容机制：
另一个是关于hash桶的数量，它的默认容量是16，负载因子是0.75，当添加的元素大于0.75*16=12的时候，创建一个新的entry空数组，长度是原数组的两倍，等同于2的n次幂，并且对之前的元素进行hash计算，存放到新的hash桶中，以链表或者红黑树的方式排列。
补充：扩容？怎么扩容的呢？
扩容：创建一个新的entry空数组，长度是原数组的两倍。
rehash：遍历原entry数组，把所有的entry重新hash到
新数组中。

第二种答法：HashMap的扩容机制原理
1.7版本
1.先生成新数组
2.遍历老数组中的每个位置上的链表上的每个元素
3.取每个元素的key，并基于新数组长度，计算出每个元素在新数组中的下标
4.将元素添加到新数组中去
5.所有元素转移完了之后，将新数组赋值给HashMap对象的table属性
1.8版本
1.先生成新数组
2.遍历老数组中的每个位置上的链表或红黑树
3.如果是链表，则直接将链表中的每个元素重新计算下标，并添加到新数组中去
4.如果是红黑树，则先遍历红黑树，先计算出红黑树中每个元素对应在新数组中的下标位置
a.统计每个下标位置的元素个数
b.如果该位置下的元素个数超过了8，则生成一个新的红黑树，并将根节点添加到新数组的对应位置
c.如果该位置下的元素个数没有超过8，则生成一个链表，并将链表的头节点添加到新数组的对应位置
5.所有元素转移完了之后，将新数组赋值给HashMap对象的table属性

ConcurrentHashMap的扩容机制
1.7版本
1.1.7版本的ConcurrentHashMap是基于Segment分段实现的
2.每个Segement相当于一个小型的HashMap
3.每个Segement内部会进行扩容，和HashMap的扩容逻辑类似
4.先生成新的数组，然后转移元素到新数组中
5.扩容的判断也是每个Segment内部单独判断的，判断是否超过阈值
1.8版本
1.1.8版本的ConcurrentHashMap不再基于Segment实现
2.当某个线程进行put时，如果发现ConcurrentHashMap正在进行扩容那么该线程一起进行扩容
3.如果某个线程put时，发现没有正在进行扩容，则将key-value添加到ConcurrentHashMap中，然后
判断是否超过阈值，超过了则进行扩容
4.ConcurrentHashMap是支持多个线程同时扩容的
5.扩容之前也先生成一个新的数组
6.在转移元素时，先将原数组分组，将每组分给不同的线程来进行元素的转移，每个线程负责一组或多组的元素转移工作

HashMap在jdk1.7与jdk1.8之间的不同点：
（1）jdk1.7中，new HashMap（）的时候，底层会创建一个长度为16的数组。
（2）jdk1.8中，只有在首次调用put（）时，才会创建一个长度为16的数组。
（3）jdk1.7的底层数据结构:数组+链表，jdk1.8的底层数据结构：数组+链表+红黑树。
（4）jdk1.7的数组类型是entry[],jdk1.8的数组类型是node[]。

HashMap在jdk7中的底层实现原理：
首先，put(key1,value1)时，调用key1所在类的hashCode()方法，得到一个hash值，这个hash值根据某种hash算法计算，求出在数组中的存放位置。
当存放位置不存在其他元素时，则添加成功；------情况一
当存放位置存在其他一个或多个元素（以链表的形式存在），则继续比较他们的hash值，
如果hash值不相同时，则添加成功；------情况二
如果hash值相同时，则key1调用所在类的equals(key2)进行比较，
如果equeals返回false时，添加成功；-------情况三
如果equeals返回true时，value1替换value2。
小总结：情况二和情况三，（key1,value1）元素和原来的元素的存储数据的方式是以链表的形式存储。

HashMap是不是线程安全的：
他不是线程安全的，由于put()和putVal()代码没有同步，插入一个value的时候会进行判空处理，在多线程的时候，如果正好2个线程都检查到对应位置是空的，都会插进去的话，先插进去的就会被后插进去的节点覆盖，而不是都挂在后面。就会出现数据错误，导致线程不安全。

默认初始化大小是多少？为啥是这么多？为啥大小都是2的幂？
（1）默认初始化大小是16，是2的次幂
（2）而当数组长度为16时，即为2的n次方时，2n-1得到的二进制数的每个位上的值都为1，这使得在低位上&时，得到的和原hash的低位相同，加之hash()方法对key的hashCode的优化，使得只有相同的hash值的两个值才会被放到数组中的同一个位置上形成链表。所以说，当数组长度为2的n次幂的时候，不同的key计算的index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。
（3）如果是其他数字，会调用tableSizeFor(int cap)方法，帮你优化成2的次幂。继续运行这段代码，会发现如果传3会优化为4，传5会优化为8，以此类推，都会优化为2的次幂。
传负数、0、1，会被优化为1。

ConcurrentHashMap与HashMap的区别，以及怎么简单自己实现ConcurrentHashMap？
1.HashMap是线程不安全的，所以效率相对于HashTable较高。HashTable是线程安全的，所以相对于HashMap效率较低。
2.ConcurrentHashMap可以看作是HashMap的线程安全版本，但是内部实现机制与HashMap不同。在不同版本的JDK中有不同的实现。
3. HashMap的键值对允许有null，但是ConCurrentHashMap都不允许。HashTable也是都不允许。这个Segment就是ConcurrentHashMap为了线程安全又提高效率采用的方法，将整个Map进行分割，分割成多个较小的分区。ConcurrentHashMap的线程安全问题已经明确了，ConcurrentHashMap – Segment – lock 保证了线程安全并且获取到了比HashTable的syn更加高效率的操作。既然不能全锁（HashTable）又不能不锁（HashMap），所以就搞个部分锁，只锁部分，用到哪部分就锁哪部分。一个大仓库，里面有若干个隔间，每个隔间都有锁，同时只允许一个人进隔间存取东西。但是，在存取东西之前，需要有一个全局索引，告诉你要操作的资源在哪个隔间里，然后当你看到隔间空闲时，就可以进去存取，如果隔间正在占用，那你就得等着。
通过把整个Map分为N个Segment（类似HashTable），可以提供相同的线程安全，但是效率提升N倍，默认提升16倍。

HashMap的get()方法的工作原理？
只需要根据key的hashcode算出元素在数组中的下标,之后遍历Entry对象链表,直到找到元素为止。
补充：调用key所在类的hashcode方法得到hash值，
hash值通过某种算法得出数组的索引即存放位置，然后迭代Eentry对象链表，调用equals方法，如果返回值为ture,get方法返回Entry对象中的value值，返回false，则get方法返回null。

当两个对象的hashcode相同会发生什么？
会发生哈希碰撞，生成一个链表，先插入的数据到链表的尾部，后插入的数据到链表的头部。
补充：jdk7最新插入的数据会放到数组中，原来的数据会挤到链表中去，会采用头部插入法，，jdk8最新插入的数据会放到链表中去，原来的数据会放到数组中来，采用尾部插入法。

可以使用CocurrentHashMap来代替Hashtable吗？为什么
可以，它们都可以用于多线程的环境，但是当Hashtable的大小增加到一定的时候，性能会急剧下降，因为迭代时需要被锁定很长的时间。因为ConcurrentHashMap引入了分割(segmentation)，不论它变得多么大，仅仅需要锁定map的某个部分，而其它的线程不需要等到迭代完成才能访问map。简而言之，在迭代的过程中，ConcurrentHashMap仅仅锁定map的某个部分，而Hashtable则会锁定整个map。

如果HashMap的大小超过了负载因子(loadfactor)定义的容量，怎么办？
默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。