Java 学习笔记--容器类

Author Avatar
ChihoPang 2月 25, 2018
  • 在其它设备中阅读本文章

本文包含普通容器类和并发容器类的原理、具体实现。各知识点已经在思维导图中提供总览。

参考资料

《Java 编程思想》第11、17章
IBM Java technology:并发集合类

思维导图

img

Collection接口

独立元素的序列,所有元素都服从一条或多条规则。
img

List 接口

将元素维护在特定序列中。

ArrayList

底层实现为数组,默认元素数量为 10 个,不足时扩容成 oldCapacity + (oldCapacity >> 1)个。

LinkedList

使用双向链表实现,记录头尾结点。同时实现了 Queue 接口。

Vector(旧代码)

通过 synchronized 进行同步,其余实现细节与 ArrayList 相似,相当于 ArrayList 的线程安全版本,但不属于并发容器,属于一种同步容器。

Stack

Vector 的子类,同时拥有的栈的功能。

Set 接口

不保存重复的元素

HashSet

为快速查找而设计的 Set。
底层实现为 HashMap。将元素当作 map 的 key 值,value 置入公用 new Object()。

TreeSet

实现 NavigableSet -> SortedSet -> Set 接口,保持排序的 Set。
底层实现为 NavigableMap(默认使用 TreeMap)。实现与 HashSet 相同。

LinkedHashSet

HashSet 的子类。具备 HashSet 的查询速度,同时以插入顺序来存储。
底层实现为 LinkedHashMap ,实现与 HashSet 相同。

Queue 接口

先进先出的容器。

LinkedList

双端队列,同时实现了 List 接口。
底层实现为双向链表。

PriorityQueue

优先级队列,每次插入都会按照优先级调整存储顺序,所以每次弹出的都是最高优先级元素。
底层实现为小顶堆。

Map 接口

img

HashMap

可以传入 null 的 key\value 值。
底层为链表组成的数组。通过 key 的 hashcode 计算数组下标。
JDK8 中哈希冲突过多,链表会转红黑树,时间复杂度是O(logn),不会是O(n)
可以设置初始容量和负载因子,负载因子为当哈希表中的条目超过了容量和加载因子的乘积的时候,就会进行重哈希操作。

LinkedHashMap

HashMap 的子类,相比父类增加维护一个双向链表,链表中存放着插入的键值对,用于遍历记录顺序查找。
链表顺序(遍历顺序)为插入顺序或最近最少使用顺序(LRU)。

TreeMap

实现 NavigableMap -> SortedMap -> Map 接口,保持排序的 Map。
底层实现为红黑树,是一种自平衡二叉查找树。

Hashtable(旧代码)

底层为链表组成的数组,通过 synchronized 进行同步,线程安全。

并发容器类

Vector 和 Hashtable 这类早期容器,以及 Collections 类提供的静态装饰方法如 synchronizedList、synchronizedMap 都是使用 synchronized 进行加锁实现同步的,增加了开销且在高并发环境下不适用。
Java SE5 添加免锁容器,策略为:修改和读取可以同时发生,但修改在副本上执行,修改完成后再与主数据进行同步。

CopyOnWriteArrayList

写入时会创建完整的副本,修改完成后,以原子性操作替换新数组,修改方法均用 synchronized 修饰。
读取时直接读取主数据。

CopyOnWriteArraySet

CopyOnWriteArraySet 底层使用 CopyOnWriteArrayList实现免锁。
添加时直接调用 cowArrayList.addIfAbsent() ,所有方法都没有加 synchronized 修饰,直接使用 CopyOnWriteArrayList 的免锁方法。

ConcurrentHashMap

采用分段锁设计,只有在分段时才会产生竞争。
ConcurrentHashMap总结 - ImportNew

ConcurrentLinkedQueue

http://www.infoq.com/cn/articles/ConcurrentLinkedQueue