第一章 数据结构

数据存储的常用结构：栈、队列、数组、链表、红黑树。

1. 栈：入口和出口在同一侧，先进后出；
2. 队列：入口和出口在集合的两侧，先进先出；
3. 数组：
   查询快：数组地址连续，通过数组首地址找到数组，通过数组索引快速查找元素；
   增删慢：数组的长度是固定的，要增删元素，必须创建一个新数组，把原数组的数据复制过来并销毁原数组(在堆内存中，频繁地创建数组、销毁数组，效率低下)；
4. 链表：每一个元素包含了自己的数据、地址、下一个元素的地址；
   查询慢：链表中地址不是连续的，每次查询元素，都必须从头开始查询；
   增删快：链表结构，增删一个元素对链表整体结构没有影响，所以增删快；
   单向链表：链表中只有一条链，不能保证元素顺序(存储和取出元素顺序有可能不一样);
   双向链表：链表中有两条链，一条专门记录元素的顺序，是一个有序集合；
5. 红黑树：
   二叉树：分支不能超过两个；
   排序树/查找树：二叉树的基础上，左子树小，右子树大；
   平衡树：左右孩子数量相等；
   红黑树：
   趋近于平衡树，查询速度非常快，查询叶子节点的最大次数和最小次数不超过2倍；
   红黑树约束(了解即可)：
   5.1 节点可以是红色或黑色；
   5.2 根节点和叶子节点(空节点)是黑色；
   5.3 红色节点的子节点是黑色；
   5.4 每一个节点到每一个叶子节点的所有路径上黑色节点数量相同；

第二章 List集合

java.util.List接口 extends Collection接口
List接口的特点：

1. 有序的集合，存储和取出元素的顺序是一致的；
2. 有索引，包含了一些带索引的方法；
3. 允许存储重复的元素；

List接口带索引的方法(特有):

1. public void add(int index, E element);
2. public E get(int index);
3. public E remove(int index); 返回值为移除的元素；
4. public E set(int index, E element); 返回值为被替换的元素；
   注意：操作索引时，要防止索引越界异常；
   IndexOutOfBoundsException: 索引越界异常，集合会报；
   ArrayIndexOutOfBoundsException: 数组索引越界异常；
   StringIndexOutOfBoundsException: 字符串索引越界异常；

第三章 List的子类

ArrayList集合

底层其实是一个数组结构，查询快，增删慢；

LinkedList集合

java.util.LinkedList
LinkedList集合的特点：

1. 底层是一个链表结构，查询慢，增删快；
2. 里面包含了大量操作首尾元素的方法；

注意：使用LinkedList特有的方法不能使用多态；

1. public void addFirst(E e); 将指定元素插入此列表的开头
2. public void addLast(E e); 将指定元素插入此列表的结尾，等效于add方法
3. public void push(E e); 将指定元素推入此列表所表示的堆栈
4. public void getFirst(); 返回此列表的第一个元素
5. public void getLast(); 返回此列表的最后一个元素
6. public void removeFirst(); 移除并返回此列表的第一个元素
7. public void removeLast(); 移除并返回此列表的最后一个元素
8. public void pop(); 从此列表所表示的堆栈弹出一个元素
9. public boolean isEmpty(); 如果列表不包含元素，则返回true
10. public void clean(); 清空集合中的元素；

Vector集合

已经被ArrayList代替，了解即可；

第四章 Set接口

java.util.Set接口 extends Collection接口
Set接口的特点：

1. 不允许存储重复的元素
2. 没有索引，没有索引的方法，也不能使用普通的for循环遍历；

HashSet集合

java.util.HashSet特点：

1. 不允许存储重复元素
2. 没有索引，没有索引的方法，也不能使用普通的for循环遍历，可以用迭代器iterator或增强for遍历；
3. 是一个无序集合，存储元素和取出元素的顺序有可能不一致；
4. 底层是一个哈希表结构(查询的速度很快);

哈希值：是一个十进制的整数，由系统随机给出(就是对象的地址值，是一个模拟出的逻辑地址，不是数据实际存储的物理地址);
Object类有一个方法可以获取对象的哈希值：int hashCode();
native: 代表该方法调用的是本地操作系统的方法；

HashSet集合存储数据的结构(哈希表)：
JDK1.8前：哈希表 = 数组 + 链表；
JDK1.8后：哈希表 = 数组 + 链表；哈希表 = 数组 + 红黑树(提高查询速度)；

哈希表的特点：速度快；
哈希冲突：两个元素不同，但哈希值相同；
哈希表的数组结构：相同元素一个分组，链表/红黑结构把相同的哈希值元素连接在一起；
如果链表的结构超过了8位，那么就会把链表转换为红黑树，提高查询速度；
Set集合在调用add方法时，会调用元素的hashCode方法和equals方法判断元素是否重复；

HashSet存储自定义类型元素

HashSet存储自定义类型元素，必须重写该类型的hashCode和equals方法，保证同属性值的元素只存储一次；

LinkedHashSet

java.util.LinkedHashSet集合 extends HashSet集合
LinkedHashSet集合特点：
不允许重复，底层是一个哈希表(数组+链表/红黑树)+链表，多了一条链表记录元素存储顺序，保证元素有序；

可变参数

JDK1.5之后出现的新特性；
使用前提：当方法的参数列表数据类型确定，但参数个数不确定；
使用格式：
定义方法时用：修饰符 返回值类型 方法名(数据类型…变量名){}
原理：可变参数底层就是一个数组，根据传递参数个数的不同创建不同长度的数组，传递的参数可以是0(不传递)、1、2…多个；
注意事项：

1. 一个方法的参数列表，只能有一个可变参数；
2. 如果方法的参数有多个，那么可变参数必须写在参数列表的末尾；
3. 如果有多个可变参数，可以用其终极写法：修饰符 返回值类型 方法名(Object…obj){};

第五章 Collections

java.utils.Collections是集合工具类，用来对集合进行操作；

1. public static boolean addAll(Collections c, T…elements); 往集合c中添加一些元素；
2. public static void shuffle(List<?> list); 打乱集合顺序；
3. public static void sort(List list); 将集合中元素按照默认规则排序；
   注意：
   sort(List list)使用前提：该排序的集合里存储的元素，必须实现Comparable，重写接口中的方法compareTo定义排序的规则；
4. public static void sort(List list, Comparator<? Super T>);

Comparable和Comparator的区别：
Comparable：自己(this)和别人(参数)比较，自己需要实现Comparable接口，重写比较的规则compareTo方法；
Comparable接口的排序规则， (自己)this - 参数：升序；
Comparator：相当于第三方裁判，比较另外两个，重写compare方法；
Comparator比较规则：o1-o2升序；