Java集合类面试题汇总
Java类集面试题汇总
# Java集合类概述
- List(顺序好帮手): List接口存储顺序唯一,可以有序的存储对象
- Set(有序不重复): 不允许重复的集合,不会有多个元素引用相同的对象
- Map(用key找value): 使用键值对存储。Key唯一,Value可重复
Collection
- List:以特定顺序存储
- ArrayList、LinkList、Vector
- Set:不能包含重复的元素
- HashSet、TreeSet
Map
- HashMap
- HashTable
- TreeMap
Collection:Collection是一个父接口,List和Set是继承自他的子接口,Collection是最基本的集合接口,Java SDK中不提供直接继承自Collection的类,而是提供继承自他子接口的类,如List何Set。所用的Collection类都支持一个Iterator()
方法来遍历。
List:List接口是有序的,会精确的将元素插入到指定的位置,和下面的Set接口不同,List接口允许有相同元素
ArrayList:实现可变大小的数组,线程不安全
LinkedList:允许null元素,通常在首部或者尾部操作,所以常被使用做堆栈(stack)、队列(queue)和双向队列(deque)
Vector:类似于ArrayList,但Vector是同步的,Stack继承自Vector
Set:是一种不包含重复元素的Collection接口
- HashSet:不能有重复元素,底层是使用HashMap来实现的
- TreeSet: 不能有重复元素,对元素做排序(升序),底层是使用TreeMap来实现的
Map:此接口实现的Key到Value的映射,一个Map中不能包含相同的Key,每个Key只能映射一个Value
HashTable:实现了一个Key-Value的哈希表,每一个非null元素都可作为Key或者Value,HashA
Table是同步的
HashMap:和HashTable的不同之处是,非同步的,且允许null元素的存在
# List问题汇总
# 1. ArrayList和LinkedList的区别
- 线程安全: ArrayList和LinkedList都是不同步的,不保证线程安全;
- 底层实现: ArrayList底层是用Object动态数组实现的,LinkedList是用双向链表实现的
- 扩容问题: ArrayList默认长度是10,使用1.5倍数组拷贝扩容;LinkedList链表实现,不存在扩容问题
- 插入删除: ArrayList采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。指定位置插入需要将后面的元素挪后,删除时要往前覆盖,插入删除效率低下;LinkedList删除元素时间复杂度不受元素位置的影响,更换节点指向即可,插入删除效率高
- 查询访问: ArrayList是数组实现,支持任意位置元素访问,查询高效;LinkedList是链表实现,查询需要重头遍历链表,查询低下
- 内存空间占用: ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间,而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间(因为要存放直接后继和直接前驱以及数据)
# 2. ArrayList和Vector的区别
【相同点】
- 底层都使用数组实现
- 功能相同,实现增删改查等操作的方法相似
- 长度可变的数组结构
【不同点】
- Vector是早期JDK1.0 版本提供,ArrayList是JDK1.2 新版本替代Vector的
- Vector 的方法都是同步的,线程安全;ArrayList非线程安全,异步操作,但性能比Vector好
- 默认初始化容量都是10,Vector 扩容默认会翻倍,可指定扩容的大小;ArrayList默认大小是10,1.5倍扩容机制
# 3. ArrayList扩容机制
# Set问题汇总
# 1. HashSet如何检查重复
HashSet不允许插入重复元素,会对插入的元素进行排序
- hash值相同,调用equals比较
- equals比较相同,元素重复,不能插入
- equals比较不同,元素不存在,可以插入
- hash值不同,元素不存在,可以插入
# 2. Set集合与Map集合的关系
HashSet的底层是基于HashMap实现的,TreeSet的底层是基于TreeMap实现的,Set集合的元素是Map集合中的value
。
- Set集合中存放的数据不允许重复
- Map集合的数据是
key-value
的形式
# 3. hashCode,equals方法关系
hashCode
相同,则equals
不一定相同,会存在哈希冲突equals
相同,hashCode
则一定相同- equals方法被覆写过,则hashCode方法也必须被覆写
# 4. TreeSet怎么实现的?TreeMap用的什么
TreeSet基于TreeMap实现,TreeMap基于红黑树实现。TreeSet内部维持了—个简化版的TreeMap,存放的元素就是TreeMap中的key
,会对元素排序且不允许重复。
# Map问题汇总
# 1. HashMap 和 Hashtable的区别
- 线程安全: HashMap是线程不安全的,Hashtable是线程安全的。Hashtable的方法都是同步的
synchronized
修饰(不建议使用,用ConcurrentHashMap替代) - 效率: 因为线程安全的问题,HashMap 要比 HashTable 效率高。Hashtable基本被淘汰(ConcurrentHashMap替代),不要在代码中使用它;
- null-key,null-value: HashMap允许存放null-
key
,null-value
(null-key
只允许存放一次);Hashtable中put进的键值只要有一个 null,直接抛出 NullPointerException - 初始容量和扩容 : ①Hashtable 默认的初始大小为11,之后每次扩充,容量变为原来的2n+1; ①HashMap 默认的初始化大小为16。之后每次扩充,容量变为原来的2倍(HashMap 总是使用2的幂作为哈希表的大小)
- 底层数据结构: JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8)时,将链表转化为红黑树,以减少搜索时间。Hashtable 没有这样的机制。
# 2. HashMap 和 HashSet区别
HashSet 底层就是基于 HashMap 实现的。
【HashSet源码】
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
map = new HashMap<>();
}
2
3
4
5
6
7
8
9
10
11
12
我们可以看到,在初始化map时,其实就是使用了HashMap
HashMap | HashSet |
---|---|
实现了Map接口 | 实现Set接口 |
存储键值对 | 仅存储对象 |
调用 put() 向map中添加元素 | 调用 add() 方法向Set中添加元素 |
HashMap使用键(Key)计算hashCode | HashSet使用成员对象来计算hashCode值,对于两个对象来说hashCode可能相同,所以equals()方法用来判断对象的相等性 |
# 3. ConcurrentHashMap 和 Hashtable 的区别
# 4. 说说常见的hash算法,解决hash冲突的方式有哪些
目前流行的 Hash 算法包括 MD5、SHA-1 和 SHA-2
解决hash冲突的方式有哪些
- 拉链法
- 开放地址法
- 再散列法
# List、Map、Set 三个接口,存取元素时,各有什么特点
- List 以索引来存取元素,元素可重复
- Set 不能存放重复元素
- Map 保存键值对映射,映射关系可以一对一、多对一
- List 有基于数组和链表实现两种方式
- Set、Map 容器有基于哈希存储和红黑树两种方式实现
- Set 基于 Map 实现,Set 里的元素值就是 Map 里 key