Java 集合

集合框架图

Java集合框架主要包括两种类型的容器 Collection、Map。

Collection接口又有3种子类型,List、Set 和 Queue,再下面是一些抽象类,最后是具体实现类,常用的有ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap等等。

Collection接口

Collection接口是处理对象集合的根接口,其中定义了很多对元素进行操作的方法,AbstractCollection是提供Collection部分实现的抽象类。

1. Interface List<E>

List接口主要是增加了面向位置的操作,允许在指定位置上操作元素,同时增加了一个能够双向遍历线性表的新列表迭代器ListIterator

1.1 ArrayList

ArrayList是最常用的List实现类,内部是通过数组实现的,它允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔,当数组大小不满足时需要增加存储能力,就要讲已经有数组的数据复制到新的存储空间中。当从ArrayList的中间位置插入或者删除元素时,需要对数组进行复制、移动、代价比较高。因此,它适合随机查找和遍历,不适合插入和删除。

1.2 LinkedList

1.3 Vector

Vector与ArrayList一样,也是通过数组实现的,不同的是它支持线程的同步,Vector与ArrayList基本一致,不同之处在于Vector使用了关键字synchronized将访问和修改向量的方法都变成同步的了,即某一时刻只有一个线程能够写Vector,避免多线程同时写而引起的不一致性,但实现同步需要很高的花费,因此,访问它比访问ArrayList慢。

1.4 Stack

继承自 Vector

1.5 Class CopyOnWriteArrayList<E>

是一个线程安全的List接口的实现,它使用了ReentrantLock锁来保证在并发情况下提供高性能的并发读取。

2. Interface Set<E>

Set接口有三个具体实现类,分别是散列集HashSet、链式散列集LinkedHashSet和树形集TreeSet。

2.1 Class HashSet<E>

2.2 Class LinkedHashSet<E>

LinkedHashSet是用一个链表实现来扩展HashSet类,它支持对规则集内的元素排序。HashSet中的元素是没有被排序的,而LinkedHashSet中的元素可以按照它们插入规则集的顺序提取。

2.3 Class TreeSet<E>

TreeSet扩展自AbstractSet,并实现了NavigableSet,AbstractSet扩展自AbstractCollection,树形集是一个有序的Set,其底层是一颗树,这样就能从Set里面提取一个有序序列了。在实例化TreeSet时,我们可以给TreeSet指定一个比较器Comparator来指定树形集中的元素顺序。树形集中提供了很多便捷的方法。


public class TestSet {



public static void main(String[] args) {



TreeSet<Integer> set = new TreeSet<>();



set.add(1111);

set.add(2222);

set.add(3333);

set.add(4444);

set.add(5555);



System.out.println(set.first()); // 输出第一个元素

System.out.println(set.lower(3333)); //小于3333的最大元素

System.out.println(set.higher(2222)); //大于2222的最大元素

System.out.println(set.floor(3333)); //不大于3333的最大元素

System.out.println(set.ceiling(3333)); //不小于3333的最大元素



System.out.println(set.pollFirst()); //删除第一个元素

System.out.println(set.pollLast()); //删除最后一个元素

System.out.println(set);

}

}

3. Interface Queue<E>

poll()与remove()方法都是移除队列头部的元素,两者的区别在于如果队列为空,那么poll()返回的是null,而remove()会抛出一个异常。方法element()与peek()主要是获取头部元素,不删除。

Summary of Queue methods

Throws exception Returns special value

Insert add(e) offer(e)

Remove remove() poll()

Examine element() peek()

接口Deque,是一个扩展自Queue的双端队列,它支持在两端插入和删除元素,因为LinkedList类实现了Deque接口,所以通常我们可以使用LinkedList来创建一个队列。PriorityQueue类实现了一个优先队列,优先队列中元素被赋予优先级,拥有高优先级的先被删除。


public class TestQueue {



public static void main(String[] args) {



Queue<String> queue = new LinkedList<>();



queue.offer("aaaa");

queue.offer("bbbb");

queue.offer("cccc");

queue.offer("dddd");



while (queue.size() > 0) {

System.out.println(queue.remove() + "");

}

}

}

Map 接口

Map,图,是一种存储键值对映射的容器类,在Map中键可以是任意类型的对象,但不能有重复的键,每个键都对应一个值,真正存储在图中的是键值构成的条目。下面是接口Map的类结构。

从上面这张图中我们可以看到接口Map提供了很多查询、更新和获取存储的键值对的方法,更新包括方法clear()、put()、putAll()、remove()等等,查询方法包括containsKey、containsValue等等。Map接口常用的有三个具体实现类,分别是HashMap、LinkedHashMap、TreeMap。

1.1 Class HashMap<K,V>

HashMap是基于哈希表的Map接口的非同步实现,继承自AbstractMap,AbstractMap是部分实现Map接口的抽象类。在平时的开发中,HashMap的使用还是比较多的。我们知道ArrayList主要是用数组来存储元素的,LinkedList是用链表来存储的,那么HashMap的实现原理是什么呢?先看下面这张图:

HashMap采用数组+链表实现,即使用链表处理冲突,同一hash值的链表都存储在一个链表里。但是当链表中的元素较多,即hash值相等的元素较多时,通过key值依次查找的效率较低。而JDK1.8中,HashMap采用数组+链表+红黑树实现,当链表长度超过阈值(8)时,将链表转换为红黑树,这样大大减少了查找时间。

数组的元素类型是Node,Node继承自Map.Entry,表示键值对映射。

1.2 Class LinkedHashMap<K,V>

LinkedHashMap继承自HashMap,它主要是用链表实现来扩展HashMap类,HashMap中条目是没有顺序的,但是在LinkedHashMap中元素既可以按照它们插入图的顺序排序,也可以按它们最后一次被访问的顺序排序。

1.3 Class TreeMap<K,V>

TreeMap基于红黑树数据结构的实现,键值可以使用Comparable或Comparator接口来排序。TreeMap继承自AbstractMap,同时实现了接口NavigableMap,而接口NavigableMap则继承自SortedMap。SortedMap是Map的子接口,使用它可以确保图中的条目是排好序的。

在实际使用中,如果更新图时不需要保持图中元素的顺序,就使用HashMap,如果需要保持图中元素的插入顺序或者访问顺序,就使用LinkedHashMap,如果需要使图按照键值排序,就使用TreeMap。

2. Class Hashtable<K,V>

HashTable和前面介绍的HashMap很类似,它也是一个散列表,存储的内容是键值对映射,不同之处在于,HashTable是继承自Dictionary的,HashTable中的函数都是同步的,这意味着它也是线程安全的,另外,HashTable中key和value都不可以为null。

上面的三个集合类(Vector Stack HashTable)都是在Java2之前推出的容器类,可以看到,尽管在使用中效率比较低,但是它们都是线程安全的。

3. Class ConcurrentHashMap<K,V>

Concurrent,并发,从名字就可以看出来ConcurrentHashMap是HashMap的线程安全版。同HashMap相比,ConcurrentHashMap不仅保证了访问的线程安全性,而且在效率上与HashTable相比,也有较大的提高。