集合进阶（一）
集合体系结构
单列集合（Collection）
Collection代表单列集合，每个元素（数据）只包含一个值。
双列集合（Map）
Map代表双列集合，每个元素包含两个值（键值对）。
Collection集合体系
Collection集合体系的特点
- List系列集合：添加的元素有序、可重复、有索引。
- ArrayList、LinkedList ：有序、可重复、有索引。
- Set系列集合：添加的元素无序、不重复、无索引。
- HashSet: 无序、不重复、无索引；
- LinkedHashSet: 有序、不重复、无索引。
- TreeSet：按照大小默认升序排序、不重复、无索引。
有序：取出的数据的顺序与放入数据的顺序相同即为有序。
可重复：可以放入多个相同元素。
有索引：可以通过索引操作存储的数据。
Collection的常用方法
Collection是单列集合的祖宗，它规定的方法（功能）是全部单列集合都会继承的。
| 方法名 | 说明 |
|---|---|
| public boolean add(E e) | 把给定的对象添加到当前集合中 |
| public void clear() | 清空集合中所有的元素 |
| public boolean remove(E e) | 把给定的对象在当前集合中删除，只删除匹配到的第一个对象 |
| public boolean contains(Object obj) | 判断当前集合中是否包含给定的对象 |
| public boolean isEmpty() | 判断当前集合是否为空 |
| public int size() | 返回集合中元素的个数。 |
| public Object[] toArray() | 把集合中的元素，存储到数组中 |
| public boolean addAll(Collection<? extends E> c) | 将指定集合中的所有元素添加到此集合中(把c中的全部数据倒入主调集合中) |
| public <T> T[] toArray(T[] a) | 返回一个包含此collection中所有元素的数组， 返回数组的运行时类型是指定数组的运行时类型 |
可以使用以下方式将toArray()的返回值存入到String类型的数组中（即上表最后一个方法）：
String[] arr = collection.toArray(new String[collection.size()]);
Collection的遍历方式
迭代器
迭代器是用来遍历集合的专用方式（数组没有迭代器），在java中迭代器的代表是Iterator。
Collection集合获取迭代器的方法
| 方法名称 | 说明 |
|---|---|
| Iterator<E> iterator() | 返回集合中的迭代器对象，该迭代器对象默认指向当前集合的第一个元素 |
Iterator迭代器中的常用方法
| 方法名称 | 说明 |
|---|---|
| boolean hasNext() | 询问当前位置是否有元素存在，存在返回true ,不存在返回false |
| E next() | 获取当前位置的元素，并同时将迭代器对象指向下一个元素处。 |
注意：要问一次取一次。
增强for循环
for (元素的数据类型 变量名 : 数组或者集合) {
...
}
-
增强for可以用来遍历集合或者数组。
-
增强for遍历集合，本质就是迭代器遍历集合的简化写法。
Lambda表达式
JDK 8开始的新技术Lambda表达式提供了一种更简单、更直接的方式来遍历集合。
需要使用Collection的如下方法来完成
| 方法名称 | 说明 |
|---|---|
| default void forEach(Consumer<? super T> action) | 结合lambda遍历集合 |
List集合
List系列集合的特点
有序，可重复，有索引。
经典代码：
List<String> list = new ArrayList<>();
List集合的特有方法
List集合因为支持索引，所以多了很多与索引相关的方法。当然，Collection的功能List也都继承了。
| 方法名称 | 说明 |
|---|---|
| void add(int index,E element) | 在此集合中的指定位置插入指定的元素 |
| E remove(int index) | 删除指定索引处的元素，返回被删除的元素 |
| E set(int index,E element) | 修改指定索引处的元素，返回被修改的元素 |
| E get(int index) | 返回指定索引处的元素 |
遍历方式
-
for循环（因为List集合有索引）
-
迭代器
-
增强for循环
-
Lambda表达式
ArrayList集合的底层原理
ArrayList是基于数组实现的。
ArrayList集合的特点
查询快，增删慢。
-
查询速度快（注意：是根据索引查询数据快）：查询数据通过地址值和索引定位，查询任意数据耗时相同。
-
删除效率低：可能需要把后面很多的数据进行前移。
-
添加效率极低：可能需要把后面很多的数据后移，再添加元素；或者也可能需要进行数组的扩容。
ArrayList集合的底层原理
- 利用无参构造器创建的集合，会在底层创建一个默认长度为0的数组。
- 添加第一个元素时，底层会创建一个新的长度为10的数组。
- 存满时，会新创建一个1.5倍容量的新数组，并调用Arrays.copyOf方法将原数组复制到新的数组中去。
- 如果一次添加多个元素，1.5倍还放不下，则新创建数组的长度以实际为准。
ArrayList适合的应用场景
ArrayList适合：根据索引查询数据，比如根据随机索引取数据（非常高效），或者数据量不是很大时。
ArrayList不适合：数据量大的同时，又要频繁地进行增删操作。
链表
链表中的结点是独立的对象，在内存中是不连续的，每个结点包含数据值和下一个结点的地址。链表中的第一个结点叫头结点，它的地址是会被记住的，最后一个结点叫尾结点。
链表的特点
-
查询慢（根据索引查询数据也很慢），无论查询哪个数据都要从头开始找。
-
链表增删相对快。
-
不存在扩容的问题。
单向链表
每个结点中只保存了下一个结点的地址，只能从头往后查。
双向链表（双链表）
每个结点中不仅保存了下一个结点的地址，还保存了上一个结点的地址，可以从头往后查，也可以从尾往前查。同时，尾结点的地址也会被记住。
特点：查询慢（相对单向链表快一点），增删相对较快，但对首尾元素进行增删改查的速度是极快的。
LinkedList集合的底层原理
-
LinkedList是基于双链表实现的。
-
特点：查询慢，增删相对较快，但对首尾元素进行增删改查的速度是极快的。
LinkedList的新增方法
LinkedList新增了很多首尾操作的特有方法。
| 方法名称 | 说明 |
|---|---|
| public void addFirst(E e) | 在该列表开头插入指定的元素 |
| public void addLast(E e) | 将指定的元素追加到此列表的末尾 |
| public E getFirst() | 返回此列表中的第一个元素 |
| public E getLast() | 返回此列表中的最后一个元素 |
| public E removeFirst() | 从此列表中删除并返回第一个元素 |
| public E removeLast() | 从此列表中删除并返回最后一个元素 |
LinkedList适合的应用场景
- 可以用来设计队列，队列的特点：先进先出，后进后出。
- 可以用来设计栈，栈的特点：先进后出，后进先出。
Set集合
Set系列集合的特点
无序：添加数据的顺序和获取出的数据顺序不一致；不重复；无索引。
经典代码：
Set<Integer> set = new HashSet<>();
注意：Set要用到的常用方法，基本上就是Collection提供的，自己几乎没有额外新增一些常用功能。
哈希值
-
就是一个int类型的数值，Java中每个对象都有一个哈希值。
-
Java中的所有对象，都可以调用Obejct类提供的hashCode方法，返回该对象自己的哈希值。
public int hashCode(); //返回对象的哈希码值
对象哈希值的特点
- 同一个对象多次调用hashCode()方法返回的哈希值是相同的。
- 不同的对象，它们的哈希值一般不相同，但也有可能会相同(哈希碰撞)。
HashSet集合的底层原理
- 基于哈希表实现。
- 哈希表是一种增删改查数据性能都较好的数据结构。
哈希表
- JDK8之前，哈希表 = 数组+链表
- JDK8开始，哈希表 = 数组+链表+红黑树
JDK8之前HashSet集合的底层原理
-
创建一个默认长度16的数组，默认加载因子为0.75，数组名为table。
-
使用元素的哈希值对数组的长度求余（特殊的求余算法）计算出应存入的位置。
-
判断当前位置是否为null，如果是null直接存入。
-
如果不为null，表示有元素，则调用equals方法比较，若相等，则不存；若不相等，则存入数组：
- JDK 8之前，新元素存入数组，占老元素位置，老元素挂下面。
- JDK 8开始之后，新元素直接挂在老元素下面。
-
当数组中已经被占的位置数量达到
数组长度×加载因子时，数组会进行扩容，扩容到原来的两倍，再把原数组中的元素全部转入到新数组中。
JDK8开始HashSet集合的底层原理
JDK8开始，当链表长度超过8，且数组长度>=64时，自动将链表转成红黑树。
二叉树
每个节点都会保存四个数据：本节点的值、父节点地址、左子节点地址和右子节点地址。
二叉树的常见概念：
- 度：每一个节点的子节点数量，二叉树中，任意节点的度<=2。
- 树高：树的总层数。
- 根节点：最顶层的节点。
- 左子节点：左边的子节点。
- 右子节点：右边的子节点。
- 左子树：左边的子树。
- 右子树：右边的子树。
二叉查找树（二叉排序树）
规则：小的存左边，大的存右边，一样的不存。
二叉查找树存在的问题：当数据已经是排好序的时，会导致查询的性能与单链表一样，查询速度变慢。
平衡二叉树
在满足查找二叉树的大小规则下，让树尽可能矮小，以此提高查数据的性能。
红黑树
-
红黑树，就是可以自平衡的二叉树。
-
红黑树是一种增删改查数据性能相对都较好的结构。
深入理解HashSet集合去重复的机制
-
HashSet集合默认不能对内容一样的两个不同对象去重复。
-
如果希望Set集合认为2个内容一样的对象是重复的，必须重写对象的hashCode()和equals()方法。
LinkedHashSet集合的底层原理
- LinkedHashSet依然是基于哈希表（数组、链表、红黑树）实现的。
- 但是，它的每个元素都额外地多了一个双链表的机制记录它前后元素的位置。
TreeSet
- 特点：不重复、无索引、可排序（默认升序排序 ，按照元素的大小，由小到大排序）。
- 底层是基于红黑树实现的排序。
注意：
- 对于数值类型：Integer , Double，默认按照数值本身的大小进行升序排序。
- 对于字符串类型：默认按照首字符的编号升序排序。
- 对于自定义类型如Student对象，TreeSet默认是无法直接排序的。
自定义排序规则
TreeSet集合存储自定义类型的对象时，必须指定排序规则，支持如下两种方式来指定比较规则。
-
方式一：让自定义的类（如学生类）实现Comparable接口，重写里面的compareTo方法来指定比较规则。
-
方式二：通过调用TreeSet集合有参数构造器，可以设置Comparator对象（比较器对象，用于指定比较规则）。
public TreeSet(Comparator<? super E> comparator)
两种方式中，关于返回值的规则：
- 如果认为第一个元素 > 第二个元素 返回正整数即可。
- 如果认为第一个元素 < 第二个元素返回负整数即可。
- 如果认为第一个元素 = 第二个元素返回0即可，此时Treeset集合只会保留一个元素，认为两者重复。
注意
- 如果类本身有实现Comparable接口，TreeSet集合同时也自带比较器，默认使用集合自带的比较器排序。
- 比较值为double类型时，可以直接调用Double.compare()方法。
Collection各种集合的选择
-
如果希望记住元素的添加顺序，需要存储重复的元素，又要频繁的根据索引查询数据？
- 用ArrayList集合（有序、可重复、有索引），底层基于数组的。（常用）
-
如果希望记住元素的添加顺序，且增删首尾数据的情况较多？
- 用LinkedList集合（有序、可重复、有索引），底层基于双链表实现的。
-
如果不在意元素顺序，也没有重复元素需要存储，只希望增删改查都快？
- 用HashSet集合（无序，不重复，无索引），底层基于哈希表实现的。 （常用）
-
如果希望记住元素的添加顺序，也没有重复元素需要存储，且希望增删改查都快？
- 用LinkedHashSet集合（有序，不重复，无索引）， 底层基于哈希表和双链表。
-
如果要对元素进行排序，也没有重复元素需要存储？且希望增删改查都快？
- 用TreeSet集合，基于红黑树实现。
注意事项：集合的并发修改异常问题
集合的并发修改异常
- 使用迭代器遍历集合时，又同时在删除（或添加）集合中的数据，程序就会出现并发修改异常的错误。
- 由于增强for循环就是迭代器遍历集合的简化写法，因此，使用增强for循环遍历集合，又在同时删除集合中的数据时，程序也会出现并发修改异常的错误，且此时异常问题无法解决。
- 由于lambda表达式内部也是调用增强for循环，因此，使用lambda表达式遍历集合，又在同时删除集合中的数据时，程序也会出现并发修改异常的错误，且此时异常问题无法解决。
解决方案
- 使用迭代器遍历集合，但用迭代器自己的删除方法删除数据即可（内部也做了i--的操作）。
- 如果能用for循环遍历：可以倒着遍历并删除；或者从前往后遍历，但删除元素后做i--操作。