给岁月以文明,而不是给文明以岁月

文章分类

关于博主

头像不见了

Java中的集合


/ 阅读 107

本文是Java集合的总结,不涉及具体的实现细节。

Java的集合体系结构最主要部分如上图,为了简洁,没有画出虚类及一些辅助类和接口。

最底层两个接口Collection<T>Map<K,V>,实现这两个接口的6个最主要最常用的实现类

Collection<T>

  • ArrayList<T>
  • LinkedList<T>
  • HashSet<T>
  • TreeSet<T>

Map<K,V>

  • HashMap<K,V>
  • TreeMap<K,V>

接口

Collection<T>

一个集合代表一组相同类型元素,Collection<T>接口定义了集合通用方法,主要是获取集合大小、添加元素、删除元素、判断是否包含元素、清空集合、获取集合迭代器和将集合转为数组。

List<T>

List<T>接口继承自Collection<T>接口,添加了排序方法和一些基于下标的操作方法,如获取指定下标元素、在指定下标位置插入元素、移除指定下标元素和获取元素下标等。

Queue<T>

Queue<T>继承自CollectionT>接口添加了作为队列的操作方法。

Deque<T>

Deque<T>继承自Queue<T> ,添加了作为双端队列的操作方法。

Set<T>

继承自Collection<T>代表不包含重复元素的集合,没有添加新的方法。

SortedSet<T>

继承自Set<T>,代表不包含重复元素的有序集合,能够按照元素顺序遍历,添加了一些利用元素的有序性的方法,如subSet(E fromElement, E toElement)获取两个元素之间的元素等。

NavigableSet<T>

继承自SortedSet<T>,添加了更多的利用元素的有序性的方法,如lower(E e)floor(E e)等。

Map<K,V>

map代表了一组键值对的集合,其中键不能重复,这个接口定义了map的通用方法,包括增,删,该,查,获取键集合,获取值集合等。

SortedMap<K,V>

继承自Map<K,V>,不同的键是有序的,能够按照键的顺序遍历,添加了一些利用键的有序性的方法。

NavigableMap<K,V>

继承自SortedMap<K,V>,添加了更多利用键的有序性的方法。

实现

ArrayList<T> 和 LinkedList<T>

都实现了List<T>接口,不同的是内部实现不同,LinkedList<T>同时实现了Deque<T>接口。

List直接实现接口内部实现适合场景其它功能
ArrayListList数组多读少写
LinkedListList,Deque双向链表少读多写作为栈、队列、双端队列

ArraryList<T>LinkedList<T> 都有适合自己的使用场景,差异主要在于它们内部实现的数组和链表在增、删、该、查操作的效率差异,适合数组的地方更适合ArrayList,适合链表的地方更适合LinkedList

LinkedList<T>作为队列,Queue<T> queue = new LinkedList<T>()

作为双端队列,Deque<T> deque = new LinkedList<T>()

作为栈,Deque<T> stack = new LinkedList<T>()

HashSet<T> 和 TreeSet<T>

Set直接实现接口内部实现适合场景
HashSet<T>Set<T>基于HashMap<K,V>元素无序
TreeSet<T>NavigableSet<T>基于TreeMap<K,V>元素有序

HashSet<T>实现基于HashMap<K,V>,内部是一个HashMap<K,V>实例

TreeSet<K,V>实现基于TreeMap<K,V>,内部是一个TreeMap<K,V>实例

HashMap<K,V> 和 TreeMap<K,V>

Map直接实现接口内部实现适合场景
HashMap<K,V>Map<K,V>数组+链表+红黑树键无序
TreeMap<K,V>TreeMap<K,V>红黑树键有序

HashMap<K,V>内部实现基于 数组 + 链表,即拉链法,相同hashcode的元素会组织成一个链表,不过在链表长度大于 8 (TREEIFY_THRESHOLD) 时,会将链表转为红黑树,当链表长度缩小到6时,会从红黑树转为链表。8 这个数字是根据泊松分布得到了,在hashcode()函数设计得足够好的情况下,链表的长度达到8的概率是非常低的。

TreeMap<K,V>内部实现是红黑树。

迭代

Collection<T>继承自Iterable<T>接口,定义了一个方法iterator()获取迭代器,使用迭代器能够方便的遍历集合,并且接口统一,不用关心集合的内部实现机制。实现了Iterable<T>接口能够使用foreach循环。

所有的迭代器都实现了Iterator<T>接口,该接口主要定义了next()、hasNext()、remove()三个方法,使用hasNext()判断是否还有未迭代元素,next()获取下一个元素,remove()移除当前元素。

常用使用方式:

while(iter.hasNext()){
    iter.next();
    // iter.remove();
}

注意:如果在迭代过程中如果使用了非迭代器的修改方法(即iterator.remove()),而是集合本身的修改方法,会触发异常 (fail-safe机制)。

注意事项

一些集合的注意事项:

  • 这6个集合实现都不是线程安全的,要用线程安全的集合,你可以自己实现,或者使用java提供的如ConcurrentHashMap等,或者使用Collections.synchronizedxxx()方法等。一些旧的集合如StackHashMap是线程安全的,但是已经过时,java提供了更好的替代品,如使用ConcurrentHashMap代替HashMap效率更好。
  • 使用HashSet和HashMap注意重写键对象的equals()方法和hashcode()方法的一致性,以及尽量不要使用可变对象作为键。
  • 这些集合都是可变大小的,能够自动扩容,但是如果使用前能够预估数据量,用一个最大容量初始化集合能够减少扩容带来的性能损失。
  • 集合都是泛型的,不支持基本数据类型。

其它集合

  • LinkedHashMap

    相比HashMap内部多维护了一条双向链表,能够按照插入的顺序迭代键值对,或者按照最近最少使用-最近最多使用顺序迭代 (LRU算法)。

  • LinkedHashSet

    基于LinkedHashMap

  • WeakHashMap

    WeakHashMap的键是弱引用(WeakRefenerce),不会阻止键被 gc 回收,在操作时会清理失效的键值对。

  • ArrayDeque

    Deque<T>接口的非链表实现,内部是数组实现的循环队列。仅作为队列或栈使用时效率比LinkedList<T>要好一些。

  • HashTable

    线程安全但效率低,已经过时,不推荐使用

  • Stack

    线程安全但效率低,已经过时,不推荐使用

工具类:

  • Arrays:提供数组相关的工具函数
  • Collections:提供集合相关的工具函数