学习这一节，请先学习：https://www.jianshu.com/p/1dbf1be8006b
将List理解为链条、列表：按顺序
将Set理解为集、容器：没有顺序
1. List派系
List接口派系，继承Collection接口，下面有很多实现类
特点：有序，索引，可重复，取出方式有索引、 Iterator和增强for
常见实现类：ArrayList、LinkedList、Vector
1.1 List的特有抽象方法
一般来讲，在List的api手册中，方法中带有index的方法就是List特有的抽象方法，例如add方法：
1.1.1 void add(int index, E element)
另外，带有索引的操作都要防止越界操作，index的范围是0~集合的size
1.1.2 E remove(int index)
删除集合中位置为index的元素，返回删除的元素值
1.1.3 E set(int index, E element)
修改集合中的元素，返回修改前的元素，要防止越界操作
1.1.4 List的遍历
方式一：使用for循环 带索引的遍历
方式二：增强型for循环，foreach
方式三：集合通用的Iterator
1.2 迭代器的并发修改异常
复习：基本类型的等值比较可以用 ==， 引用类型使用equals()方法
可见，在集合的迭代中，如果向集合添加元素，会报出集合并发的修改异常
因此在迭代集合过程中，不允许修改集合长度
1.3 List集合的存储结构
List接口下有多个集合，他们的存储元素所采用的结构方式是不同的，这样就导致了它们有各自的特点，下面依次介绍：
1.3.1 堆栈stack
特点：
FILO
栈的出入口都是栈的顶端位置
压栈存元素：把元素存到栈的顶端位置，栈中已有元素依次向栈底方向移动一个位置
弹栈取元素：把栈的顶端位置元素取出，栈中已有元素依次向栈顶方向移动一个位置
1.3.2 队列queue
特点：
FIFO
队列的入口、出口各占一侧。
1.3.3 Java的数组array
特点：
查找速度快
增删元素慢（只针对java，因为java的数组是固定长度的）
指定索引位置增加元素：需要创建一个新数组，将指定新元素存储在指定索引位置，再把原数组元素根据索引，复制到新数组对应索引位置
指定索引位置删除元素： 需要创建一个新数组，把原数组元素根据索引，复制到新数组对应位置原数组中指定删除元素不复制到新数组中
1.3.4 链表link list
特点：
多个节点间通过地址进行连接
查找元素慢：查询时，需要通过连接的节点依次向后查找
增删元素快
1.3.5 总结
到底采用哪一种方式要根据实际需求：
查询得多：选择数组
修改的多：选择链表
传输的多：队列
要求效率：选择堆栈
1.4 ArrayList集合的特点
需要频繁查询的操作，用ArrayList
ArrayList看名字就知道数据结构是数组类的
但它数组长度可变，多线程不安全，查询速度快
看源码可见：
可以存储任何Object
定义时可以指定长度也可不指定，一般不指定长度初始容量10
添加元素时，如果超过当前容量（10）就要做扩容：Arrays.copyOf()
1.5 LinkedList
1.5.1 集合的特点
需要频繁增删的操作，用LinkedList
LinkedList看名字就知道数据结构是链表类的
元素长度可变，多线程不安全，查询速度慢，增删快
提供了大量的首尾操作方法
1.5.2 特有方法
1.6 Vector集合（了解一下最早的JDK1.0版集合）
Vector也是List派系的数组结构方式，且是JDK中最早提供的集合，是一个同步的线程安全集合，Vector已经淡出JDK了，但是List由Vector改进而来，ArrayList跟它也相似
ArrayList完全可以替代Vector
2. Set派系
Set接口派系，继承Collection接口，下面有很多实现类
特点：无序，无索引，不可重复，取出方式只有Iterator和增强for
常见实现类：HashSet、LinkedHashSet
Set集合的方法和Collection接口的方法一模一样
由于之前详细介绍了List派系，Set派系很多方法使用上和List派系相似，这里就主要介绍新的概念
2.1 存储和迭代
存储是不重复的，且取出时发现是无序的，没有索引的概念
2.2 底层数据结构 哈希表（hashTable）
特性：
存储、取出速度快
不同步：线程不安全
HashSet在构造器中，默认是长度为16的初始数组（List则为10）
加载因子是0.75：意思是如果数组占用长度达到16*0.75，也就是12的时候，数组就要进行扩容，由16扩容到32（rehash）
2.3 对象的hash值： public int hashCode()
对象的哈希值就是一个普通的十进制整数，源于父类Object
2.3.1 hashSet中没有重写hashCode
Object的hashCode返回一个系统指定的hash值
2.3.2public int hashCode()方法可重写
先看一段String类的hashCode测试代码：
可见String的hashCode被重写过，见源码：
2.3.3 String类的hash存储原理
存储步骤：
1. 调用对象的哈希值 new String("abc").hashCode ----> 96354
2. 集合在容器内找有没有和95354一样的hash值
3. 如果没有相同hash值就往hash容器中存储
4. 如果有相同hash值，集合会让后来的对象new String("abc").equals(已经有的对象)，如果再次相同才判定新来的对象是重复元素（因为又可能hash值相同，存储的内容不同）
结论：
如果是String类，由上面步骤可见，如果hash值不同，则存到hashSet的数组中（数组默认长度16，加载因子0.75）
如果hash值相同，equals不同，则存到拥有相同hashCode的数组中，在最后新增链表
如果hash值和equals都相同，则被判定为相同元素，不存储
2.3.4 自定义类的hash存储（了解原理）
自定义的类，hashCode是不同的
2.3.3 讲了一大堆原理，就是为了在这里重写方法
如果希望姓名年龄相同的对象在add到HashSet是同一个对象的话，需要重写hashCode和equals方法
重写hashCode：
由于String重写hashCode的源码比较麻烦，这里我们简化一下：
public int hashCode() {
return name.hashCode() + age;
}
但是这样会有一个问题，如果不同name和age计算出来的hash值相同就不妥了，所以重写equals方法来双重验证。
重写equals方法：
public boolean equals(Object obj) {
if(this == obj)
return true;
if(obj == null)
return false;
if(obj instanceof Person) {
Person p = (Person)obj;
return name.equals(p.name) && age == p.age;
}
return false;
}
完整代码：
Person类：
package com.gamebear.s24;
public class Person {
private String name;
private int age;
public Person() {}
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public String toString() {
return "Person [name=" + name + ", age=" + age + ", hash=" + this.hashCode() + "]";
}
public int hashCode() {
return name.hashCode() + age;
}
public boolean equals(Object obj) {
if(this == obj)
return true;
if(obj == null)
return false;
if(obj instanceof Person) {
Person p = (Person)obj;
return name.equals(p.name) && age == p.age;
}
return false;
}
}
主程序：
程序可见：
相同的名字和年龄，没有被重复写入
且名字和年龄不同，hash值相同的情况，都被写入了
2.3.5 提高重写hashCode、equals的效率（了解原理）
在2.3.4中，由于hash值相同的概率相对还是比较高，这样equals运算相对比较频繁。
方法：尽量让hash值相同的概率降低，让age乘以一个非0，1的正整数，例：
public int hashCode() {
return name.hashCode() + age*55;
}
2.3.6 推荐使用eclipse的插件重写hashCode和equals方法（编程使用方法）
2.4 LinkedHashSet
LinkedHashSet继承自HashSet，实现Set接口
特性：
具有顺序：存储和取出的顺序是相同的
不同步：线程不安全
2.5 判断集合元素唯一的原理
由于八个基本数据类型都重写了hashCode和equals方法，这样就保证了将数据添加到Set集合中时帮你过滤了重复元素
由于contains源码中，最终是使用equals去判断元素是否重复，
因此，自定义类的情况下，需要注意每次创建类时，使用2.3.6的方式重写hashCode和equals方法
2.5.1 ArrayList的contains方法
boolean contains(Object o)
2.5.2 HashSet的add/contains方法
boolean add(E e)
boolean contains(Object o)
