精选8道Java集合最常见面试题,进大厂99%都会被问到,限时送!

2021/4/29 22:26:38

本文主要是介绍精选8道Java集合最常见面试题,进大厂99%都会被问到,限时送!,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Hello,今天给各位童鞋们分享java常见的面试题,想在面试、工作中脱颖而出?想在最短时间内快速掌握Java的核心基础知识点?那赶紧拿出小本本记下来吧!

1. List,Set,Map三者的区别?

List:一个有序(元素存入集合的顺序和取出的顺序一致)容器,元素可以重复,可以插入多个null元素,元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector Set:一个无序(存入和取出顺序有可能不一致)容器,不可以存储重复元素,只允许存入一个null元素,必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet Map是一个键值对集合,存储键、值和之间的映射。 Key无序,唯一;value 不要求有序,允许重复。Map 的常用实现类:HashMap、TreeMap、HashTable、LinkedHashMap、ConcurrentHashMap

2. 集合框架底层的数据结构

List集合 Arraylist和Vector使用的是 Object 数组, LinkedList使用双向循环链表 Set集合 HashSet(无序,唯一):基于 HashMap 实现的,HashSet的值作为key,value是Object类型的常量 LinkedHashSet继承HashSet,并且通过 LinkedHashMap 来实现的 TreeSet(有序,唯一): 红黑树(自平衡的排序二叉树。) Map集合 HashMap由数组+链表+红黑树组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的,当链表长度大于阈值(默认为8)并且数组长度大于64时,将链表转化为红黑树 LinkedHashMap(有序) 继承自 HashMap,底层仍然是数组+链表+红黑树组成。另外,LinkedHashMap 在此基础上,节点之间增加了一条双向链表,使得可以保持键值对的插入顺序 HashTable无序,数组+链表组成的,数组是 HashTable的主体,链表则是主要为了解决哈希冲突而存在的 TreeMap有序,红黑树

3. 集合框架的扩容

ArrayList和Vector默认初始容量为10,当元素个数超过容量长度时都进行进行扩容,ArrayList扩容为原来的1.5倍,而Vector扩容为原来的2倍 HashSet和HashMap默认初始容量为16,加载因子为0.75:即当元素个数超过容量长度的0.75倍时,进行扩容,扩容为原来的2倍。HashSet基于 HashMap 实现的,因此两者相同 HashTable:默认初始容量为11,加载因子为0.75,扩容策略是2倍+1,如 初始的容量为11,一次扩容后是容量为23

4. HashMap 的实现原理以及JDK1.7和JDK1.8的区别?

实现原理 数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。我们综合两者的特性,做出一种寻址容易,插入删除也容易的数据结构哈希表。并且使用最常用的一种方法—— 拉链法来实现哈希表。 数组存储的元素是一个Entry类,这个类有三个数据域,key、value(键值对),next(指向下一个Entry)。当两个key经过计算得到的index(索引)相同时,即产生哈希冲突时,用链地址法来解决哈希冲突,即通过next属性将索引值相同的链接在一起。随着map的容量或者链表长度越来越大,在进行进一步的优化,比如使用红黑树。 存储过程 HashMap个put()方法: 第一步首先将k,v封装成Node节点。第二步调用hashCode()方法得出hash值并将hash值转换成数组的下标,下标位置上如果没有任何元素(没有碰撞),就把Node节点添加到这个位置上。如果说下标对应的位置上有值(hash碰撞)。碰撞的元素与要插入的元素key值相等,直接进行value的更新;如果key值不相同,于是增长链表或者树节点的增加。插入之后判断是否进行扩容。 HashMap个get()方法: 先调用k的hashCode()方法得出哈希值,并转换成数组的下标。第二步:通过数组下标快速定位到某个位置上。如果该位置上什么都没有,则返回null。如果这个位置上有数据,那么它就会拿着参数k和单向链表上(红黑树)的每一个节点的k进行equals,如果所有equals方法都返回false,则get方法返回null。如果其中一个节点的k和参数k进行equals返回true,那么返回该节点的value。 区别 JDK1.7是数组+链表,无冲突时,存放数组;冲突时,存放链表;采用头插法。 JDK1.8是数组 + 链表 + 红黑树,无冲突时,存放数组;有冲突存放链表或者红黑树,当链表长度大于阈值(默认为8)并且数组长度大于64时,将链表转化为红黑树;树元素小于等于6时,树结构还原成链表形式。

5. HashMap是怎么解决哈希冲突的?

使用链地址法(链表)来链接拥有相同hash值的数据; 使用2次扰动函数(hash函数)来降低哈希冲突的概率,使得数据分布更平均; 引入红黑树进一步降低遍历的时间复杂度,使得遍历更快; 扰动函数的解释: 如果只使用hashCode取余,那么相当于参与运算的只有hashCode的低位,高位是没有起到任何作用的,所以我们的思路就是让hashCode的高位(与自己右移16位进行异或)也参与运算,来获取hash值,进一步降低hash碰撞的概率,使得数据分布更平均,我们把这样的操作称为扰动。

6. 为什么默认长度和扩容后的长度都必须是 2 的幂

获取数组索引的计算方式为 key 的 hash 值与数组长度减一按位与,当长度为 2 的幂时减一的值的二进制位数一定全为 1,这样数组下标 index 的值完全取决于 key 的 hash 值的后几位,只要key 的 hash 值分布均匀,HashMap 中Node也就尽可能是均匀的,所以当长度为 2 的幂时不同的 hash 值发生碰撞的概率比较小。

7. HashMap的数据的迁移机制

由于数组的容量是以2的幂次方扩容的,新的位置要么在原位置,要么在原长度+原位置的位置。因为数组长度变为原来的2倍,表现为key 的 hash 值在二进制上就是多了一个高位参与数组下标确定。此时,一个元素通过hash转换坐标的方法计算后,恰好出现一个现象:最高位是0则坐标不变,最高位是1则坐标变为“原长度+原坐标”。 因此,我们在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好。 例如:HashMap扩容之前为16,那么length-1的二进制为01111,同理扩容后的数组长度为32,length-1二进制表示为011111。我们可以看出扩容后只有一位差异,也就是多出了最左位的1,这样在通过 h&(length-1)的时候,只要h对应的最左边的那一个差异位为0,那么就是在原先位置;差异位为1,就在原长度+原位置

8. ConcurrentHashMap 底层具体实现

在 JDK1.7 中,ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。Segment 继承了 ReentrantLock,是一种可重入锁。HashEntry 则用于存储键值对数据。一个 ConcurrentHashMap 里包含一个 Segment 数组,一个 Segment 里包含一个 HashEntry 数组 ,每个 HashEntry 是一个链表结构的元素,因此 JDK1.7 的 ConcurrentHashMap 是一种数组+链表结构。当对 HashEntry 数组的数据进行修改时,必须首先获得与它对应的 Segment 锁,这样只要保证每个 Segment 是线程安全的,也就实现了全局的线程安全 在 JDK1.8 中采用Node + CAS + Synchronized来保证并发安全进行实现,synchronized只锁定当前链表或红黑二叉树的首节点。如果相应位置的Node还没有初始化,则调用CAS插入相应的数据;如果相应位置的Node不为空,如果该节点的first.hash!=-1,则对该节点加synchronized锁,更新节点或插入新节点; 如果该节点的first.hash=-1,则扩容。读操作无锁,Node节点的val和next使用volatile修饰,数组也用volatile修饰。 好啦,今天的文章就到这里,希望能帮助到屏幕前的你们!

这篇关于精选8道Java集合最常见面试题,进大厂99%都会被问到,限时送!的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程