java集合详解和集合面试题目 java 集合面试总结 _java集合详解和集合面试题目

文章插图

文章插图
本章节主要分享一些Java中的集合在面试中常问的高频问题，这里给出的是相对比较简略的答案，不过针对面试的回答，这些就足够了，另外就是一定要加入自己的个人理解，不要背书形式的回答。
1.Java中的集合框架有哪些？
回答：Java 集合框架主要包括两种类型的容器，一种是集合（Collection），存储一个元素集合，另一种是图（Map），存储键/值对映射。
Collection 接口又有 3 种子类型， List、Set 和 Queue ，再下面是一些抽象类，最后是具体实现类，常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、TreeMap、LinkedHashMap 等等。

2.ArrayList和LinkedList的底层实现和区别？
【java集合详解和集合面试题目 java 集合面试总结】回答：ArrayList底层使用的是 Object数组；LinkedList底层使用的是双向链表数据结构。
ArrayList:增删慢、查询快，线程不安全，对元素必须连续存储。
LinkedList:增删快，查询慢，线程不安全。
追问：说说ArrayList的扩容机制？
回答：通过阅读ArrayList的源码我们可以发现当以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10 。当插入的元素个数大于当前容量时，就需要进行扩容了， ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右。
3.HashMap的底层实现？扩容？是否线程安全？
回答：在jdk1.7之前HashMap是基于数组和链表实现的，而且采用头插法。
而jdk1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64 ，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。采用尾插法。
HashMap默认的初始化大小为 16 。当HashMap中的元素个数之和大于负载因子*当前容量的时候就要进行扩充，容量变为原来的 2 倍。（这里注意不是数组中的个数，而且数组中和链/树中的所有元素个数之和！）

注意：我们还可以在预知存储数据量的情况下，提前设置初始容量（初始容量 = 预知数据量 / 加载因子）。这样做的好处是可以减少 resize() 操作，提高 HashMap 的效率
美团面试的时候问到这个问题，还给出具体的值，让我算出初始值设置为多少合适？

HashMap是线程不安全的，其主要体现：
1.在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失。
2.在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。
追问：HashMap扩容的时候为什么是2的n次幂？
回答：数组下标的计算方法是（n-1）& hash ，取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次方；）。并且采用二进制位操作 & ，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是2的幂次方。
追问：HashMap的put方法说一下。
回答：通过阅读源码，可以从jdk1.7和1.8两个方面来回答
1.根据key通过哈希算法与与运算得出数组下标
2.如果数组下标元素为空，则将key和value封装为Entry对象（JDK1.7是Entry对象， JDK1.8是Node对象）并放入该位置。
3.如果数组下标位置元素不为空，则要分情况
(i)如果是在JDK1.7 ，则首先会判断是否需要扩容，如果要扩容就进行扩容，如果不需要扩容就生成Entry对象，并使用头插法添加到当前链表中。
(ii)如果是在JDK1.8中，则会先判断当前位置上的TreeNode类型，看是红黑树还是链表Node
? (a)如果是红黑树TreeNode ，则将key和value封装为一个红黑树节点并添加到红黑树中去，在这个过程中会判断红黑树中是否存在当前key ，如果存在则更新value 。
? (b)如果此位置上的Node对象是链表节点，则将key和value封装为一个Node并通过尾插法插入到链表的最后位置去，因为是尾插法，所以需要遍历链表，在遍历过程中会判断是否存在当前key ，如果存在则更新其value ，当遍历完链表后，将新的Node插入到链表中，插入到链表后，会看当前链表的节点个数，如果大于8 ，则会将链表转为红黑树
? (c)将key和value封装为Node插入到链表或红黑树后，在判断是否需要扩容，如果需要扩容，就结束put方法。
追问：HashMap源码中在计算hash值的时候为什么要右移16位？
回答：我的理解是让元素在HashMap中更加均匀的分布，具体的可以看下图，下图是《阿里调优手册》里说的。

4.Java中线程安全的集合有哪些？
Vector：就比Arraylist多了个同步化机制（线程安全）。
Hashtable：就比Hashmap多了个线程安全。
ConcurrentHashMap:是一种高效但是线程安全的集合。
Stack：栈，也是线程安全的，继承于Vector 。
追问：说一下ConcurrentHashMap的底层实现，它为什么是线程安全的？
回答：在jdk1.7是分段的数组+链表， jdk1.8的时候跟HashMap1.8的时候一样都是基于数组+链表/红黑树。
ConcurrentHashMap是线程安全的
（1）在jdk1.7的时候是使用分段所segment ，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。
（2）在jdk1.8的时候摒弃了 Segment的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。synchronized只锁定当前链表或红黑二叉树的首节点。
5.HashMap和Hashtable的区别
回答：
（1）线程是否安全： HashMap 是非线程安全的， HashTable 是线程安全的,因为 HashTable 内部的方法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）；
（2）对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value ，但 null 作为键只能有一个， null 作为值可以有多个；HashTable 不允许有 null 键和 null 值，否则会抛出 NullPointerException 。
（3）初始容量大小和每次扩充容量大小的不同： ① 创建时如果不指定容量初始值， Hashtable 默认的初始大小为 11 ，之后每次扩充，容量变为原来的 2n+1 。HashMap 默认的初始化大小为 16 。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的tableSizeFor()方法保证，下面给出了源代码）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小,后面会介绍到为什么是 2 的幂次方。
（4）底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64 ，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。
（5）效率：因为线程安全的问题， HashMap 要比 HashTable 效率高一点。另外， HashTable 基本被淘汰，不要在代码中使用它；
6.HashMap和TreeMap的区别？
回答：
1、HashMap是通过hash值进行快速查找的；HashMap中的元素是没有顺序的；TreeMap中所有的元素都是有某一固定顺序的，如果需要得到一个有序的结果，就应该使用TreeMap；
2、HashMap和TreeMap都是线程不安全的；
3、HashMap继承AbstractMap类；覆盖了hashcode() 和equals() 方法，以确保两个相等的映射返回相同的哈希值；
TreeMap继承SortedMap类；它保持键的有序顺序；
4、HashMap：基于hash表实现的；使用HashMap要求添加的键类明确定义了hashcode() 和equals() （可以重写该方法）；为了优化HashMap的空间使用，可以调优初始容量和负载因子；
TreeMap：基于红黑树实现的；TreeMap就没有调优选项，因为红黑树总是处于平衡的状态；
5、HashMap：适用于Map插入，删除，定位元素；
TreeMap：适用于按自然顺序或自定义顺序遍历键（key）