JavaSE 集合

第一节 集合框架介绍

集合官方文档

1. 概念

A collection — sometimes called a container — is simply an object that groups multiple elements into a single unit. 
Collections are used to store, retrieve, manipulate, and communicate aggregate data.
集合（有时称为容器）只是一个将多个元素分组为一个单元的对象。集合用于存储，检索，操作和传达聚合数据。

A collections framework is a unified architecture for representing and manipulating collections.
集合框架是用于表示和操作集合的统一体系结构。

2. 适用场景

回想我们的数组也是对元素的增删改查，纳闷数组和集合之间有什么区别？

使用数组对元素进行增删改查时，需要我们自己编码实现。但是集合是Java平台提供的，也能进行增删改查，已经有了具体的实现。我们不需要再去实现，直接利用Java平台提供的集合即可，这无疑减少了编程的工作量。同时Java平台提供的集合无论实在数据结构还是在算法设计上都具有更高的性能。

3. 集合框架接口体系

• 集合接口体系中有两个顶层接口Collection和Map，Collection接口属于单列集合（可以理解为一次存储一个元素），Map接口属于双列集合（可以理解成一次存储一对元素）。

package com.university01.javase03.chapter01.collection;
//Java代码在这个包下，太长了

第二节 Collection接口

1. Collection接口常用方法

  int size();//获取集合大小
  boolean isEmpty();//判断集合是否为空
  boolean contains(Object o);//判断集合是否包含该元素
  Iterator<E> iterator();//获取集合的迭代器
  Object[] toArray(T[] a);//将集合转换为数组
  <T> T[] toArray(T[] a);//将集合转换为指定类型的数组并返回该数组
  boolean add(E e);//添加元素
  boolean remove(Object o);//删除元素
  void clear();//清除集合中所有元素
  boolean containsAll(Collection<?> c);//判断集合是否包含给定集合的所有元素
  boolean addAll(Collection<? extends E> c);//将给定的集合的所有元素添加到集合中

2. AbStractCollection

AbStractCollection实现了Collection接口，属于单列集合的顶层抽象类。
AbStractCollection类并没有定义存储元素的容器，因此，其核心方法都是空方法，这些空实现需要子类重写方法。

第三节 Iterator迭代器

1. 概念

集合是用存储元素的，存储元素的目的是为对元素进行操作，最常用的操作就是检索元素。为了满足这要的需要，JDK提供了一个Iterator接口（表示可迭代的），供所有单列集合来实现。

2. 用法

public interface Collection<E> extends Iterable<E>
//从源码我们可以看出，Collection接口是Iterable接口的子接口，表示单列集合都是可迭代的。

Iterable接口中有一个约定：

Iterator<T> iterator();//获取集合迭代器

因此所有单列集合必需提供一个迭代元素的迭代器。并且迭代器Iterator也是一个接口。其中有如下约定：

boolean hasNext();//判断迭代器中是否有下一个元素
E next();//获取迭代器中的下一个元素
default void remove();//将元素从迭代器中移除，默认是空实现

第四节 泛型

1. 概念

泛型就是在定义类，接口和方法时使用类型（类和接口）成为参数。与方法中声明使用的更熟悉的形式参数非常相似，类型参数为你提供了一种是用不同输入重复使用相同代码的方法。区别在于形式参数的输入是值，而类型参数输入是类型。
泛型就是一个变量，只是该变量只能使用引用数据类型来复制，这样能够使同样的代码被不同数据类型的数据重用。

2. 使用泛型（通常使用泛型变量E T K V)

包含泛型的类定义语法：

访问修饰符 class 类名<泛型变量> {}

包含泛型的接口定义语法：

访问修饰符 interface 接口名<泛型变量> {}

方法中使用新的泛型语法：

访问修饰符 泛型变量 返回值类型 方法名（泛型变量 变量名，数据类型1，变量名1，...，数据类型n，变量名n）{}

3. 泛型通配符

当使用泛型类或接口时，如果泛型类型不能确定，可以通过通配符?表示，例如collection接口中的约定：

boolean containsAll(Collection<?> c);

4. 泛型上限

在使用泛型时，可以设置泛型的上限，表示只能接受该类型或其子类。当集合使用泛型上限时，因为编译器只知道存储类型的上限，但不知道具体存档是什么类型。因此，该集合不能存储元素，只能读取元素。

<? extend 数据类型>

5. 泛型下限

在使用泛型时，可以设置泛型的下线，表示只能接受该类型机器子类或该类型的父类。当集合使用泛型下限时，应为编译器知道存储数据类型的下限，至少可以将该类型对象存入，但不知道有存储的数据又多少个父类，因此，该集合只能存储元素，不能读取元素。

<? super 数据类型>

第五节 List接口

1. 特性

列表是有序的集合（有时称为序列）。列表可能包含重复的元素。
Java平台包含两个常用的List实现。ArrayList通常时性能比较好的实现，而LinkedList在某些情况下可以提供更好的性能

List接口的常用方法

E get(int index);//获取给定位置的元素
E set(int index, E element);//修改给定位置的元素
void add(int index,E element);//在给定位置插入一个元素
E remove(int index);//移除给定位置的元素
int indexOf(Object o);//获取给定元素第一次出现的下标
int lastIndexOf(Object o);//获取给定元素最后一次出现的下标
ListIterator<E> listIterator();//获取List集合专用的迭代器
ListIterator<E> listItrtator(int index);//获取List集合专用的迭代器，从给定的下标位置开始的迭代器
List<E> subList(int formIndex, int toIndex);//获取List集合的一个子集合

2. ArrayList

• ArrayList继承于AbstarctList,AbstractList继承于AbstractCollection
• ensureCapacityInternal(int minCapacity)确保数组有足够的容量来存储新添加的数据
• void grow(int minCapcity)实现数组扩容，扩容至原来的1.5倍数。
• Listltr可以从前到后对集合进行遍历，也可以从后往前对集合进行遍历，还可以向集合中添加修改操作，而ltr只能从前往后对集合进行遍历。

ArrayList底层采用的是数组来存储元素，根据数组的特性，ArrayList在随机访问时效率极高，在增加和删除元素时效率偏低，因为在增加和删除元素时会设计到数组中元素位置的移动。ArrayList在扩容时每次扩容到原来的1.5倍。

3. LinkedList

LinkedList继承于AbstractSequentialList，AbstractSequentialList继承于AbstractList，AbstractList继承于AbstractCollection

void addFirst(E e)；//将数据存储在链表头部

void addLast(E e)；//将数据存储在链表尾部

E removeFirst()；//移除第一个节点，返回该节点的内容

E removeLast()；//移除最后一个节点，返回该节点的内容

总结：
LinkedList底层采用的是双向链表来存储数据，根据链表的特征可行性可知，LinkedList在增加和删除元素时，效率极高，只需要链表间进行链接即可。在随机访问时效率较低，因为需要从头一个个访问

栈（先进后出)

第六节 Queue接口

1.特性描述

队列时用于在处理之前保存元素的集合。除了基本的手机操纵之外，对咧还提供其他插入，移除和检查操作。
队列通常但不是必须以FIFO（先进先出)的方式对元素进行排序。优先队列除外，它们根据元素的值对元素精选排序（有关详细星系，请参见“对象排序”部分）。无论使用哪种排序，，队列的开头都是通过调用remove或poll删除的元素。在FIFO队列中，所有新元素都插入到队列的尾部。其它种类的队列可能使用不同的规则放置，每个Queue实现必须指定其排序属性。
队列实现有可能限制其持有元素数量：这样的队列称之为游街队列。java.util.concurrent中的某些Queue是有界的，但是java，util中的某些实现不受限制。

boolean add(E e);//向队列添加一个元素，如果出现异常，则直接抛出异常
boolean offer(E e);//向队列中添加一个元素，如果出现异常，则返回false
E remove();//移除队列中的第一个元素，如果队列中没有元素，则抛出异常
E poll();//移除队列中的第一个元素，如果队列中没有元素，则返回false
E element();//获取队列中的第一个元素，但不会移除，如果队列为空，则将抛出异常
E peek();//获取队列的第一个元素，但不会移除。如果队列为空，则返回null。

2. LinkedBlockingQueue

LinkedBlockingQueue是一个FIFO队列，队列有重读，超出长度范围的元素将无法存储进队列。

3. PriorityQueue

PriorityQueue是一个有排序规则的队列，存入进去的元素时无序的，队列有长度，超出朝古都范围的元素将无法存储进队列。需要注意的是，如果存储的元素如果不能进行比较排序，也未提供任何对元素精选进行排序的方式，运行实惠抛出一成仓

如果PriorityQueue队列中存储的是对象，会怎么排序

如果对象不能精选比较，则不能排序，运行时报异常。要解决这个问题，需要使用Java平台提供的比较器接口。

第七节 比较器接口

1. 作用

在使用数组或者集合时，我们经常都会遇到排序问题，比如将学生信息按照学生从高到低排序，数字能够直接对比大小，对象不能够直接比较大小，为了解决这个问题，Java平台提供了Comparable和comparator两个接口来解决。

2. Comparable接口

接口对实现该接口的每个类的对象强加了总体排序。此排序称为类的自然排序，而该类的conparaTo方法被称为其自然比较方法。

3. Comparator接口（外排序器）

比较功能，对某些对象集合施加从排序。可以将比较器传递给排序方法（例如collections.sort或Arrays.sort），以实现对排序的精确控制。

Comparable接口是有数组或者集合中的对象的类所示先，实现后对象就拥有了比较的方法，因此称为内排序或者自然排序。
Comparator接口时外部提供的对连个对象的比较方式的实现，对象本身并没有比较的方式，因此被称为外排序器。

第八节 Map接口

1. 特性描述

Map集合是将键影射到值的对象，映射不能包括重复的键：每一个键最多可以映射到一个值。
Java平台包含三个常用Map的实现：HashMap， TreeMap和LinkedHashMap。
Map接口常用方法：

int size();//获取集合大小
boolean isEmpty();//判断集合是否为空
boolean containsKey(Object key);//判断集合中是否包含给定的键
boolean containsValue<Object value);//判断集合中是否包含给定的值
v get(Object key);//获取集合中给定键对应的值
v put(K key, V value);//将一个键值放入集合中
V remove(Object key);//将给定的键从集合中移除
void putAll<Map<？extends K, ? extends V> m);//将给定的集合添加到集合中
void clear();//清除集合中所有元素
set<K> keySet();//获取集合中键的集合
Collection<V> values();//获取集合中值的集合
Set<Map.Entry<K, V>> entrySet();//获取集合中键值对的集合

Entry接口常用方法：

K getKey();//获取键
V getvalue();//获取值
V setvalue(v value);//设置值
boolean equals(Object o);//比较是否是同一个对象
int hashCode();//获取哈希码

2. HashMap

基于哈希表的Map接口的实现。此时先提供所有可选的映射操作，并允许空值和空键。(HashMap类与Hashtable大致等效)，不同之处在于它是不同步的，并且允许为null。）该类不保证映射的顺序。特别是，它不能保证顺序随着时间的推移爆出恒定。
HashMap采用的是数组加单向链表加红黑树的组合来存储数据。

3. TreeMap

基于红河树的NavigableMap实现，根据集合春初的键的自然排序或在映射创建时提供Comparator来对键进行排序，具体确界与所使用的构造方法，

4. LinkedHashMap

Map接口的哈希表和链表实现，具有可预测的迭代顺序。此实现与HashMap的不同之处在于，它维护一个惯出其他所有条目的双向链表，此链表定义迭代顺序，通常时将建插入映射的顺序（插入顺序）。请注意，如果将键重新插入到映射中，则插入顺序不会受到影响。

第九节 Set接口

1. 概念

集合是一个集合，不能包含重复的元素。它为数学集合抽象建模。Set接口仅仅包含从Collection继承的方法。并增加了禁止重复元素限制，Set还为equals和hashCode错做行为增加了更加紧密的约定，即使它们实现类型不同。也可以有意义地比较Set实例。如果两个Set实力包含相同的元素，则它们相等。
Java平台包含三个通用的Set实现：HashSet，TreeSet和LinkedHashSet，HashSet将元素存储到哈希表中，时性能最好的实现，但是它不能保证迭代顺序。

2. HashSet

此类实现Set接口，该接口由哈希表（实际上时HasMap实例）支持。它不保证集合的迭代顺序。特别是，它不能保证舒徐会随着时间的推移爆出恒定。此类允许使用null元素。

3. TreeSet

基于TreeMap的NavigableSet实现。元素使用其自然顺序或在集合创建时提供的Comparator进行排序，具体去接与所使用的构造方法。

4. LinkedHashSet（有插入顺序了）

Set接口的哈希表和链表实现，具有可预测的迭代顺序。此实现与HashSet的不同指出在于，他维护在其所有条目中运行的双向链接列表，此列表定义了迭代顺序，即将元素插入到集合中的顺序（插入顺序）。注意，如果将元素重新插入到集合中，则插入顺序不会受到影响。