Java 集合框架整理
JAVA 集合包括 Collection 和 Map 两大接口,其中Collection 又包含了List、Set、Queue着三种集合接口,他们继承了Collection接口,又分别有自己的实现类。
Collection collection 一般存储单一元素
List List 是线性有序集合,元素可重复,主要有 ArrayList 和 LinkedList 两种实现,前者通过数组实现,支持随机访问,但插入效率较低。后者通过链表实现,插入效率高,但无法做到随机访问,需要从头开始遍历,而且存储指针也带来了额外空间开销。此外还有 Vector 这种实现,但由于较老,性能较差,一般不使用。
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 自旋来保证并发安全。 此外还有一个 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