集合是一个存储多个数据的容器。大小不固定。

集合的顶级接口。
子接口：List,Set,Queue
Collection：E表示泛型，声明集合的元素类型。由于泛型的限定，集合中只能存储引用类型的数据。
例子：

1.重要方法

add();

添加元素。
已经重写了toString方法，把每个元素用“，”拼接成一个字符串。

remove();

移除元素。如果移除的元素不存在，会直接忽略。

containe();

判断指定的元素是否存在。

clear();

清空集合。

equals(Object o);

比较。

isEmpty();

判断集合是否为空。

iterator();

返回在此 collection 的元素上进行迭代的迭代器。

size();

获取集合中元素个数。

toArray();

将集合转化为数组。数组的类型只能是Object类。

toArray(new String[0]);

参数表示要转化的数组类型。 如果传入的数组长度小于了集合中元素的个数，那么会将底层的数组返回。如果传入的数组的长度大于等于了集合中元素的个数，会将底层数组的元素复制到传入的数组中，返回传入的数组。
当传入的数组容量过大时，你就分不清数组中的null到底是元素还是真的空着，所以最好传入最小的数组大小。

代码示例：

List接口保证元素的存入顺序，元素是有序的，可以存储重复元素，元素有序可重复。
在List中会对元素进行编号，编号从0开始，元素存在下标，所以可以通过下标来获取和操作对应的元素。

1.特点

1.元素是有序的。
2.可以存储重复元素。
3.元素存在下标。所以我们可以通过下标来获取和操作对应的元素。

2.重要方法

get(int index);

获取指定下标对应的元素。

add(int index, E e);

指定的下标处，插入指定的元素。在下标index的位置插入d。index <= size。index > size就会报错。

equals(object o)

依次调用每个位置上的元素的equals方法来比较的。两个集合在进行比较的时候和元素的顺序有关。

底层过程：

1.比较两个列表的元素个数是否一致，如果不一致，返回false。
2.如果元素个数一致，则一次比较对应下标位置上的元素。底层比较元素的时候用的是equals方法。
凡是引用类型的对象，除非确定不存在为null的可能，否则一律先==后equals。

indexOf(object o);

获取指定元素第一次出现的下标。如果元素不存在就返回-1。

lastIndexOf(object o);

最后一次出现的下标。

remove(int index);

移除指定下标的元素。

set(int index,E e);

表示替换指定下标位置上的元素。

size();

获取列表的大小。

subList(int index,int index);

截取列表。包含起始下标，而不包含结束下标。

代码示例：

3.ArrayList< E > class

ArrayList底层是用数组来存储数据的，是基于数组的。内存空间是连续的，默认初始容量是10，每次扩容一半，是一个线程不安全的列表。不便于增删元素，便于查询元素较快。

重要方法

继承List< E >接口。

练习

简易ArrayList
数组来实现一个简易版的ArrayList，元素是String，实现add/remove/set/get/indexOf/contains/isEmpty/size/toString

4.LinkedList< T > class

LinkedList< T > 类基于链表实现的。内存空间是不连续的。不用设置初始容量，便于增删元素，不便于查询元素。是一个线程不安全的列表。

每个元素包含三部分：
第一部分存储上个节点的地址。第一个元素的第一部分为null。
第二部分存储元素在常量池的地址。
第三部分存储下个节点的地址。最后一个元素的第三部分null。

链表对象里有三个属性：
第一个属性：Node< E >fist:null
第二个属性：Node< E >last:null
第三个属性：int size :0
在对查询效果影响不是很大的情况，一般都会选择LinkedList。可以节省内存。

重要方法

继承List。

5.Vector class（向量）

Vector基于数组实现的。默认初始容量是10，每次扩容一倍。是一个线程安全的集合。
Vector是java中最早的集合,在1.1版本中出现，List是在1.2版本出现，由于接口比类出现的晚，Vector中出现来大量重复的方法。

重要方法

capacity();

获取集合的容量。

elements();

返回向量组件的枚举。名义上是枚举，其实返回的是迭代器。

6.Stack class（栈）

定义

栈的原则是先进后出或者后进先出。继承了Vector class。
最先放入的元素叫栈底元素。
最后放入的元素叫栈顶元素。
将元素放入栈中的操作叫入栈（压栈）。
将元素从栈中取出叫出栈（弹栈）。

构造方法：

Stack< E >();

创建一个空堆栈。

重要方法

isEmpty();

判断栈是否为空。

push();

入栈、压栈。

peek();

获取栈顶元素，不删除。
如果栈为空，则抛出EmptyStackException(空栈异常)。

pop();

出栈,获取并移除栈顶元素。
如果栈为空，则抛出EmptyStackException(空栈异常)。

search();

获取指定元素在栈中的位置。获取的时候从栈顶到栈底的顺序查找，以1位基数。如果元素不存在返回-1。

练习

用数组实现Stack。

用节点实现Stack。

7.总结

ArrayList和数组有什么区别？

ArrayList的容量可变，数组的容量是固定的。ArrayList只可以存储引用类型，数组不做限制。
容量：ArrayList可变，数组固定
元素类型：ArrayList可以存储引用类型，数组不限制。

List和数组有什么区别？

List的容量是可变的，数组的容量是固定的，List只能存储引用类型，数组不做限制。数组的内存空间是连续的，List的的内存空间是根据实现类的不同而不同，针对LinkedList而言，内存空间是不连续的，针对ArrayList、Vocter、Stack而言内存空间是连续的。

ArrayList和Vector有什么区别？

ArrayList和Vector都是基于数组实现的，并且其底层的数组的默认初始容量都是10.对于ArrayList而言，其扩容机制是基于右移运算的，每次右移1位，所以扩容完成之后，容量就变为原来的1.5倍。对于Vector而言，其扩容机制是基于三元运算求和的，如果不指定增量的话，扩容完成之后就变为原来的两倍。ArrayList是一个线程不安全的集合，但是可以通过Collections.synchronizedList();方法将其包装成一个线程安全的集合。Vector是一个线程安全的集合。

LinkedList和ArrayList那个增添数据更快？

如果增删的元素的位置相对靠前，此时LinkedList较快；如果增删的元素的位置靠后，此时ArrayList较快。
如果需要扩容，LinkedList偏快；如果不需要扩容，ArrayList偏快。

队列遵循先进先出的原则。先放入的元素叫队头元素，最后放入的叫队尾元素。

重要方法

offer();

插入元素。如果失败返回false。

add();

插入元素。如果失败则抛出异常。

peek();

获取队头元素。如果获取失败，则返回null。

element();

获取队头元素。如果获取失败则抛出一个异常

poll();

移除队头。如果移除失败则返回一个null。

remove();

移除队头。如果失败则返回一个NoElementException。

1.定义：

散列集合，Set中的元素无序不可重复。

2.特点：

1.Set中元素不可重复。
2.Set中元素不保证存入的顺序。
3.基于元素的哈希码进行存储。
4.Set在存储过程中，如果出现了相同元素，则会抛弃后续添加的元素。

重要方法

继承Collection< E >接口的方法。

equals(Set s);

比较。在比较的时候比较的是实际元素是否一致。跟顺序和地址无关。

3.HashSet class

Set实现类之一。不保证Set的迭代顺序，不保证该顺序恒久不变。HashSet的底层是基于HashMap的。是一个线程不安全的集合。
碰撞：当两个对象往同一个位置存储的时候产生的现象。当存储的数据越多的时候，碰撞的次数越多，效率越低。
加载因子：相当于一个警戒线。
rehash：将扩容之后的HashSet的空间打乱，重新分配空间范围。

构造方法

HashSet();

默认初始容量是16，加载因子是0.75f。每次扩容一倍。

HashSet(int initialCapacity, float loadFactor);

指定容量，指定加载因子。

重要方法

继承Set的方法。

iterator();

通过指针的挪动来遍历集合。在遍历过程中不允许集合本身来增删原集合。

1.Iterable< T > interface

如果一个对象允许用增强for循环来遍历，那么这个对象对应的类必须实现Iterable 接口，增强for（foreach）循环本质上就是在进行迭代遍历。增强for循环不允许对原集合进行增删操作。
Iterable< T > interface 是JDK1.5的特性之一。

方法摘要

iterator();

返回一个在一组 T 类型的元素上进行迭代的迭代器。

2.Enumeration< E > interface

不要使用这个类的方法，来删除元素。只删除偶数位，永远删除不完。

重要方法

hasMoreElements();

判断是否还有更多的元素。

nextElement();

表示挪动指针到下一个元素。

3.Itertor< E > interface

推荐使用的迭代器。它在操作集合的时候，将集合进行了复制，操作的是复制之后的集合，在复制后的集合上进行迭代标记操作。在迭代器操作集合的时候，不允许原集合自己进行增删操作。

重要方法

hasNext();

判断是否有可迭代的元素。

next()；

返回迭代的下一个元素。

remove();

表示将当前在迭代的元素进行移除。会改变原集合。

Collections是一个操作集合的工具类。提供来一系列的操作集合的静态方法。

1.构造方法

Collections 的构造方法是私有的。

2.重要方法

replaceAll(List< T > list,T oldt,T newt);

用一个对象替换另一个对象。

reverse(List list);

反转集合。

sort(List< T > list);

将集合从小到大排序。

指定规则进行排序。
示例：

1.Comparable< T > interface

如果没有指定排序规则，这个时候要求集合中的元素对应的类必须实现Comparable接口,比较规则是写在compareTo方法中。

重要方法

compareTo(T o);

比较此对象与指定对象的顺序。

2.Comparator< T > interface

比较器，重写compare方法，将比较规则写到compare方法中，根据返回值的正负来确定大小，如果返回值是正数，表示第一个参数排到第二个参数之后；反之表示第一个参数排到第二个参数之前。

重要方法

compareTo(T o1,T o2);

用来排序两个参数。

equals(object obj);

指示某个其他对象是否等于此Comparator。

ParameterizedType，学名参数化类型。JDK1.5特性之一。

1.泛型发展历史

List list = new ArrayList();：早期没有泛型集合可以存储任意数据，底层以Object类型来存储。
List list = new ArrayList< E>();：仅仅起了一个建议性的作用。
List< E> list = new ArrayList< E>();：强制元素类型必须是指定的类型。
List< E> list = new ArrayList<>();：JDK1.7之后可以省去后面泛型，JVM在编译的时候会做自动类型推导。

2.泛型的擦除

用具体类型来替换泛型的过程叫泛型的擦除。发生在编译期。

3.定义泛型类

泛型命名

泛型的命名只要遵循标识符的命名规则即可。习惯上用一个大写字母来表示。
T – type，类型。
E – element，元素。
K – key，键。
V – value，值。
R – result，结果。
因为泛型不确定具体类型，所以只允许声明，不允许初始化。
泛型可以作为参数来使用，同样也可以作为返回值使用。
泛型在定义的时候不限制个数，只要以逗号隔开就行。

类的泛型：

表示属于当前类的泛型。
class Demo< T,E,R>{}

方法的泛型：

表示只属于当前方法的泛型。
public < V>void m(V v){}

返回值的泛型：

public < R> R m(){}

4.泛型的继承

Arrays.asList();
允许以操作list的方式来操作一个数组。

数组允许存在向下兼容，也就是说数组中的元素类型可以存在继承关系。

在泛型中不存在向下兼容，是指在声明的时候前后必须一致。

通配符

“?”在泛型的继承中是一个通配符。
List< ?> list;：表示这个集合的元素类型暂时不确定，往往作为参数。

泛型的上限

< ? extends 类/接口>
表示传入的是类/接口及其子类/子接口。这就是规定了泛型的上限。在规定上限方法里，为来防止添加的元素与原类型不一致，只能添加null，不能添加其他元素。

泛型的下限

< ? super 类/接口>
表示传入的这个类/接口及其父类/父接口对象。这就是规定了泛型的下限。在规定下限方法里，能添加元素，元素类型必须是最小类型，null也可以添加。
Java中不允许同时规定上限和下限。可以使用两个方法进行这个上限下限规定的操作。

泛型继承嵌套

Java中允许互相嵌套。
代码示例：

练习

疯狂值
先输入一个整数n，然后获取n个整数，求这一组数的疯狂值，（疯狂值：相邻两个数之差的绝对值之和）。获取这一组数的最大疯狂值。——2017年8月网易校招题。
方法一：