Java集合

今天进行了一场面试, 面试官在问我关于HashMap的时候, 感觉自己回答的不是很好, 所以现在索性就梳理一下Java关于集合的这部分知识.

主要是问了这么几个问题:

1. HashMap是线程安全的么
2. 那线程安全的map是哪种?
3. 在定义HashMap的时候会有定义长度的习惯么?
4. HashMap的底层是怎么实现的?
5. HashMap是如何存储的?
6. HashMap最大长度是多少? 或者说是达到多大的长度就需要扩容了? (这个没答上来…)

说到Java的Collection就一定会放出这张神图

根据这张图能发现, 这一切的一切都起始于Iterable接口.

Iterable

从源码里能看到, 这个接口允许对象成为for-each的循环目标, 也就是增强型for循环, 是Java中的一种语法糖.

1
2
3
4
5

List<Object> list = new ArrayList();
// 补充: 数组也可`for-each`遍历
// Object[] list = new Object[5];

for (Object obj: list) {}

其他遍历方式

JDK 1.8 之前, Iterable只有一个方法:

1

Iterator<T> iterator();

这个接口能够创建一个轻量级的迭代器, 用于安全的遍历元素, 移除元素, 添加元素. 其中涉及了一个概念就是fail-fast.

总结起来就是: 能创建迭代器进行元素添加和删除的话, 就尽量使用迭代器进行添加和删除操作.

1
2
3

for (Iterator it = list.iterator(); it.hasNext(); ) {
	System.out.println(it.next());
}

顶层接口

Collection是一个顶层接口, 主要是用来定义集合的约定.

List接口也是一个顶层接口, 继承了Collection接口, 同时也是ArrayList, LinkedList等集合元素的父类.

Set接口位于与List接口同级的层次上, 它同时也继承了Collection接口. Set接口提供了额外的规定. 对add(), equals(), hashCode()方法提供了额外的标准.

Queue是和List, Set接口并列的Collection的三大接口之一. Queue的设计用来在处理之前保持元素的访问次序. 除了Collection基础的操作外, 对立提供了额外的插入, 读取, 检查操作.

SortSet接口直接继承与Set接口, 使用Comparable对元素进行自然排序或者使用Comparator在创建时对元素提供定制的排序规则. set的迭代器将按升序元素顺序遍历集合.

Map是一个支持key-value存储的对象, Map不能包含重复的key, 每个键最多映射一个值. 这个接口替代了Dictionary类, Dictionary是一个抽象类而不是接口.

ArrayList

ArrayList是实现List接口的可扩容数组(动态数组), 它的内部是基于数组实现的, 具体的定义:

1

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {...}

• ArrayList可以实现所有可选择的列表操作, 允许所有元素 (包括 null). ArrayList还提供了内部存储list的方法, 它能够完全替代Vector, 只有一点例外, ArrayList不是线程安全的容器.

  下面会说到Vector

• ArrayList有一个容量的概念, 这个数组的容量就是List用来存储元素的容量.

  在不声明容量的时候, 默认的是10. 当达到当前容量上限的时候, 就会进行扩容, 负载因子为0.5, 即:

  1	旧容量 * 1.5 ==> 10->15->22->33...

  ArrayList的上限为Integer.MAX_VALUE - 8(2³² - 8).

• ArrayList不是线程安全的容器, 所以可以使用线程安全的List:

  1	List list = Collections.synchronizedList(new ArrayList<>());

• ArrayList具有fail-fast快速失败机制, 当在迭代集合的过程中, 该集合发成了改变的时候, 就可能会发生fail-fast, 抛出ConcurrentModificationException异常.

Vector

Java中的Vector类是允许不同类型共存的变长数组, Java.util.Vector提供了向量(Vector)类以实现类似动态数组的功能. 在相对于ArrayList来说, Vector线程是安全的, 也就是说是同步的. 因为Vector对内部的每个方法都是简单粗暴的上锁, 所以访问元素的效率远远低于ArrayList.

还有一点在扩容上, ArrayList扩容后的数组长度会增加50%, 而Vector的扩容长度后数组是翻倍.

LinkedList

LinkedList是一个双向链表, 允许所有元素 (包括 null):

• LinkedList所有的操作都可以表现为双向性, 索引到链表的操作将遍历从头到尾, 看那个距离短为遍历顺序.

• LinkedList不是线程安全的容器, 所以可以使用线程安全的Set:

  1	List list = Collections.synchronizedList(new LinkedList<>());

• 因为LinkedList是一个双向链表, 所以没有初始化大小, 没有扩容机制.

Stack

堆栈(Stack)就是常说的后入先出的容器. 它继承了Vector类, 提供了常用的pop, push和peek操作, 以及判断stack是否为空的empty方法和寻找与栈顶距离的search方法.

HashSet

• HashSet是Set接口的实现类, 有哈希表支持 (实际上HashSet是HashMap的一个实例), 不能保证集合的迭代顺序. 允许所有元素 (包括 null).

• HashSet不是线程安全的容器, 所以可以使用线程安全的Set:

  1	Set set = Collections.synchronizedSet(new HashSet<>());

• 支持fail-fast机制.

• 因为HashSet的底层实际使用HashMap实现的, 所以和HashMap的容量和扩容机制是一致的:

  在不声明容量的时候, 默认的是16. 当达到当前容量上限的时候, 就会进行扩容, 负载因子为0.75, 即:

  1	旧容量 * 1.75 ==> 16->28->49->85...

TreeSet

TreeSet是一个基于TreeMap的NavigableSet实现. 这些元素使用他们的自然排序或者在创建时提供的Comparator进行排序, 具体取决于使用的构造函数.

• 此实现为基本操作add, remove, contains提供了log(n)的时间成本.

• HashSet不是线程安全的容器.

• 支持fail-fast机制.

LinkedHashSet

LinkedHashSet继承体系

LinkedHashSet是Set接口的Hash表和LinkedList的实现. 但是这个实现不同于HashSet的是, 它维护者一个贯穿所有条目的双向列表. 此链表定义了元素插入集合的顺序. 注意: 如果元素重新插入, 则插入顺序不会受到影响.

• LinkedHashSet有两个影响其构成的参数: 初始容量和负载因子. 它们的定义与HashSet完全相同. 但是对于LinkedHashSet, 选择过高的初始容量值的开销要比HashSet小, 因为LinkedHashSet的迭代次数不收容量影响.

• LinkedHashSet不是线程安全的容器.

• 支持fail-fast机制.

PriorityQueue

PriorityQueue(优先级队列)是AbstractQueue的实现类, 其中的元素根据自然排序(最小元素最先出)或者通过构造函数时期提供的Comparator来排序, 具体根据构造器判断. 注意: PriorityQueue不允许null元素.

• 队列的头在某种意义上是指定顺序的最后一个元素. 队列查找操作poll, remove, peek和element访问队列头部元素.
• PriorityQueue是无界队列(无限制的), 但是有内部capacity, 用户控制用于在队列中存储元素的数组大小.
• 该类以及迭代器实现了Collection, Iterator接口的所有可选方法. 这个迭代器提供了iterator()方法不能保证以任何特定顺序遍历PriorityQueue. 如果需要有序遍历的话, 可以考虑使用Arrays.sort(pq.toArray()).
• PriorityQueue必须存储的可比较的对象, 如果不是的话, 则必须指定比较器.
• PriorityQueue不是线程安全的容器, 而线程安全的类是PriorityBlockingQueue.

HashMap

HashMap是一个利用哈希表原理来存储元素的集合, 允许空的key-value键值对.

• HashMap的默认初始用量和负载因子和HashSet一致.
• HashMap不是线程安全的容器.

TreeMap

一个基于NavigableMap实现的红黑树. 这个map根据key自认排序存储, 或者通过Comparator进行定制排序.

• TreeMap为containsKey,get,put和remove方法提供了log(n)的时间开销.

• TreeMap不是线程安全的容器.

• 支持fail-fast机制.

LinkedHashMap

LinkedHashMap是Map接口的哈希表和链表的实现. 这个实现与HashMap的不同之处在于它维护了一个贯穿其所有条目的双向链表. 这个链表中定义的顺序, 通常是插入的顺序.

• 提供了一个特殊的构造器: LinkedHashMap(int,float,boolean), 其遍历的顺序是其最后一次访问的顺序.

• 可以重写removeEldestEntry(Map.Entry)方法, 以便在将新映射添加到map时强制删除过期映射的策略.

• 这个类提供了所有可选择的map操作, 并且允许null元素. 由于维护链表的额外开销, 性能可能会低于HashMap, 有一条除外: 遍历LinkedHashMap中的collection-views需要与map.size成正比, 无论其容量如何. HashMap的迭代看起来开销更大, 因为还要求时间与其容量成正比.

• LinkedHashMap有两个因素影响了它的构成: 初始容量和负载因子.

• LinkedHashMap不是线程安全的容器.

• 支持fail-fast机制.

HashTable

与HashMap不同的是, HashTable是线程安全的. 任何非空对象都可以用作键或值.

• 支持fail-fast机制.

IdentityHashMap

IdentityHashMap 是一个比较小众的Map实现类.

• IdentityHashMap不是一个通用的Map实现, 虽然这个类实现了Map接口, 但是它故意违反了Map的约定, 该约定要求在比较对象时使用equals方法, 此类仅适用于需要引用相等语义的极少数情况.

• IdentityHashMap不是线程安全的容器.

• 支持fail-fast机制.

WeakHashMap

WeakHashMap类基于哈希表的Map基础实现, 带有弱键. WeakHashMap中的entry当不再使用时还会自动移除. 也就是说, WeakHashMap中的entry不会增加其引用计数.

• 基于map接口, 是一种弱键相连, WeakHashMap里面的键会自动回收.
• 支持null键和null值.
• 支持fail-fast机制
• WeakHashMap经常用作缓存.

集合实现类特征图

下面这个表格汇总了部分集合框架的主要实现类的特征