目录

一、List 接口
1. 概述
2. List 接口中的抽象方法（特有）
3. List 遍历
二、ListIterator 接口
1.概述
2. ListIterator 接口的抽象方法
3. List 逆向遍历：
三、迭代器的并发修改异常
1. 迭代器的并发修改异常
2. 出现场景：
3. 原因：
四、ArrayList 、LinkedList 集合
1. ArrayList 集合
2. LinkedList 集合
3. Vector 集合（基本不用）
五、Set 接口
六、 HashSet (哈希表)
1. 特点
2. 哈希表的数据结构
3. 字符串对象的哈希值
4. 哈希表的存储过程
5. 哈希表的存储自定义对象
6. LinkedHashSet 集合
7. ArrayList，HashSet 判断对象是否重复的原因
七、TreeSet
1.概述
2. TreeSet如何实现，不能存储重复元素
3. 向TreeSet中放入，自定义的类的对象
4. 注意事项

---

一、List 接口

1. 概述

• 继承 Collection 接口，它是一个元素存取 有序 的集合

例如，存元素的顺序是11、22、33。那么集合中，元素的存储就是按照11、22、33的顺序完成的）

• 它是一个 带有索引 的集合，通过索引就可以精确的操作集合中的元素（与数组的索引是一个道理）

• 与 set 不同，List 中 可以有重复的元素，通过元素的 equals 方法，来比较是否为重复的元素

• List 接口的常用实现类有：

• ArrayList 集合

• LinkedList 集合

2. List 接口中的抽象方法（特有）

• add(int index, Object e) ： 向集合指定索引处，添加指定的元素，原元素依次 后移
• remove(int index)：将指定索引处的元素，从集合中删除，返回值为被删除的元素
• set(int index,E element)：将指定索引处的元素，替换成指定的元素，返回值为替换前的元素
• get(int index)：获取指定索引处的元素，并返回该元素

3. List 遍历

List<Person> a = new LinkedList<>();
a.add(new Person("zs",10));
a.add(new Person("lisi",20));
a.add(new Person("wangwu",30));

//利用Iterator来遍历List
Iterator<Person> iterator = a.iterator();

//利用迭代器对象遍历
while(listItr.hasNext()) {
    System.out.println(listItr.next());
}

//List独有的遍历方式
for (int i = 0; i < a.size(); i++) {
    System.out.println(a.get(i));
}

---

二、ListIterator 接口

1.概述

• List 不仅有自己独有的迭代方式，还有自己独有的迭代器: ListIterator

2. ListIterator 接口的抽象方法

• add(E, e)：将指定元素插入列表
• boolean hasPrevious()：逆向遍历列表，若列表迭代器有多个元素，则返回 true，也就是判断是否有前一个元素
• previous() ：返回列表的前一个元素

3. List 逆向遍历：

Iterator<Person> iterator = a.iterator();
ListIterator<Person> listItr = a.listIterator(a.size());
//先顺序遍历，让 cursor 到最后
while(listItr.hasNext()) {
    System.out.println(listItr.next());
}
//逆向遍历
//先previous向前移动一个位置，再访问cursor指向的元素
while(listItr.hasPrevious()) {
    System.out.println(listItr.previous());
}

---

三、迭代器的并发修改异常

1. 迭代器的并发修改异常

java.util.ConcurrentModificationException

• 就是在遍历的过程中，使用了集合方法 修改了 集合的长度

2. 出现场景：

首先，在遍历集合的过程中修改集合；其次，修改集合行为，不是迭代器对象来完成的，而是直接修改 Collection 对象

//场景实现
List<String> list = new ArrayList<String>();
list.add("abc1");
list.add("abc2");
list.add("abc3");
list.add("abc4");

//对集合使用迭代器进行获取,获取时候判断集合中是否存在 "abc3"对象
//如果有,添加一个元素 "ABC3"
Iterator<String> it = list.iterator();
while(it.hasNext()){
    String s = it.next();
    //对获取出的元素s,进行判断,是不是有"abc3"
    if(s.equals("abc3")){
        list.add("ABC3");
    }
    System.out.println(s);
}

3. 原因：

在迭代过程中，使用了集合的方法对元素进行操作。导致迭代器并不知道集合中的变化，容易引发数据的不确定性。迭代器对象，是依赖与当前的数据集合产生的（换言之，迭代器依赖于数据集，它们必须对应）

public class ListDemo{
    public static void main(String[] args) {
       List<Person> a = new LinkedList<>();
       //迭代器
       ListIterator<Person> listItr = a.listIterator();

        a.add(new Person("zs",10));
        a.add(new Person("lisi",20));
        a.add(new Person("wangwu",30));

        while(listItr.hasNext()){
            Person p = listItr.next();
            //这种添加元素的方式，会产生异常
            //a.add(new Person("zhaoliu", 40));

            //解决： 利用ListIterator对象添加元素
            listItr.add(new Person("zhaoliu", 40));
        }
    }
    System.out.println(s);

    //针对List还有另外一种，在遍历集合同时修改集合的解决方案
    for (int i = 0; i < a.size(); i++){
        if("lisi".equals(a.get(i).name)){
            a.add(new Person("zhaoliu", 40));
        }
    }
    System.out.println(a);
    //如果使用 ListIterator 的add方法向集合中添加元素,这个元素的位置处在当前遍历到的元素之后的位置
    //如果使用 集合对象的 add(e) 方法添加元素，插入的元素处在表尾位置
}

---

四、ArrayList 、LinkedList 集合

1. ArrayList 集合

• 底层采用的是 数组 结构，线程不安全，查询快，增删慢

//创建了一个长度为0的Object类型数组
ArrayList al=new ArrayList();
al.add("abc");
//本质：
//底层会创建一个长度为10的Object数组 Object[] obj=new Object[10]
//obj[0]="abc"
//如果添加的元素的超过10个,底层会开辟一个1.5*10的长度的新数组
//把原数组中的元素拷贝到新数组,再把最后一个元素添加到新数组中

2. LinkedList 集合

• 底层采用 链表 结构，线程不安全，查询慢，增删快
• 每次查询都要从链头或链尾找起，查询相对数组较慢，但是删除直接修改元素记录的地址值即可,不要大量移动元素
• LinkedList 的索引决定是从链头开始找还是从链尾开始找，如果该元素小于元素长度一半,从链头开始找起,如果大于元素长度的一半,则从链尾找起
• LinkedList 提供了大量的操作开始和结尾的方法
• 子类的特有功能：不能多态调用：

addFirst(E) 添加到链表的开头
addLast(E) 添加到链表的结尾
E getFirst() 获取链表的开头
E getLast() 获取链表的结尾
E removeFirst() 移除并返回链表的开头
E removeLast() 移除并返回链表的结尾

3. Vector 集合（基本不用）

• Vector 集合数据存储的结构是 数组 结构，为JDK中最早提供的集合，它是线程同步的，线程安全的
• Vector 集合已被 ArrayList 替代

---

五、Set 接口

1. 特点

• 它是个 不包含重复元素 的集合，没索引

• 是一个不包含重复元素的 collection

• 无序集合，没有索引，不存储重复元素

• Set无序：存储和取出的顺序不同，

• Set集合取出元素的方式可以采用：迭代器、增强for

• 代码的编写上，和 ArrayList 完全一致

• Set集合常用实现类：

• HashSet 集合

• LinkedHashSet 集合

---

六、 HashSet (哈希表)

1. 特点：

• 底层数据结构为 哈希表
• 存储、取出都比较快
• 线程不安全，运行速度快
• 不保证 set 的迭代顺序
• 不保证该顺序的恒久不变

2. 哈希表的数据结构：

• 加载因子：表中填入的记录数/哈希表的长度
  例如：加载因子是 0.75 代表：数组中的16个位置, 其中存入 16 * 0.75 = 12个元素。
• 如果在存入第十三个( > 12 )元素，导致存储链子过长，会降低哈希表的性能，那么此时会扩充哈希表(再哈希)，底层会开辟一个长度为原长度2倍的数组，把老元素拷贝到新数组中，再把新元素添加数组中。
  当 存入元素数量 > 哈希表长度 * 加载因子，就要扩容，因此加载因子决定扩容时机

3. 字符串对象的哈希值：

• 对象的哈希值，是普通的十进制整数，Object 类的方法 public int hashCode() 来计算，计算结果 int 整数
• String 类重写了hashCode() 方法，见源码

4. 哈希表的存储过程

存取原理:
每存入一个新的元素都要走以下三步:
1. 首先调用本类的 hashCode() 方法算出哈希值
2. 在容器中找是否与新元素哈希值相同的老元素，如果没有直接存入，如果有转到第三步
3. 新元素会与该索引位置下的老元素利用 equals 方法一一对比，一旦 新元素.equals(老元素)，返回 true，停止对比，说明重复，不再存入，如果与该索引位置下的老元素都通过 equals 方法对比返回 false，说明没有重复，存入

哈希表

哈希表的存储过程

5. 哈希表的存储自定义对象

• 自定义对象需要重写 hashCode() 和 equals()，来保证存入对象的不重复

//重写hachCode() 方法
public int hashCode(){
    return name.hashCode() +age +id; //算法为name的hashCode值+age+id
}
//重写equals
public boolean equals(Object obj){
    if(this == obj)
        return true;
    if(obj == null)
        return false;
    if(obj instanceof Student){
        Student s = (Student)obj;
        return name.equals(s.name) && age == s.age && id == s.id;
    }
    return false;
}

6. LinkedHashSet 集合

• LinkedHashSet 基于链表的哈希表实现，继承自 HashSet

• LinkedHashSet 自身特性：

• 具有顺序，存储和取出的顺序相同的，线程不安全，运行速度块

public class LinkedHashSetDemo {
    public static void main(String[] args) {
        LinkedHashSet<Integer> link = new LinkedHashSet<Integer>();
        link.add(123);
        link.add(44);
        link.add(33);
        link.add(33);
        System.out.println(link);
    }
}

7. ArrayList，HashSet 判断对象是否重复的原因

• ArrayList 的 contains()原理：底层依赖于equals()

ArrayList的 contains方法 调用时，传入的元素的调用 equals方法 依次与集合中的旧元素所比较，从而根据返回的布尔值判断是否有重复元素。
此时，当ArrayList存放自定义类型时，由于自定义类型在未重写equals方法前， 判断是否重复的依据是地址值，所以如果想根据内容判断是否为重复元素，需要重写元素的 equals方法。

• HashSet 的 add() 和 contains() 底层都依赖hashCode()与 equals()

Set集合不能存放重复元素，其添加方法在添加时会判断是否有重复元素，有重复不添加，没重复则添加。
HashSet集合由于是无序的，其判断唯一的依据是元素类型的hashCode与equals方法的返回结果。规则如下：

1. 先判断新元素与集合内已经有的旧元素的HashCode值
2. 如果不同，说明是不同元素，添加到集合。
3. 如果相同，再判断equals比较结果。返回true则相同元素；返回false则不同元素，添加到集合。
所以，使用HashSet存储自定义类型，如果没有重写该类的 hashCode()与equals()，则判断重复时，使用的是地址值，如果想通过内容比较元素是否相同，需要重写该元素类的 hashcode()与equals()。

---

七、TreeSet

1.概述

• Set 的另外一种实现，底层由 红黑树 实现；也就是说TreeSet会根据元素的大小关系，将元素默认从小到大排列

• 特点：

• 元素无序（迭代或者存储顺序和插入顺序）

• 不能存储重复元素

• 没有位序

• Comparator comparator()；如果TreeSet采用了定制排序，则该方法返回定制排序所使用 Comparator；如果TreeSet采用了自然排序，则返回null；

2. TreeSet如何实现，不能存储重复元素

• 其实，在真正的添加元素，treeset 的 add方法 会搜索整颗红黑树(这个元素值，是否已经存在于当前集合，如果存在，则不添加，不存在，就添加）

3. 向TreeSet中放入，自定义的类的对象

• 如果试图把一个对象添加到 TreeSet 时，则该对象的类必须实现Comparable接口，否则程序会抛出异常 java.lang.ClassCastException

现象：直接向一个 TreeSet 中放入自定义类型的对象，发现直接抛出异常
原因：TreeSet 不知道如何对自定义的类对象进行排序，不像字符串可以根据字典顺序

• 如何向TreeSet中放入自定义类型的对象？

通过某种方式告诉 TreeSet 我们 自定义对象的比较规则

• 如何自定义比较规则？
• 第一种方式：放入TreeSet 中的元素实现Comparable接口，根据 CompareTo 方法来指定比较规则：比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象，则分别返回负整数、零或正整数。负整数 -> 小于，0 -> 等于，正整数 -> 大于

//compareTo方法
@Override
public int compareTo(Student o) {
    int result;
    if(age == o.age) {
        //当两个同学的年龄形同的时候，进一步按照名字排序
       result =  name.compareTo(o.name);
    } else if(age > o.age) {
        result = 100;
    } else {
        result = -34;
    }
    return result;
}

• 第二种方式：给 TreeSet 对象定义比较器Comparator

//通过比较器，来制定比较的规则
TreeSet<Student> students = new TreeSet<>(new Comparator<Student>() {
    @Override
    public int compare(Student o1, Student o2) {
    return o1.getAge() - o2.getAge();
    }
}); 

4. 注意事项

• 约定俗成：一旦元素添加到 TreeSet 之后，禁止修改TreeSet中的元素值
• 原因：修改完TreeSet中的对象后，TreeSe t不会重新调整该元素在树中的位置