Java集合体系

Java集合体系

何集合框架都包含三大块内容：对外的接口、接口的实现和对集合运算的算法。

接口：是代表集合的抽象数据类型。例如 Collection、List、Set、Map 等。之所以定义多个接口，是为了以不同的方式 *** 作集合对象

实现（类）：是集合接口的具体实现。从本质上讲，它们是可重复使用的数据结构，例如：ArrayList、linkedList、HashSet、HashMap。

算法：是实现集合接口的对象里的方法执行的一些有用的计算，例如：搜索和排序。这些算法被称为多态，那是因为相同的方法可以在相似的接口上有着不同的实现。

总述

理解Java的集合体系可以从三个层次，分别是最上层的接口、中间的抽象类、最后的实现类。

最上层接口：表示不同的类型集合，Collection、Map、List、Set、Queue、Deque等，以及辅助性质的接口Iterator、linkIterator、Comparator、Comparable这些接口是为迭代和比较元素而准备。

中层抽象类：在这里实现大多数的接口方法，继承类只需要根据自身特性重写部分方法或者实现接口方法即可。

最底层实现类：对接口的具体实现，主要常用的有：ArrayList、linkedList、HashMap、HashSet、TreeMap等等。

除此之外，还有Collections和Arrays类用来提供各种方法，方便开发。

接口和实现类都比较熟悉，在敲代码时经常碰到，但是中间的抽象类一般看不到，但是各种各样的抽象类却有着承上启下的作用。


所有的集合都位于java.util包下，Java集合的基本接口是Collection接口和Map接口，所有的实现类都是这两个接口派生出来的。Collection一次存一个元素，是单列集合，Map一次存一对元素，是双列集合。Map存储的一对元素：键–值，键（key）与值(value)间有对应(映射)关系。

单列集合继承关系图：

双列集合继承图：

为了整体更简洁，更好理解，上面的图没有显示Cloneable和Serializable接口关系。

Collection接口

上面的这些方法在实现类中都必须提供，而每一个类都要提供如此多的例行方法将是一件很烦人的事情，为了能够让实现者更容易地实现这个接口，Java 类库提供了一个类 AbstractCollection，它将基础方法 size 和 iterator 抽象化，但是实现了其他的方法。参照上面单列集合继承关系图，Collection下的所有实现类都是继承自AbstractCollection。AbstractCollection下又派生出AbstractList、AbstractSet、AbstractQueue、ArrayQueue。
List下的全部继承自AbstractList，而Set下的继承自AbstractSet。

List 是一个有序集合，元素会加到容器的特定位置，并且允许重复元素。
而Set是无序集合，并且不允许元素重复。Set要保证没有重复，就需要equals()和hashCode的正确重写。

Java中经常使用的语法糖"for each"循环可以与任何实现了Iterable接口的对象一起工作。Iterable包含了Iterator对象，可以调用iterator()方法，返回一个Iterator对象。这就是常用的迭代器，其中包含hasNext()、next()、remove()、forEachRemaining(Consumer)4个方法。Java中的Iterator接口实现

Iterator()的功能简单，只能单向移动：
1.调用iterator()方法返回一个Iterator对象。
2.第一次调用Iterator的next()方法，返回序列的第一个元素。此后每调用一个next(),会返回序列的下一个元素。调用next()方法前最好先调用hasNext()方法，判断序列后面是否还有元素。
3.remove()删除上次next()返回的对象，remove()只能在next()之后使用，并且一个remove()匹配一个next()，不能重复调用.
4.使用hasNext()判断序列中是否还有元素

List接口

List接口常用的实现类有ArrayList、linkedList

List接口继承自Collection。List中的方法和Collection中的大致相同，多出sort()、get()、listIterator()等方法，listIterator返回一个链表迭代器。

List有着特殊的迭代器接口ListIterator，继承Iterator接口。Iterator是单向的，但是ListIterator是双向的，增加了previous()和hasPreviousO方法用来反向遍历，ListIterator是一个功能更加强大的迭代器。注意只能List使用，其他接口无法使用。

Set接口

Set继承Collection,其方法的行为有更严谨的定义。Set不允许添加重复元素，为了实现这一点就要适当的定义equals方法和hashcode()方法。

Set常用的实现类有：HashSet、TreeSet、linkedHashSet

Queue接口

Queue接口也继承自Collenction。很多实现类既实现类List接口，又实现类Queue接口，如linkedList,也有只实现了一个多，比如ArrayList就没有实现Queue接口，而PriorityQueue也没有实现List接口。这些交叉实现的类最容易混淆。

Deque接口继承自Queue,在Deque的基础上更加细化，可以选择从头部或者尾部 *** 作。另外如果Deque中使用Queue的方法，一定要清楚实现类是从头部还是尾部 *** 作的。

Map接口

Map是一组键值对，它是独立于Collection接口的。常用的实现类有：HashMap、TreeMap、HashTable、linkedHashMap、ConcurrentHashMap等

由双列集合继承关系图可知，Map是顶层接口，sortedMap接口提供排序选项。所有实现类都派生于AbstractMap抽象类。

集合工具类Collections

类中方法都是静态方法，不需要创建对象就可直接使用。

排序
void reverse(List list)：对指定 List 集合元素进行逆向排序。
void shuffle(List list)：对 List 集合元素进行随机排序（shuffle 方法模拟了“洗牌”动作）。
void sort(List list)：根据元素的自然顺序对指定 List 集合的元素按升序进行排序。
void sort(List list, Comparator c)：根据指定 Comparator 产生的顺序对 List 集合元素进行排序。
void swap(List list, int i, int j)：将指定 List 集合中的 i 处元素和 j 处元素进行交换。
void rotate(List list, int distance)：当 distance 为正数时，将 list 集合的后 distance 个元素“整体”移到前面；当 distance 为负数时，将 list 集合的前 distance 个元素“整体”移到后面。该方法不会改变集合的长度。

查找、替换
int binarySearch(List list, Object key)：使用二分搜索法搜索指定的 List 集合，以获得指定对象在 List 集合中的索引。如果要使该方法可以正常工作，则必须保证 List 中的元素已经处于有序状态。
Object max(Collection coll)：根据元素的自然顺序，返回给定集合中的最大元素。
Object max(Collection coll, Comparator comp)：根据 Comparator 指定的顺序，返回给定集合中的最大元素。
Object min(Collection coll)：根据元素的自然顺序，返回给定集合中的最小元素。
Object min(Collection coll, Comparator comp)：根据 Comparator 指定的顺序，返回给定集合中的最小元素。
void fill(List list, Object obj)：使用指定元素 obj 替换指定 List 集合中的所有元素。
int frequency(Collection c, Object o)：返回指定集合中指定元素的出现次数。
int indexOfSubList(List source, List target)：返回子 List 对象在父 List 对象中第一次出现的位置索引；如果父 List 中没有出现这样的子 List，则返回 -1。
int lastIndexOfSubList(List source, List target)：返回子 List 对象在父 List 对象中最后一次出现的位置索引；如果父 List 中没有岀现这样的子 List，则返回 -1。
boolean replaceAll(List list, Object oldVal, Object newVal)：使用一个新值 newVal 替换 List 对象的所有旧值 oldVal。

复制
void copy(List dest,List src)

数组工具类Arrays

类中方法都是静态方法，不需要创建对象就可直接使用。

1.void sort（array）对数组array的元素进行升序排序
2.int binarySearch(array,val):查询元素值val在数组array中的下标
3.String toString(array):该方法将会把一个数组array转换成字符串
4.boolean equals(array1,array2):比较两个数组是否相等
5.void fill(array,val):把数组array所有元素都赋值为val
6.copyof(array,length):把数组array复制成长度为length的新数组
7.Arrays.asList(array).contains(val1):查看数组array中是否有特定的值val1
8.Arrays.hashCode(array)：基于指定数组的内容返回哈希码