Java集合框架及常见面试题

文章目录

• 一、集合是什么？
• 二、Set和List的区别
• • List
  • • Arraylist 与 linkedList 区别?
  • Set
  • • HashSet
    • HashSet如果检查重复
• 三、Map
• • HashMap
  • HashMap的底层实现
• 四、面试题
• 五、集合框架底层数据结构总结
• • Collection
  • • 1. List
    • 2. Set
  • Map

---

一、集合是什么？

---

从上面的集合框架图可以看到，Java 集合框架主要包括两种类型的容器，一种是集合（Collection），存储一个元素集合，另一种是图（Map），存储键/值对映射。Collection 接口又有 3 种子类型，List、Set 和 Queue，再下面是一些抽象类，最后是具体实现类，常用的有 ArrayList、linkedList、HashSet、linkedHashSet、HashMap、linkedHashMap 等等。

二、Set和List的区别

1. Set 接口实例存储的是无序的，不重复的数据。(底层结构是链表)

2. List 接口实例存储的是有序的，可以重复的元素。(底层结构是数组)

3. Set检索效率低下，删除和插入效率高，插入和删除不会引起元素位置改变 <实现类有HashSet,TreeSet>。

4. List和数组类似，可以动态增长，根据实际存储的数据的长度自动增长List的长度。查找元素效率高，插入删除效率低，因为会引起其他元素位置改变 <实现类有ArrayList,linkedList,Vector> 。

List Arraylist 与 linkedList 区别?

1. 是否保证线程安全： ArrayList 和 linkedList 都是不同步的，也就是不保证线程安全；

2. 底层数据结构： Arraylist 底层使用的是 Object 数组；linkedList 底层使用的是 双向链表 数据结构（JDK1.6之前为循环链表，JDK1.7取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）

3. 插入和删除是否受元素位置的影响： ① ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e) 方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element) ）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ② linkedList 采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似 O（1）而数组为近似 O（n）。

4. 是否支持快速随机访问： linkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index) 方法)。

5. 内存空间占用： ArrayList的空 间浪费主要体现在在list列表的结尾会预留一定的容量空间，而linkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。

Set HashSet

HashSet 基于 HashMap 来实现的，是一个不允许有重复元素的集合。

HashSet 允许有 null 值。

HashSet 是无序的，即不会记录插入的顺序。

HashSet如果检查重复

当你把对象加入HashSet时，HashSet会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的hashcode值作比较，如果没有相符的hashcode，HashSet会假设对象没有重复出现。但是如果发现有相同hashcode值的对象，这时会调用equals（）方法来检查hashcode相等的对象是否真的相同。如果两者相同，HashSet就不会让加入操作成功。（摘自我的Java启蒙书《Head fist java》第二版）

---

三、Map

Map是一个将key映射到value的对象.一个Map不能包含重复的key：每个key最多只能映射一个value。

HashMap

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。

HashMap 实现了 Map 接口，根据键的 HashCode 值存储数据，具有很快的访问速度，最多允许一条记录的键为 null，不支持线程同步。

HashMap 是无序的，即不会记录插入的顺序。

HashMap的底层实现

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。

相比于之前的版本， JDK1.8之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。

---

四、面试题

总结一些常见的集合面试问题

1.说说List,Set,Map三者的区别？

List(对付顺序的好帮手)： List接口存储一组不唯一（可以有多个元素引用相同的对象），有序的对象
Set(注重独一无二的性质): 不允许重复的集合。不会有多个元素引用相同的对象。
Map(用Key来搜索的专家): 使用键值对存储。Map会维护与Key有关联的值。两个Key可以引用相同的对象，但Key不能重复，典型的Key是String类型，但也可以是任何对象。

2.ArrayList和Vector的区别（是否有序、是否重复、数据结构、底层实现）

ArrayList和Vector都实现了List接口，他们都是有序集合，并且存放的元素是允许重复的。它们的底层都是通过数组来实现的，因此列表这种数据结构检索数据速度快，但增删改速度慢。

而ArrayList和Vector的区别主要在两个方面：

第一，线程安全。Vector是线程安全的，而ArrayList是线程不安全的。因此在如果集合数据只有单线程访问，那么使用ArrayList可以提高效率。而如果有多线程访问你的集合数据，那么就必须要用Vector，因为要保证数据安全。

第二，数据增长。ArrayList和Vector都有一个初始的容量大小，当存储进它们里面的元素超过了容量时，就需要增加它们的存储容量。ArrayList每次增长原来的0.5倍，而Vector增长原来的一倍。ArrayList和Vector都可以设置初始空间的大小，Vector还可以设置增长的空间大小，而ArrayList没有提供设置增长空间的方法。

3.HashMap 实现原理

在 JDK1.6/1.7，数组 + 链表；
在 JDK 1.8，数组 + 红黑树。
具体说来，

对于 HashMap 中的每个 key，首先通过 hash function 计算出一个哈希值，这个哈希值就代表了在桶里的编号，而“桶”实际上是通过数组来实现的，但是桶有可能比数组大呀，所以把这个哈希值模上数组的长度得到它在数组的 index，就这样把它放在了数组里。

这是理想情况下的 HashMap，但现实中，不同的元素可能会算出相同的哈希值，这就是哈希碰撞，即多个 key 对应了同一个桶。

为了解决哈希碰撞呢，Java 采用的是 Separate chaining 的解决方式，就是在碰撞的地方加个链子，也就是上文说的链表或者红黑树。

4.List 和 Map 区别？（数据结构，存储特点）

这个要从两个方面来回答，一方面是List和Map的数据结构，另一方面是存储数据的特点。在数据结构方面，List存储的是单列数据的集合，而Map存储的是key、value类型的数据集合。在数据存储方面，List存储的数据是有序且可以重复的，而Map中存储的数据是无序且key值不能重复（value值可以重复）。

5.如何选用集合?

主要根据集合的特点来选用，比如我们需要根据键值获取到元素值时就选用Map接口下的集合，需要排序时选择TreeMap,不需要排序时就选择HashMap,需要保证线程安全就选用ConcurrentHashMap.当我们只需要存放元素值时，就选择实现Collection接口的集合，需要保证元素唯一时选择实现Set接口的集合比如TreeSet或HashSet，不需要就选择实现List接口的比如ArrayList或linkedList，然后再根据实现这些接口的集合的特点来选用。

五、集合框架底层数据结构总结 Collection 1. List

• Arraylist： Object数组
• Vector： Object数组
• linkedList： 双向链表(JDK1.6之前为循环链表，JDK1.7取消了循环)

2. Set

• HashSet（无序，唯一）: 基于 HashMap 实现的，底层采用 HashMap 来保存元素
• linkedHashSet： linkedHashSet 继承与 HashSet，并且其内部是通过 linkedHashMap 来实现的。有点类似于我们之前说的linkedHashMap 其内部是基于 Hashmap 实现一样，不过还是有一点点区别的。
• TreeSet（有序，唯一）： 红黑树(自平衡的排序二叉树。)

Map

• HashMap： JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间
• linkedHashMap： linkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，linkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。详细可以查看：《linkedHashMap 源码详细分析（JDK1.8）》
• Hashtable： 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的
• TreeMap： 红黑树（自平衡的排序二叉树）