Collection集合的常用知识点总结02

Collection集合的相关前提知识就介绍完了，接下来说他的两个子接口List和Set
这里就要先说一下基本的数据结构知识
数据结构——栈，队列，数组，链表，红黑树

**栈：**先进后出，入口和出口在同一个侧，入/压栈123，出/弹栈321

**队列：**先进先出，入口和出口在集合的两边，存储123，取出123

**数组：**查询快，增删慢
查询快的原因：数组的地址是连续的，我们通过数组的首地址找到数组，然后通过数组的索引值找到对应的元素
增删慢的原因：由于数组的长度是不变的，我们想要增加或删除元素，就必须创建一个新数组，把根源数组的数据复制过来，然后源数组就会被垃圾回收

**链表：**查询慢，增删快
查询慢的原因：链表地址不是连续的，每次查询元素，都必须从头开始查询
增删快的原因：增删一个元素，只需要把该元素前面和后面元素的地址值进行变更就可以了，对链表的整体结构没有影响
什么叫对其的地址值进行变更？
因为链表中每个元素，也称为一个节点。一个节点包含了一个数据源（存储数组），两个指针（存储地址）

因此改变一个节点，只需要改变其前后的地址值即可

补充：链表中有单向链表和双向链表之分
单向链表：链表中有且只有一条链子，不能保证元素的顺序（存取的元素和取出的元素的顺序可能不一致）
双向链表：链表中有两条链子，有一条链子是专门记录元素的顺序，是一个有序的集合

红黑树由于需要过多的图形，这里就不展开讲了

List接口
java.util.List接口extendsCollection接口
List接口的特点
1.有序的集合，存取元素和取出元素的顺序是一致的
2.有索引，包含了一些带索引的方法
3.允许存储重复的元素

常用的方法
1.public void add(int index,E element)将指定元素添加到该集合中的指定索引位置上面
2.public E remove(index)移除并返回指定索引位置的元素
3.public E set(int index,E element)替换并返回指定索引位置的元素
4.public E get(int index)获取集合中指定位置的元素（可以配合for循环遍历使用）
5.public int size()获取集合的长度

**ArrayList集合：**底层为数组，多线程（不同步）

**LinkedList集合：**底层为链表，多线程（不同步）
因为为链表结构，包含了大量的操作首尾元素的方法
注意操作LinkedList集合时，不能使用多态
1.public void addFirst(E e)将指定元素添加到链表开头
2.public void push(E e)等同于addFirst

3.public void addLast(E e)将指定元素加到末尾。等同于add
4.public E getFirst()获取并返回第一个元素
5.public E getLast()获取并返回最后一个元素
6.public E removeFirst():移除并返回第一个元素
7.public E pop()等同于removeFisrt
8.public E removeLast():移除并返回最后一个元素

Vector集合
1.底层为一个数组
2.同步，单线程

Set接口
1.不允许存储重复的元素
2.没有索引，因此不能使用带索引的方法，也不能使用普通的for循环

HashSet集合
1.底层是一个哈希表结构（查询速度非常的快）
2.是一个无序的集合，存储元素和取出元素的顺序有可能不一样

要说到哈希表，就得先说我们的哈希值
哈希值是一个十进制的整数，由系统随机给出（就是对象的地址值，但是这是一个逻辑地址，是模拟出来的，不是数据实际存储的物理地址）
比如我们通常直接打印一个类对象，出来的就是包名 类名@哈希值（十六进制）
当然我们也可以通过Obeject的hashCode（）方法来获取引用对象的哈希值（十进制）

在1.8之前 哈希表=数组+链表
在1.8之后 哈希表=数组+链表
哈希表=数组+红黑树（提高查询速度）

数组结构（初始容量为16）把元素进行分组（相同哈希值的是一组）。
链表/红黑树把相同哈希值的元素链接到一起。（如果链表长度超过了8位，就会转换为红黑树结构）

而Set集合之所以不能存储相同的元素，就是因为Set集合在调用add方法的时候，add方法会调用元素的hashCode方法和equals方法，先存储元素的hashCode在集合中有没有重复（哈希冲突），如果没有，顺利存储，如果有，则判断两者是否equals，如果不相等，就顺利存储，相等就无法存储。
因此我们的set集合不能存储相同元素的前提是必须重写hashCode和equals方法
比如我们采用HashSet集合存储一个自定义的Person类的时候，就必须在Person类里面吧equals和hashCode方法都给它重写了，这样了在存储元素时，就不能存储重复元素了。

LinkedHashSet
底层是一个哈希表加链表的结构，这里多了个链表用来记录元素存取的顺序，保证元素有序

补充知识
可变参数（1.5之后，三个句号）
使用前提，当方法的参数列表数据类型已经确定的时候，但是参数的个数不确定，就可以使用可变参数
格式：定义方法的时候使用
修饰符 返回值类型 方法名（数据类型…变量名）{方法体}

public class Demo01 {
	public static void main(String[] args) {
		add(1,2,3,4,5,6);
	}
	public static int add(int...arr){
		System.out.println(arr.length);//6
		return 0;
	}
}

可变参数的原理：
底层是一个数组，根据传递参数个数不同会创建不同长度的数组，来存取这些元素
传递的参数个数可以是0到多个

注意：
1.一个方法的参数列表只能有一个可变参数
2.如果方法的参数有多个，那么可变参数要写到参数列表的末尾

操作集合的工具类Collections
常用方法（静态）
1.public static boolean addAll(Collection c,T…elements)往集合中添加一系列元素
2.public static void shuffle(List<?> list)随机打乱集合元素顺序
3.public static void sort(List list)将集合中元素按照默认规则（一般是升序）来排序，不能用于Set集合，用于List集合
注意：排序的使用前提是被排序集中里边存储的元素必须实现Comparable接口中的compareTo方法——定义排序的规则

比如存储一个Person类的元素到集合当中，那么Person就必须去implements Comparable接口，然后重写compareTo的方法。当然了，还有toString方法，不然就都是地址值输出出来了。