JAVA 集合

Java 集合框架整理

JAVA 集合包括 Collection 和 Map 两大接口，其中Collection 又包含了List、Set、Queue着三种集合接口，他们继承了Collection接口，又分别有自己的实现类。

Collection

collection 一般存储单一元素

List

List 是线性有序集合，元素可重复，主要有 ArrayList 和 LinkedList 两种实现，前者通过数组实现，支持随机访问，但插入效率较低。后者通过链表实现，插入效率高，但无法做到随机访问，需要从头开始遍历，而且存储指针也带来了额外空间开销。此外还有 Vector 这种实现，但由于较老，性能较差，一般不使用。

线程安全的 list 可以使用 CopyOnWriteArrayList，遵循写时复制的原则，每当对列表进行修改（例如添加、删除或更改元素）时，都会创建列表的一个新副本，这个新副本会替换旧的列表，而对旧列表的所有读取操作仍然可以继续。

Queue

Queue 即队列，遵从先进先出的关系，其有一个子接口叫 Deque 双端队列，两端都可以出队和入队，更加灵活不仅可以作为队列使用还可以作为栈使用，而且也更推荐用 deque 作为栈，而不是 stack 这个类，因为这个类是 vector 的子类性能比较低。LinkedList 不仅实现了 List 接口也实现了 Deque 接口，此外也有用数组实现的 Deque，叫做 ArrayDeque，除此之外还有一类 priorityqueue 实现了有序队列，可以按照元素的大小关系出队，这个类是通过堆来实现的。

Set

Set 类一般是无序无重复的，最常用的是 HashSet，其是依靠 HashMap 实现的，所以这个类的代码量很少，相当于在把 HashMap 的 value 填充为一个无用的值，只需要使用他的 key 就可以了。
然后有一个 LinkedHashSet 继承了 HashSet，其通过链表把节点串了起来，可以实现按照插入顺序进行访问的效果。
西外还有一类特殊的 set 是 TreeSet，底层依靠红黑树实现，可以按照大小关系查找。

Map

Map 接口主要有两个实现一个是 HashMap，其通过哈希表来实现，采用链表和红黑树来解决 hash 冲突，为了提高查找效率，提供扩容机制，当容量达到一定阈值时触发扩容，通过保证哈希表大小永远是 2 的幂次来提高效率。在 jdk 1.7 前使用头插法进行 rehash 操作，这可能导致并发环境下出现环，因此 jdk 1.8 将其改为了尾插法，解决了这个问题，但是 HashMap 并不是为并发环境设计的，并发情况下存在覆盖丢失等一系列问题，因此在并发环境下应该是用线程安全的 concurrentHashMap，这个类最开始通过分段锁来保证线程安全，后来锁的粒度进一步降低，在每个 hash 节点通过 CAS 和 synchronized 来保证并发安全。
此外还有一个 TreeMap，通过红黑树来提供了按照顺序查找的功能，比如说可以查找大于某个 key 的节点等。

UML 类图由 PlantUML 绘制，代码如下：

@startuml
!theme vibrant
interface Iterable
interface Collection
interface List
interface Queue
interface Set
interface Map
interface Deque
interface SortedSet
interface NavigableSet
interface NavigableMap
interface SortedMap

abstract  AbstractList
abstract  AbstractCollection
abstract AbstractSequentialList
abstract AbstractQueue
abstract AbstractSet
abstract AbstractMap
abstract Dictionary

class ArrayList
class LinkedList
class ArrayDeque
class Vector
class Stack
class HashSet
class LinkedHashSet
class HashMap
class Hashtable
class TreeMap


Iterable <|-- Collection

Collection  <|-- List
Collection  <|-- Queue
Collection  <|-- Set
Collection <|.. AbstractCollection

AbstractCollection <|--  AbstractList
AbstractCollection <|-- AbstractQueue
AbstractCollection <|-- AbstractSet
AbstractCollection <|-- ArrayDeque

List  <|.. AbstractList
List <|.. ArrayList
List <|.. LinkedList
List <|.. Vector

Vector <|-- Stack

AbstractList <|-- ArrayList
AbstractList <|-- AbstractSequentialList
AbstractList <|-- Vector

AbstractSequentialList <|-- LinkedList


AbstractQueue <|-- PriorityQueue


Queue <|-- Deque
Queue <|.. AbstractQueue

Deque <|.. LinkedList
Deque <|.. ArrayDeque


Set <|.. AbstractSet
Set <|.. HashSet
Set <|.. LinkedHashSet
Set <|-- SortedSet

AbstractSet <|-- HashSet
AbstractSet <|-- TreeSet

SortedSet <|-- NavigableSet

HashSet <|-- LinkedHashSet

NavigableSet <|.. TreeSet

Map <|.. AbstractMap
Map <|.. HashMap
Map <|.. Hashtable
Map <|-- SortedMap

AbstractMap <|-- HashMap
AbstractMap <|-- TreeMap
Dictionary  <|-- Hashtable
SortedMap <|-- NavigableMap

AbstractMap <|-- TreeMap

NavigableMap <|.. TreeMap

@enduml