java集合及源码 - IPS99技术分享

数组在内存存储方面的特点

        – 数组初始化以后，长度就确定了。

        – 数组中的添加的元素是依次紧密排列的，有序的，可以重复的。

        – 数组声明的类型，就决定了进行元素初始化时的类型。不是此类型的变量，就不能添加。
 int[] arr = new int[10];
      arr[0] = 1;
      arr[1] = "AA";//编译报错

      Object[] arr1 = new Object[10];
      arr1[0] = new String();
      arr1[1] = new Date();
        – 可以存储基本数据类型值，也可以存储引用数据类型的变量

• 数组在存储数据方面的弊端：

        – 数组初始化以后，长度就不可变了，不便于扩展

        – 数组中提供的属性和方法少，不便于进行添加、删除、插入、获取元素个数等操作，且效率不高。

        – 数组存储数据的特点单一，只能存储有序的、可以重复的数据

集合

特点：

唯一性：集合中的每个元素都是唯一的，不允许重复。
无序性：集合中的元素没有特定的顺序，即元素的存储和访问顺序是随机的。
高效的查找和插入操作：集合提供了高效的查找和插入操作，时间复杂度为O(1)。
支持集合操作：集合支持并集、交集、差集等集合操作，方便进行集合间的比较和合并。

缺点：

元素无序：由于集合是无序的，无法按照特定的顺序访问元素。
元素不可重复：集合中的元素必须是唯一的，无法存储重复的元素。
元素不可修改：集合中的元素一旦被添加，就无法修改，只能进行删除操作。
不支持索引访问：由于集合是无序的，无法通过索引直接访问元素。

1.2Java集合框架体系

Collection接口：是集合框架的根接口，定义了集合的基本操作，如添加、删除、遍历等。Collection接口有两个子接口：List和Set。

List接口：表示有序的集合，允许重复元素。List接口的常用实现类有ArrayList、LinkedList和Vector。

Set接口：表示无序的集合，不允许重复元素。Set接口的常用实现类有HashSet、LinkedHashSet和TreeSet。

Map接口：表示键值对的集合，键和值都可以是任意类型。Map接口的常用实现类有HashMap、LinkedHashMap和TreeMap。

Queue接口：表示队列，遵循先进先出（FIFO）的原则。Queue接口的常用实现类有LinkedList和PriorityQueue。

Deque接口：表示双端队列，可以在队列的两端进行元素的添加和删除操作。Deque接口的常用实现类有LinkedList和ArrayDeque。

Iterator接口：表示迭代器，用于遍历集合中的元素。Iterator接口的常用方法有hasNext()、next()和remove()。

Iterable接口：表示可迭代的对象，可以通过迭代器遍历其中的元素。Iterable接口的常用方法有iterator()。

常用

java.util.Collection:存储一个一个的数据
|-----子接口：List:存储有序的、可重复的数据 ("动态"数组)
|---- ArrayList(主要实现类)、LinkedList、Vector

|-----子接口：Set:存储无序的、不可重复的数据(高中学习的集合)
|---- HashSet(主要实现类)、LinkedHashSet、TreeSet

java.util.Map:存储一对一对的数据(key-value键值对，(x1,y1)、(x2,y2) --> y=f(x),类似于高中的函数)
|---- HashMap(主要实现类)、LinkedHashMap、TreeMap、Hashtable、Properties

二. Collection中的常用方法

添加元素：

boolean add(E e): 向集合中添加一个元素。如果集合不包含该元素，则返回true，否则返回false。

移除元素：

boolean remove(Object o): 从集合中移除指定元素。如果集合包含该元素，则返回true，否则返回false。

判断集合是否包含某个元素：

boolean contains(Object o): 判断集合是否包含指定元素。

清空集合：

void clear(): 移除集合中的所有元素。

获取集合的大小：

int size(): 返回集合中的元素个数。

判断集合是否为空：

boolean isEmpty(): 判断集合是否为空。

迭代集合中的元素：

Iterator<E> iterator(): 返回一个迭代器，用于遍历集合中的元素。

将集合转换为数组：

<T> T[] toArray(T[] a): 返回一个包含集合中所有元素的数组。

批量添加元素：

boolean addAll(Collection<? extends E> c): 将指定集合中的所有元素添加到该集合中。

批量移除元素：

boolean removeAll(Collection<?> c): 从该集合中移除指定集合中的所有元素。

保留集合中与指定集合的交集：

boolean retainAll(Collection<?> c): 仅保留该集合中与指定集合的交集元素。

检查集合是否与指定集合相等：

boolean equals(Object o): 如果指定对象与该集合相等，则返回true。

返回集合的哈希码值：

int hashCode(): 返回该集合的哈希码值。

1. 常用方法：（Collection中定义了15个抽象方法。

添加

（1）add(Object obj)：添加元素对象到当前集合中
（2）addAll(Collection other)：添加other集合中的所有元素对象到当前集合中，即this = this ∪ other

判断

（3）int size()：获取当前集合中实际存储的元素个数
（4）boolean isEmpty()：判断当前集合是否为空集合
（5）boolean contains(Object obj)：判断当前集合中是否存在一个与obj对象equals返回true的元素
（6）boolean containsAll(Collection coll)：判断coll集合中的元素是否在当前集合中都存在。即coll集合是否是当前集合的“子集”
（7）boolean equals(Object obj)：判断当前集合与obj是否相等

删除

（8）void clear()：清空集合元素
（9） boolean remove(Object obj) ：从当前集合中删除第一个找到的与obj对象equals返回true的元素。
（10）boolean removeAll(Collection coll)：从当前集合中删除所有与coll集合中相同的元素。即this = this - this ∩ coll
（11）boolean retainAll(Collection coll)：从当前集合中删除两个集合中不同的元素，使得当前集合仅保留与coll集合中的元素相同的元素，即当前集合中仅保留两个集合的交集，即this = this ∩ coll；

其它

（12）Object[] toArray()：返回包含当前集合中所有元素的数组
（13）hashCode()：获取集合对象的哈希值
***************************************************************************
（14）iterator()：返回迭代器对象，用于集合遍历
（15）forEach(Consumer action)：从当前集合中取出每一个元素，并执行给定的action指定的操作。

package Exer1.test1;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;


public class CollectionTest {
    /*
    *   （1）add(Object obj)：添加元素对象到当前集合中
        （2）addAll(Collection other)：添加other集合中的所有元素对象到当前集合中，即this = this ∪ other
    * */
    @Test
    public void test() {
        Collection coll = new ArrayList();

        //add()增加
        coll.add("AA");
        coll.add(123);//自动装箱
        coll.add("肆小七");
        coll.add(new Object());
        coll.add(new Person("Tom", 12));
        System.out.println(coll);//[AA, 123, 肆小七, java.lang.Object@2a18f23c, Person{name='Tom', age=12}]

        //addAll(Collection other)
        Collection coll1 = new ArrayList();
        coll1.add("BB");
        coll1.add(456);


        System.out.println(coll.size());//5

        coll.addAll(coll1);
//        coll.add(coll1);

        System.out.println(coll);//[AA, 123, 肆小七, java.lang.Object@2a18f23c, Person{name='Tom', age=12}, BB, 456]


        //size():
        System.out.println(coll.size());//7


    }

    /*
        （3）int size()：获取当前集合中实际存储的元素个数
        （4）boolean isEmpty()：判断当前集合是否为空集合
        （5）boolean contains(Object obj)：判断当前集合中是否存在一个与obj对象equals返回true的元素
        （6）boolean containsAll(Collection coll)：判断coll集合中的元素是否在当前集合中都存在。即coll集合是否是当前集合的“子集”
        （7）boolean equals(Object obj)：判断当前集合与obj是否相等
    */

    @Test
    public void test2() {
        Collection coll = new ArrayList();

        //add()
        coll.add("AA");
        Person p1 = new Person("Tom", 12);
        coll.add(p1);
        coll.add(128);//自动装箱
        coll.add(new String("肆小七"));

        //isEmpty()
        System.out.println(coll.isEmpty());//false

        //contains(Object obj)
        System.out.println(coll.contains("AA"));//true
        System.out.println(coll.contains(128));//true
        System.out.println(coll.contains(new String("肆小七")));//true
        System.out.println(coll.contains(new Person("Tom", 12)));//被调用2次 false-->true


        //containsAll(Collection coll)
        Collection coll1 = new ArrayList();

        //add()
        coll1.add("AA");
        coll1.add(128);
//        coll1.add("BB");

        System.out.println(coll.containsAll(coll1));//true
    }

    /*
    *   （8）void clear()：清空集合元素
        （9） boolean remove(Object obj) ：从当前集合中删除第一个找到的与obj对象equals返回true的元素。
        （10）boolean removeAll(Collection coll)：从当前集合中删除所有与coll集合中相同的元素。即this = this - this ∩ coll
        （11）boolean retainAll(Collection coll)：从当前集合中删除两个集合中不同的元素，使得当前集合仅保留与coll集合中的元素相同的元素，即当前集合中仅保留两个集合的交集，即this  = this ∩ coll；
    *
    * */
    @Test
    public void test3() {
        Collection coll = new ArrayList();

        coll.add("AA");
        coll.add("AA");
        Person p1 = new Person("Tom", 12);
        coll.add(p1);
        coll.add(128);//自动装箱
        coll.add(new String("肆小七"));
        System.out.println(coll);
//        coll.clear();
//        System.out.println(coll);
//        System.out.println(coll.size());//0

        //remove(Object obj)
        coll.remove(new Person("Tom", 12));

        coll.remove("AA");
        System.out.println(coll);

    }

    /*
    *  （12）Object[] toArray()：返回包含当前集合中所有元素的数组
        （13）hashCode()：获取集合对象的哈希值
        （14）iterator()：返回迭代器对象，用于集合遍历
    * */
    @Test
    public void test4() {
        Collection coll = new ArrayList();

        coll.add("AA");
        coll.add("AA");
        Person p1 = new Person("Tom", 12);
        coll.add(p1);
        coll.add(128);//自动装箱
        coll.add(new String("肆小七"));
        //集合 ---> 数组
        Object[] arr = coll.toArray();
        System.out.println(Arrays.toString(arr));//[AA, AA, Person{name='Tom', age=12}, 128, 肆小七]

        //hashCode():
        System.out.println(coll.hashCode());//469231963

    }

    @Test
    public void test5() {
        String[] arr = new String[]{"AA", "BB", "CC"};
        Collection list = Arrays.asList(arr);
        System.out.println(list);//[AA, BB, CC]

        List list1 = Arrays.asList("AA", "BB", "CC", "DD");

        System.out.println(list1);//[AA, BB, CC, DD]
    }

    @Test
    public void test6() {
        Integer[] arr = new Integer[]{1, 2, 3};
        List list = Arrays.asList(arr);
        System.out.println(list.size());//3
        System.out.println(list);//[1, 2, 3]


        int[] arr1 = new int[]{1, 2, 3};
        List list1 = Arrays.asList(arr1);
        System.out.println(list1.size());//1
        System.out.println(list1);//[[I@256216b3]
    }
}


public class Person {
    String name;
    int age;

    public Person() {
    }

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        System.out.println("Person equals()...");
        if (this == o) {return true;
        }
        if (o == null || getClass() != o.getClass()) return false;
            Person person = (Person) o;

        return age == person.age && Objects.equals(name, person.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

}

集合与数组的相互转换

集合转换为数组：调用方法toArray( )。

数组转化为集合：调用Arrays的静态方法asList(Object ... objs)。

向Collection中添加元素的要求：

要求元素所属的类一定要重写equals( )。因为Collection中的相关方法在使用时，要调用元素所在类的equals( )。

三Iterator(迭代器)接口

3.0源码

public interface Iterator<E> {
    boolean hasNext(); // 判断集合中是否还有元素
    E next(); // 返回集合中的下一个元素
    default void remove() { // 删除集合中的当前元素
        throw new UnsupportedOperationException("remove");
    }
    default void forEachRemaining(Consumer<? super E> action) { // 对集合中的剩余元素进行操作
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

3.1作用及格式

作用：用来遍历集合元素

Iterator接口的主要方法包括：
hasNext()：判断集合中是否还有元素，如果有返回true，否则返回false。
next()：返回集合中的下一个元素。
remove()：删除集合中的当前元素。默认情况下，该方法会抛出UnsupportedOperationException异常，需要子类重写该方法。
forEachRemaining(Consumer<? super E> action)：对集合中的剩余元素进行操作。该方法接受一个Consumer接口的实现，对剩余的每个元素执行相应的操作。
Collection<String> collection = new ArrayList<>();
collection.add("A");
collection.add("B");
collection.add("C");

Iterator<String> iterator = collection.iterator();
while (iterator.hasNext()) {
    String element = iterator.next();
    System.out.println(element);
}

3.2原理

Iterator 迭代器对象在遍历集合时，内部采用指针的方式来跟踪集合中的元素，
Iterator接口的原理是通过维护一个指向集合中下一个元素的指针，当调用next()方法时，指针会移动到下一个元素，并返回该元素。当调用hasNext()方法时，会检查指针是否指向集合中的最后一个元素，如果是，则返回false，否则返回true。当调用remove()方法时，会删除当前指针指向的元素，并移动指针到下一个元素。

3.3注意

• Iterator 可以删除集合的元素，但是遍历过程中通过迭代器对象的 remove 方法，不是集合对象的 remove 方法。 • 如果还未调用 next()或在上一次调用 next() 方法之后已经调用了 remove() 方法，再调用 remove()都会报 IllegalStateException。 • Collection 已经有 remove(xx)方法了，为什么 Iterator 迭代器还要提供删除方法呢？因为迭代器的 remove()可以按指定的条件进行删除。

public class IteratorTest {
    @Test
    public void test1() {
        Collection coll = new ArrayList();

        coll.add("AA");
        coll.add("AA");
        Person p1 = new Person("Tom", 12);
        coll.add(p1);
        coll.add(128);//自动装箱
        coll.add(new String("肆小七"));

        //获取迭代器对象
        Iterator iterator = coll.iterator();
       System.out.println(iterator.getClass());

        //方式1：
//        System.out.println(iterator.next());
//        System.out.println(iterator.next());
//        System.out.println(iterator.next());
//        System.out.println(iterator.next());
//        System.out.println(iterator.next());
//
//        System.out.println(iterator.next());//如果超出了集合中元素的个数，会报NoSuchElementException异常

//        //方式2：
//        for(int i = 0;i < coll.size();i++){
//            System.out.println(iterator.next());
//        }

        //方式3：推荐
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }

    @Test
    public void test2() {
        Collection coll = new ArrayList();

        coll.add("AA");
        coll.add("BB");
        Person p1 = new Person("Tom", 12);
        coll.add(p1);
        coll.add(128);//自动装箱
        coll.add(new String("肆小七"));

        //方式1：错误的遍历 在while循环的条件判断中，iterator.next()方法被调用了两次，
        // 这是错误的。正确的做法是先调用iterator.next()获取元素，然后判断该元素是否为null。
//        Iterator iterator = coll.iterator();
//
//        while((iterator.next()) != null){
//            System.out.println(iterator.next());
//        }

        //方式2：错误的遍历
        //每次调用coll.iterator()，都会返回一个新的迭代器对象。只会遍历同一个元素
        while (coll.iterator().hasNext()) {
            System.out.println(coll.iterator().next());
        }
    }
}

3.4获取迭代器(Iterator)对象

Iterator iterator = coll.iterator();

3.5. 实现遍历(代码实现)

while(iterator.hasNext()){
    System.out.println(iterator.next()); //next():①指针下移 ② 将下移以后集合位置上的元素返回
}

3.6 Iterator 接口的常用方法

– public E next() :返回迭代的下一个元素。 – public boolean hasNext() :如果仍有元素可以迭代，则返回 true。

四foreach 循环

4.1foreach 循环作用

高级 for 循环，专门用来 遍历数组和集合 的。

4.2语法格式

for ( 元素的数据类型局部变量 : Collection 集合或数组 ){ // 操作局部变量的输出操作 } // 这里局部变量就是一个临时变量，自己命名就可以
for(要遍历的集合或数组元素的类型 临时变量 : 要遍历的集合或数组变量){
    操作临时变量的输出
}

4.3foreach循环的原理

首先获取集合或数组的迭代器（Iterator）对象，可以通过调用集合的iterator()方法或数组的for-each方法获取迭代器对象。

然后通过调用迭代器的hasNext()方法判断集合或数组中是否还有元素，如果有返回true，否则返回false。

如果hasNext()方法返回true，则通过调用迭代器的next()方法获取集合或数组中的下一个元素。

对获取到的元素进行相应的操作。
重复步骤2-4，直到hasNext()方法返回false，表示集合或数组中的所有元素都已经遍历完毕。
//增强for循环
public class ForTest {
    @Test
    public void test(){
        Collection coll = new ArrayList();

        coll.add("AA");
        coll.add("BB");
        Person p1 = new Person("Tom",12);
        coll.add(p1);
        coll.add(128);//自动装箱
        coll.add(new String("肆小七"));


        for(Object obj : coll){
            System.out.println(obj);
        }

    }

    @Test
    public void test2(){
        int[] arr = new int[]{1,2,3,4,5};

        for(int i : arr){
            System.out.println(i);
        }
    }

    @Test
    public void test3(){
        String[] arr = new String[]{"GG","JJ","DD","MM","SS"};

        for(String s : arr){
            System.out.println(s);
        }
    }
}

五.Collection 子接口 1：List

List 集合类中元素有序、且可重复，集合中的每个元素都有其对应的顺序索引

5.1源码

public interface List<E> extends Collection<E> {
    // 添加元素
    boolean add(E e); // 在集合末尾添加一个元素
    void add(int index, E element); // 在指定位置添加一个元素
    boolean addAll(Collection<? extends E> c); // 将指定集合中的所有元素添加到集合末尾
    boolean addAll(int index, Collection<? extends E> c); // 将指定集合中的所有元素添加到指定位置

    // 删除元素
    void clear(); // 清空集合中的所有元素
    E remove(int index); // 删除指定位置的元素
    boolean remove(Object o); // 删除指定元素
    boolean removeAll(Collection<?> c); // 删除指定集合中的所有元素

    // 修改元素
    E set(int index, E element); // 修改指定位置的元素
    ListIterator<E> listIterator(); // 获取一个ListIterator对象，用于双向遍历和修改元素
    ListIterator<E> listIterator(int index); // 获取一个ListIterator对象，用于双向遍历和修改元素，指定起始位置

    // 获取元素
    E get(int index); // 获取指定位置的元素
    int indexOf(Object o); // 获取指定元素的第一个索引
    int lastIndexOf(Object o); // 获取指定元素的最后一个索引
    List<E> subList(int fromIndex, int toIndex); // 获取指定范围内的子列表

    // 其他方法
    boolean retainAll(Collection<?> c); // 保留指定集合中的所有元素，删除其他元素
    boolean containsAll(Collection<?> c); // 判断集合中是否包含指定集合中的所有元素
    boolean isEmpty(); // 判断集合是否为空
    int size(); // 获取集合的大小
    Object[] toArray(); // 将集合转换为数组
    <T> T[] toArray(T[] a); // 将集合转换为指定类型的数组
    // ...
}

List接口的常用实现类有ArrayList、LinkedList和Vector。

需要注意的是，List接口中的索引是从0开始的，可以通过索引访问、添加、删除和修改元素。List接口还提供了subList()方法，用于获取集合的子列表。此外，List接口还提供了listIterator()方法，用于获取ListIterator对象，可以通过ListIterator对象进行双向遍历和修改元素。

5.2List及其实现类特点

java.util.Collection:存储一个一个的数据
|-----子接口：List:存储有序的、可重复的数据 ("动态"数组)
|---- ArrayList:List的主要实现类；线程不安全的、效率高；底层使用Object[]数组存储
在添加数据、查找数据时，效率较高；在插入、删除数据时，效率较低

|---- LinkedList:底层使用双向链表的方式进行存储；在对集合中的数据进行频繁的删除、插入操作时，建议使用此类
在插入、删除数据时，效率较高；在添加数据、查找数据时，效率较低；
|---- Vector:List的古老实现类；线程安全的、效率低；底层使用Object[]数组存储

ArrayList源码

JDK1.7

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    // 默认初始容量
    private static final int DEFAULT_CAPACITY = 10;

    // 空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};

    // 用于存储元素的数组
    private transient Object[] elementData;

    // 集合的大小
    private int size;

    // 构造函数
    public ArrayList() {
        this.elementData = EMPTY_ELEMENTDATA; // 无参构造函数，默认初始容量为10
    }

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity]; // 有参构造函数，可以指定初始容量
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA; // 初始容量为0，使用空数组
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity); // 初始容量小于0，抛出异常
        }
    }

    // 添加元素
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 确保容量足够
        elementData[size++] = e; // 添加元素
        return true;
    }

    // 删除元素
    public E remove(int index) {
        rangeCheck(index); // 检查索引是否越界
        modCount++;
        E oldValue = elementData(index); // 获取要删除的元素
        int numMoved = size - index - 1; // 计算需要移动的元素数量
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // 将最后一个元素置为null，便于垃圾回收
        return oldValue;
    }

    // 获取元素
    public E get(int index) {
        rangeCheck(index); // 检查索引是否越界
        return elementData(index);
    }

    //方法：set()方法相关
public E set(int index, E element) {
    rangeCheck(index); //检验 index 是否合法
    //取出[index]位置的元素，[index]位置的元素就是要被替换的元素，用于最
    后返回被替换的元素
    E oldValue = elementData(index);
    //用 element 替换[index]位置的元素
    elementData[index] = element;
    return oldValue;
}

//方法：get()相关方法
public E get(int index) {
    rangeCheck(index); //检验 index 是否合法
    return elementData(index); //返回[index]位置的元素
}

//方法：indexOf()
public int indexOf(Object o) {
    //分为 o 是否为空两种情况
    if (o == null) {
        //从前往后找
        for (int i = 0; i < size; i++)
            if (elementData[i] == null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

//方法：lastIndexOf()
public int lastIndexOf(Object o) {
    //分为 o 是否为空两种情况
    if (o == null) {
        //从后往前找
        for (int i = size - 1; i >= 0; i--)
            if (elementData[i] == null)
                return i;
    } else {
        for (int i = size - 1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;

}

JDK1.8

//属性
transient Object[] elementData;
private int size;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//构造器
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; //初始化为
    空数组
}

//方法:add()相关方法
public boolean add(E e) {
    //查看当前数组是否够多存一个元素
    ensureCapacityInternal(size + 1); // Increments modCount!!
    //存入新元素到[size]位置，然后 size 自增 1
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacit
            y));
}

private static int calculateCapacity(Object[] elementData, int minCap
acity) {
    //如果当前数组还是空数组
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //那么 minCapacity 取 DEFAULT_CAPACITY 与 minCapacity 的最大值
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

//查看是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++; //修改次数加 1
    //如果需要的最小容量比当前数组的长度大，即当前数组不够存，就扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length; //当前数组容量
    int newCapacity = oldCapacity + (oldCapacity >> 1); //新数组容量是旧数组容量的 1.5 倍
    //看旧数组的 1.5 倍是否够
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //看旧数组的 1.5 倍是否超过最大数组限制
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //复制一个新数组
    elementData = Arrays.copyOf(elementData, newCapacity);
}

ArrayList源码其他方法

ensureCapacity(int minCapacity)：确保ArrayList的容量至少为minCapacity，如果容量不足，则进行扩容。
trimToSize()：将ArrayList的容量调整为实际元素的数量，以节省空间。
clone()：返回ArrayList的副本。
toArray()：将ArrayList转换为数组。
toArray(T[] a)：将ArrayList转换为指定类型的数组。
contains(Object o)：判断ArrayList中是否包含指定元素。
indexOf(Object o)：返回指定元素在ArrayList中的第一个索引。
lastIndexOf(Object o)：返回指定元素在ArrayList中的最后一个索引。
subList(int fromIndex, int toIndex)：返回指定范围内的子列表。
sort(Comparator<? super E> c)：根据指定的比较器对ArrayList进行排序。
forEach(Consumer<? super E> action)：对ArrayList中的每个元素执行指定的操作。
removeIf(Predicate<? super E> filter)：删除满足指定过滤条件的所有元素。
replaceAll(UnaryOperator<E> operator)：使用指定的操作替换ArrayList中的每个元素。
sort(Comparator<? super E> c)：根据指定的比较器对ArrayList进行排序。
parallelSort(Comparator<? super E> c)：使用并行流对ArrayList进行排序。
spliterator()：返回ArrayList的Spliterator对象，用于并行处理ArrayList中的元素。
iterator()：返回ArrayList的Iterator对象，用于遍历ArrayList中的元素。
listIterator()：返回ArrayList的ListIterator对象，用于双向遍历和修改ArrayList中的元素。
listIterator(int index)：返回ArrayList的ListIterator对象，用于双向遍历和修改ArrayList中的元素，指定起始位置。

         首先定义了一个默认的初始容量DEFAULT_CAPACITY，以及一个空数组EMPTY_ELEMENTDATA。然后定义了一个用于存储元素的数组elementData和一个表示集合大小的变量size。

        ArrayList的构造函数有两种，

                一种是无参构造函数，默认初始容量为10；

                另一种是有参构造函数，可以指定初始容量。

        ArrayList的add()方法用于添加元素，首先会确保容量足够，然后将元素添加到数组的末尾，并更新size。

        ArrayList的remove()方法用于删除元素，首先会检查索引是否越界，然后获取要删除的元素，计算需要移动的元素数量，最后将最后一个元素置为null，便于垃圾回收。

ArrayList的get()方法用于获取元素，首先会检查索引是否越界，然后返回指定索引位置的元素。

        ArrayList的set()方法用于修改元素，size()方法用于获取集合的大小，toArray()方法用于将集合转换为数组等。

ArrayList源码总结

jdk7版本：(以jdk1.7.0_07为例)

//如下代码的执行：底层会初始化数组，数组的长度为10。Object[] elementData = new Object[10];
ArrayList<String> list = new ArrayList<>();

list.add("AA"); //elementData[0] = "AA";
list.add("BB");//elementData[1] = "BB";
...
当要添加第11个元素的时候，底层的elementData数组已满，则需要扩容。默认扩容为原来长度的1.5倍。并将原有数组
中的元素复制到新的数组中。

jdk8版本:(以jdk1.8.0_271为例)

//如下代码的执行：底层会初始化数组，即：Object[] elementData = new Object[]{};
ArrayList<String> list = new ArrayList<>();

list.add("AA"); //首次添加元素时，会初始化数组elementData = new Object[10];elementData[0] = "AA";
list.add("BB");//elementData[1] = "BB";
...
当要添加第11个元素的时候，底层的elementData数组已满，则需要扩容。默认扩容为原来长度的1.5倍。并将原有数组中的元素复制到新的数组中。

小结：
jdk1.7.0_07版本中：ArrayList类似于饿汉式
jdk1.8.0_271版本中：ArrayList类似于懒汉式

LinkedList源码

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    // 链表的大小
    transient int size = 0;

    // 链表的头部节点
    transient Node<E> first;

    // 链表的尾部节点
    transient Node<E> last;

    // 链表节点
    private static class Node<E> {
        E item; // 节点元素
        Node<E> next; // 指向后一个节点的指针
        Node<E> prev; // 指向前一个节点的指针

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element; // 初始化节点元素
            this.next = next; // 初始化指向后一个节点的指针
            this.prev = prev; // 初始化指向前一个节点的指针
        }
    }

    // 构造函数
    public LinkedList() {
    }

    // 添加元素
    public boolean add(E e) {
        linkLast(e); // 将元素添加到链表的尾部
        return true;
    }

    // 删除元素
    public E remove(int index) {
        checkElementIndex(index); // 检查索引是否越界
        return unlink(node(index)); // 删除指定索引位置的节点
    }

    // 获取元素
    public E get(int index) {
        checkElementIndex(index); // 检查索引是否越界
        return node(index).item; // 返回指定索引位置的节点的元素
    }

    // 其他方法
    // ...
}

//属性
transient Node<E> first; //记录第一个结点的位置
transient Node<E> last; //记录当前链表的尾元素
transient int size = 0; //记录最后一个结点的位置

//构造器
public LinkedList() {
}

//方法：add()相关方法
public boolean add(E e) {
    linkLast(e); //默认把新元素链接到链表尾部
    return true;
}

void linkLast(E e) {
    final Node<E> l = last; //用 l 记录原来的最后一个结点
    //创建新结点
    final Node<E> newNode = new Node<>(l, e, null);
    //现在的新结点是最后一个结点了
    last = newNode;
    //如果 l==null，说明原来的链表是空的
    if (l == null)
        //那么新结点同时也是第一个结点
        first = newNode;
    else
        //否则把新结点链接到原来的最后一个结点的 next 中
        l.next = newNode;
    //元素个数增加
    size++;
    //修改次数增加
    modCount++;
}

//其中，Node 类定义如下
private static class Node<E> {
    E item; //元素数据
    Node<E> next; //下一个结点
    Node<E> prev; //前一个结点

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

//方法：获取 get()相关方法
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

//方法：插入 add()相关方法
public void add(int index, E element) {
    checkPositionIndex(index);//检查 index 范围
    if (index == size)//如果 index==size，连接到当前链表的尾部
        linkLast(element);
    else
        linkBefore(element, node(index));
}

Node<E> node(int index) {
    // assert isElementIndex(index);
/*
index < (size >> 1)采用二分思想，先将 index 与长度 size 的一半比较，如
果 index<size/2，就只从位置 0
往后遍历到位置 index 处，而如果 index>size/2，就只从位置 size 往前遍历到
位置 index 处。这样可以减少一部
分不必要的遍历。
*/
    //如果 index<size/2，就从前往后找目标结点
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {//否则从后往前找目标结点
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

//把新结点插入到[index]位置的结点 succ 前面
void linkBefore(E e, Node<E> succ) {//succ 是[index]位置对应的结点
    // assert succ != null;
    final Node<E> pred = succ.prev; //[index]位置的前一个结点
    //新结点的 prev 是原来[index]位置的前一个结点
    //新结点的 next 是原来[index]位置的结点
    final Node<E> newNode = new Node<>(pred, e, succ);
    //[index]位置对应的结点的 prev 指向新结点
    succ.prev = newNode;
    //如果原来[index]位置对应的结点是第一个结点，那么现在新结点是第一个结
    点
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;//原来[index]位置的前一个结点的 next 指向新结
    点
    size++;
    modCount++;
}

//方法：remove()相关方法
public boolean remove(Object o) {
    //分 o 是否为空两种情况
    if (o == null) {
        //找到 o 对应的结点 x
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);//删除 x 结点
                return true;
            }
        }
    } else {
        //找到 o 对应的结点 x
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);//删除 x 结点
                return true;
            }
        }
    }
    return false;
}

E unlink(Node<E> x) {//x 是要被删除的结点
    // assert x != null;
    final E element = x.item;//被删除结点的数据
    final Node<E> next = x.next;//被删除结点的下一个结点
    final Node<E> prev = x.prev;//被删除结点的上一个结点
    //如果被删除结点的前面没有结点，说明被删除结点是第一个结点
    if (prev == null) {
        //那么被删除结点的下一个结点变为第一个结点
        first = next;
    } else {//被删除结点不是第一个结点
        //被删除结点的上一个结点的 next 指向被删除结点的下一个结点
        prev.next = next;
        //断开被删除结点与上一个结点的链接
        x.prev = null;//使得 GC 回收
    }
    //如果被删除结点的后面没有结点，说明被删除结点是最后一个结点
    if (next == null) {
        //那么被删除结点的上一个结点变为最后一个结点
        last = prev;
    } else {//被删除结点不是最后一个结点
        //被删除结点的下一个结点的 prev 执行被删除结点的上一个结点
        next.prev = prev;
        //断开被删除结点与下一个结点的连接
        x.next = null;//使得 GC 回收
    }
    //把被删除结点的数据也置空，使得 GC 回收
    x.item = null;
    //元素个数减少
    size--;
    //修改次数增加
    modCount++;
    //返回被删除结点的数据
    return element;
}

public E remove(int index) { //index 是要删除元素的索引位置
    checkElementIndex(index);
    return unlink(node(index));
}

首先定义了一个表示链表大小的变量size，以及一个表示链表头部节点的变量first和一个表示链表尾部节点的变量last。

        LinkedList的Node类表示链表节点，每个节点包含一个元素item，以及指向前一个节点prev和后一个节点next的指针。

        LinkedList的构造函数是无参构造函数，默认情况下，链表的大小为0，头部节点和尾部节点都为null。

        LinkedList的add()方法用于添加元素，首先会调用linkLast()方法将元素添加到链表的尾部。

        LinkedList的remove()方法用于删除元素，首先会检查索引是否越界，然后调用unlink()方法删除指定索引位置的节点。

        LinkedList的get()方法用于获取元素，首先会检查索引是否越界，然后返回指定索引位置的节点的元素。

         LinkedList的set()方法用于修改元素，size()方法用于获取链表的大小，toArray()方法用于将链表转换为数组等。

LinkedList源码其他方法

addFirst(E e)：将元素添加到链表的头部。
addLast(E e)：将元素添加到链表的尾部。
getFirst()：获取链表的头部元素。
getLast()：获取链表的尾部元素。
removeFirst()：删除链表的头部元素。
removeLast()：删除链表的尾部元素。
offerFirst(E e)：将元素添加到链表的头部，如果链表为空，则返回false。
offerLast(E e)：将元素添加到链表的尾部，如果链表为空，则返回false。
peekFirst()：获取链表的头部元素，如果链表为空，则返回null。
peekLast()：获取链表的尾部元素，如果链表为空，则返回null。
pollFirst()：获取并删除链表的头部元素，如果链表为空，则返回null。
pollLast()：获取并删除链表的尾部元素，如果链表为空，则返回null。
push(E e)：将元素添加到链表的头部，相当于addFirst(E e)。
pop()：获取并删除链表的头部元素，相当于removeFirst()。
contains(Object o)：判断链表中是否包含指定元素。
indexOf(Object o)：返回指定元素在链表中的第一个索引。
lastIndexOf(Object o)：返回指定元素在链表中的最后一个索引。
listIterator()：返回一个ListIterator对象，用于双向遍历和修改链表。
listIterator(int index)：返回一个ListIterator对象，用于双向遍历和修改链表，指定起始位置。
subList(int fromIndex, int toIndex)：返回指定范围内的子列表。

LinkedList在jdk8中的源码解析及总结

LinkedList<String> list = new LinkedList<>(); //底层也没做的什么
list.add("AA"); //将"AA"封装到一个Node对象1中，list对象的属性first、last都指向此Node对象1。
list.add("BB"); //将"BB"封装到一个Node对象2中，对象1和对象2构成一个双向链表，同时last指向此Node对象2

...
因为LinkedList使用的是双向链表，不需要考虑扩容问题。

LinkedList内部声明：
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
}

ArrayList 采用数组作为底层实现

ArrayList 自动扩容过程

ArrayList 的 add(E e)方法

ArrayList 的 add(int index,E e)方法

Vector源码

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    // 默认初始容量
    private static final int DEFAULT_CAPACITY = 10;

    // 用于存储元素的数组
    protected Object[] elementData;

    // 集合的大小
    protected int elementCount;

    // 增长因子
    protected int capacityIncrement;

    // 构造函数
    public Vector() {
        this(DEFAULT_CAPACITY); // 无参构造函数，默认初始容量为10
    }

    public Vector(int initialCapacity) {
        this(initialCapacity, 0); // 有参构造函数，可以指定初始容量
    }

    public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity); // 初始容量小于0，抛出异常
        this.elementData = new Object[initialCapacity]; // 初始化存储元素的数组
        this.capacityIncrement = capacityIncrement; // 初始化增长因子
    }

    // 添加元素
    public synchronized boolean add(E e) {
        modCount++; // 增加修改计数器
        ensureCapacityHelper(elementCount + 1); // 确保容量足够
        elementData[elementCount++] = e; // 添加元素
        return true;
    }

    // 删除元素
    public synchronized E remove(int index) {
        modCount++; // 增加修改计数器
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index); // 索引越界，抛出异常
        E oldValue = elementData(index); // 获取要删除的元素
        int numMoved = elementCount - index - 1; // 计算需要移动的元素数量
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved); // 移动元素
        elementData[--elementCount] = null; // 将最后一个元素置为null，便于垃圾回收
        return oldValue;
    }

    // 获取元素
    public synchronized E get(int index) {
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index); // 索引越界，抛出异常
        return elementData(index); // 返回指定索引位置的元素
    }

    // 其他方法
    // ...
}

JDK1.8

//属性
protected Object[] elementData;
protected int elementCount;

//构造器
public Vector() {
    this(10); //指定初始容量 initialCapacity 为 10
}

public Vector(int initialCapacity) {
    this(initialCapacity, 0); //指定 capacityIncrement 增量为 0
}

public Vector(int initialCapacity, int capacityIncrement) {
    super();
    //判断了形参初始容量 initialCapacity 的合法性
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: " + init
                ialCapacity);
    //创建了一个 Object[]类型的数组
    this.elementData = new Object[initialCapacity];
    //增量，默认是 0，如果是 0，后面就按照 2 倍增加，如果不是 0，后面就按照你
    指定的增量进行增量
    this.capacityIncrement = capacityIncrement;
}

//方法：add()相关方法
//synchronized 意味着线程安全的 
public synchronized boolean add(E e) {
    modCount++;
    //看是否需要扩容
    ensureCapacityHelper(elementCount + 1);
    //把新的元素存入[elementCount]，存入后，elementCount 元素的个数增 1
    elementData[elementCount++] = e;
    return true;
}

private void ensureCapacityHelper(int minCapacity) {
    //看是否超过了当前数组的容量
    if (minCapacity - elementData.length > 0)
        grow(minCapacity); //扩容
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length; //获取目前数组的长度
    //如果 capacityIncrement 增量是 0，新容量 = oldCapacity 的 2 倍
    //如果 capacityIncrement 增量是不是 0，新容量 = oldCapacity + capacit
    yIncrement 增量;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
            capacityIncrement : oldCapacity);
    //如果按照上面计算的新容量还不够，就按照你指定的需要的最小容量来扩容 mi
    nCapacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    //如果新容量超过了最大数组限制，那么单独处理
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //把旧数组中的数据复制到新数组中，新数组的长度为 newCapacity
    elementData = Arrays.copyOf(elementData, newCapacity);
}

//方法：remove()相关方法
public boolean remove(Object o) {
    return removeElement(o);
}

public synchronized boolean removeElement(Object obj) {
    modCount++;
    //查找 obj 在当前 Vector 中的下标
    int i = indexOf(obj);
    //如果 i>=0，说明存在，删除[i]位置的元素
    if (i >= 0) {
        removeElementAt(i);
        return true;
    }
    return false;
}

//方法：indexOf()
public int indexOf(Object o) {
    return indexOf(o, 0);
}

public synchronized int indexOf(Object o, int index) {
    if (o == null) {//要查找的元素是 null 值
        for (int i = index; i < elementCount; i++)
            if (elementData[i] == null)//如果是 null 值，用==null 判断
                return i;
    } else {//要查找的元素是非 null 值
        for (int i = index; i < elementCount; i++)
            if (o.equals(elementData[i]))//如果是非 null 值，用 equals 判
                断
        return i;
    }
    return -1;
}

//方法：removeElementAt()
public synchronized void removeElementAt(int index) {
    modCount++;
    //判断下标的合法性
    if (index >= elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " +
                elementCount);
    } else if (index < 0) {
        throw new ArrayIndexOutOfBoundsException(index);
    }
    //j 是要移动的元素的个数
    int j = elementCount - index - 1;
    //如果需要移动元素，就调用 System.arraycopy 进行移动
    if (j > 0) {
        //把 index+1 位置以及后面的元素往前移动
        //index+1 的位置的元素移动到 index 位置，依次类推
        //一共移动 j 个
        System.arraycopy(elementData, index + 1, elementData, index,
                j);
    }
    //元素的总个数减少
    elementCount--;
    //将 elementData[elementCount]这个位置置空，用来添加新元素，位置的元素等着被 GC 回收
    elementData[elementCount] = null; /* to let gc do its work */
}

        首先定义了一个默认的初始容量DEFAULT_CAPACITY，以及一个用于存储元素的数组elementData和一个表示集合大小的变量elementCount。

        Vector的构造函数有三种，

                一种是无参构造函数，默认初始容量为10；

                另一种是有参构造函数，可以指定初始容量；

                还有一种是有参构造函数，可以指定初始容量和增长因子。

        Vector的add()方法用于添加元素，首先会调用ensureCapacityHelper()方法确保容量足够，然后将元素添加到数组的末尾，并更新elementCount。

        Vector的remove()方法用于删除元素，首先会检查索引是否越界，然后获取要删除的元素，计算需要移动的元素数量，最后将最后一个元素置为null，便于垃圾回收。

Vector的get()方法用于获取元素，首先会检查索引是否越界，然后返回指定索引位置的元素。

        Vector还提供的set()方法用于修改元素，size()方法用于获取集合的大小，toArray()方法用于将集合转换为数组等。需要注意的是，Vector中的大部分方法都使用了synchronized关键字进行同步，因此在多线程环境下使用Vector是安全的。

Vector源码其他方法

ensureCapacity(int minCapacity)：确保Vector的容量至少为minCapacity，如果容量不足，则进行扩容。
trimToSize()：将Vector的容量调整为实际元素的数量，以节省空间。
clone()：返回Vector的副本。
toArray()：将Vector转换为数组。
toArray(T[] a)：将Vector转换为指定类型的数组。
contains(Object o)：判断Vector中是否包含指定元素。
indexOf(Object o)：返回指定元素在Vector中的第一个索引。
lastIndexOf(Object o)：返回指定元素在Vector中的最后一个索引。
subList(int fromIndex, int toIndex)：返回指定范围内的子列表。
sort(Comparator<? super E> c)：根据指定的比较器对Vector进行排序。
forEach(Consumer<? super E> action)：对Vector中的每个元素执行指定的操作。
removeIf(Predicate<? super E> filter)：删除满足指定过滤条件的所有元素。
replaceAll(UnaryOperator<E> operator)：使用指定的操作替换Vector中的每个元素。
sort(Comparator<? super E> c)：根据指定的比较器对Vector进行排序。
parallelSort(Comparator<? super E> c)：使用并行流对Vector进行排序。
spliterator()：返回Vector的Spliterator对象，用于并行处理Vector中的元素。
iterator()：返回Vector的Iterator对象，用于遍历Vector中的元素。
listIterator()：返回Vector的ListIterator对象，用于双向遍历和修改Vector中的元素。
listIterator(int index)：返回Vector的ListIterator对象，用于双向遍历和修改Vector中的元素，指定起始位置。

Vector源码总结：(以jdk1.8.0_271为例)

Vector v = new Vector(); //底层初始化数组，长度为10.Object[] elementData = new Object[10];
v.add("AA"); //elementData[0] = "AA";
v.add("BB");//elementData[1] = "BB";
...
当添加第11个元素时，需要扩容。默认扩容为原来的2倍。

5.3List中的常用方法

Collection中定义了15个抽象方法。
（1）add(Object obj)：添加元素对象到当前集合中
（2）addAll(Collection other)：添加other集合中的所有元素对象到当前集合中，即this = this ∪ other
（3）int size()：获取当前集合中实际存储的元素个数
（4）boolean isEmpty()：判断当前集合是否为空集合
（5）boolean contains(Object obj)：判断当前集合中是否存在一个与obj对象equals返回true的元素
（6）boolean containsAll(Collection coll)：判断coll集合中的元素是否在当前集合中都存在。即coll集合是否是当前集合的“子集”
（7）boolean equals(Object obj)：判断当前集合与obj是否相等
（8）void clear()：清空集合元素
（9） boolean remove(Object obj) ：从当前集合中删除第一个找到的与obj对象equals返回true的元素。
（10）boolean removeAll(Collection coll)：从当前集合中删除所有与coll集合中相同的元素。即this = this - this ∩ coll
（11）boolean retainAll(Collection coll)：从当前集合中删除两个集合中不同的元素，使得当前集合仅保留与coll集合中的元素相同的元素，即当前集合中仅保留两个集合的交集，即this = this ∩ coll；
（12）Object[] toArray()：返回包含当前集合中所有元素的数组
（13）hashCode()：获取集合对象的哈希值
***************************************************************************
（14）iterator()：返回迭代器对象，用于集合遍历
（15）forEach(Consumer action)：从当前集合中取出每一个元素，并执行给定的action指定的操作。

因为List是有序的，进而就有索引，进而就会增加一些针对索引操作的方法。
- 插入元素
- void add(int index, Object ele):在index位置插入ele元素
- boolean addAll(int index, Collection eles):从index位置开始将eles中的所有元素添加进来
- 获取元素
- Object get(int index):获取指定index位置的元素
- List subList(int fromIndex, int toIndex):返回从fromIndex到toIndex位置的子集合
- 获取元素索引
- int indexOf(Object obj):返回obj在集合中首次出现的位置
- int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置
- 删除和替换元素
- Object remove(int index)`:移除指定index位置的元素，并返回此元素
- Object set(int index, Object ele)`:设置指定index位置的元素为ele

list常用方法小结：
增
add(Object obj)
addAll(Collection coll)
删
remove(Object obj)
remove(int index)
改
set(int index, Object ele)
查
get(int index)
插
add(int index, Object ele)
addAll(int index, Collection eles)
长度
size()
遍历
iterator() ：使用迭代器进行遍历
增强for循环
一般的for循环
package Exer3;

import Exer1.test1.Person;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;


public class ListTest {

    /*
    * 增
        add(Object obj)
        addAll(Collection coll)
    删
        remove(Object obj)
        remove(int index)
    改
        set(int index, Object ele)
    查
        get(int index)
    插
        add(int index, Object ele)
        addAll(int index, Collection eles)
    长度
        size()
    遍历
        iterator() ：使用迭代器进行遍历
        增强for循环
        一般的for循环
    *
    * */
    @Test
    public void test1(){
        /*
    * 增
        add(Object obj)
        addAll(Collection coll)*/

        //增加 add(Object obj)
        List list =new ArrayList();
        list.add("肆小七");
        list.add("孙俊祥");
        list.add("方荣华");
        list.add(new Person("小七",19));

        System.out.println(list.toString());//[肆小七, 孙俊祥, 方荣华, Person{name='小七', age=19}]


        /*插
        add(int index, Object ele)
        addAll(int index, Collection eles)
        */

        //插入 add(int index, Object ele)
        list.add(2,"women");
        System.out.println(list.toString());//[肆小七, 孙俊祥, women, 方荣华, Person{name='小七', age=19}]

        //addAll(int index, Collection eles)
        List list1= Arrays.asList(1,2,3);
        list.addAll(1,list1);

        System.out.println(list.toString());//[肆小七, 1, 2, 3, 孙俊祥, women, 方荣华, Person{name='小七', age=19}]

        //区别：
        list.add(0,list1);//看成一个整体，插入
        System.out.println(list.toString());//[[1, 2, 3], 肆小七, 1, 2, 3, 孙俊祥, women, 方荣华, Person{name='小七', age=19}]
    }

    /*删
    remove(Object obj)
    remove(int index)*/
    @Test
    public void test2(){
        List list =new ArrayList();
        list.add("肆小七");
        list.add("孙俊祥");
        list.add("方荣华");
        list.add(new Person("小七",19));

        //起始
        System.out.println(list.toString());//[肆小七, 孙俊祥, 方荣华, Person{name='小七', age=19}]

        //删除索引为2的集合内容对象
        list.remove(2);
        System.out.println(list.toString());//[肆小七, 孙俊祥, Person{name='小七', age=19}]

    }
    @Test
    public void test3(){
     //遍历

       /*
       遍历
        1.iterator() ：使用迭代器进行遍历
        2.增强for循环
        3.一般的for循环
        */


        List list =new ArrayList();
        list.add("肆小七");
        list.add("孙俊祥");
        list.add("方荣华");
        list.add(new Person("小七",19));

        //方法1：使用迭代器进行遍历
        Iterator iterator = list.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
        //结果
        /*
         肆小七
         孙俊祥
         方荣华
         Person{name='小七', age=19}
         */

        //方法2 增强for循环
        for (Object o:list){
            System.out.println(o);
        }
        //结果
        /*
         肆小七
         孙俊祥
         方荣华
         Person{name='小七', age=19}
         */

        //方法3 for循环
        for (int i = 0; i < list.size() ; i++) {
            System.out.println(list.get(i));
        }

        //结果
        /*
         肆小七
         孙俊祥
         方荣华
         Person{name='小七', age=19}
         */
    }
}

• 只有 1 个元素的 LinkedList

• 包含 4 个元素的 LinkedList

• add(E e)方法

• add(int index,E e)方法

• remove(Object obj)方法

• remove(int index)方法

5.4ArrayList与 LinkedList

ArrayList底层使用数组结构，查找和添加（尾部添加）操作效率高，时间复杂度为O(1)
删除和插入操作效率低，时间复杂度为O(n)
LinkedList底层使用双向链表结构，删除和插入操作效率高，时间复杂度为O(1)
查找和添加（尾部添加）操作效率高，时间复杂度为O(n) (有可能添加操作是O(1))

5.5ArrayList、Vector的区别

线程安全性：ArrayList是非线程安全的，而Vector是线程安全的。Vector中的大部分方法都使用了synchronized关键字进行同步，因此在多线程环境下使用Vector是安全的。而ArrayList没有使用同步，因此在多线程环境下使用ArrayList需要手动进行同步，否则可能会导致数据不一致的问题。

性能：由于ArrayList是非线程安全的，因此在单线程环境下，ArrayList的性能通常比Vector更好。因为Vector需要进行同步操作，所以它的性能会稍差一些。

扩容策略：ArrayList和Vector在添加元素时，如果容量不足，都会进行扩容操作。ArrayList的默认扩容策略是每次扩容为原来的1.5倍，而Vector的默认扩容策略是每次扩容为原来的2倍。

5.6 ArrayList、LinkedList的区别

线程安全性：LinkedList是非线程安全的，因此在多线程环境下使用LinkedList需要手动进行同步。

性能：由于LinkedList是链表结构，因此在添加和删除元素时，LinkedList的性能通常比ArrayList和Vector更好。因为ArrayList和Vector在添加和删除元素时，需要移动元素，而LinkedList只需要修改指针。

空间复杂度：由于LinkedList是链表结构，因此LinkedList的空间复杂度通常比ArrayList和Vector更高。因为LinkedList需要存储每个节点的指针。

遍历方式：LinkedList提供了双向遍历的方法，可以通过调用listIterator()方法获取ListIterator对象，然后通过调用ListIterator对象的previous()和next()方法进行双向遍历。

六. Collection 子接口 2：Set

6.1Set 接口概述

• Set 接口是 Collection 的子接口，Set 接口相较于 Collection 接口没有提供额外的方法 • Set 集合不允许包含相同的元素，如果试把两个相同的元素加入同一个 Set 集合中，则添加操作失败。 • Set 集合支持的遍历方式和 Collection 集合一样：foreach 和 Iterator。 • Set 的常用实现类有：HashSet、TreeSet、LinkedHashSet。

6.2Set及其实现类特点

java.util.Collection:存储一个一个的数据
|-----子接口：Set:存储无序的、不可重复的数据(高中学习的集合)
|---- HashSet：主要实现类；底层使用的是HashMap，即使用数组+单向链表+红黑树结构进行存储。（jdk8中）
|---- LinkedHashSet：是HashSet的子类；在现有的数组+单向链表+红黑树结构的基础上，又添加了
一组双向链表，用于记录添加元素的先后顺序。即：我们可以按照添加元素的顺序
实现遍历。便于频繁的查询操作。
|---- TreeSet：底层使用红黑树存储。可以按照添加的元素的指定的属性的大小顺序进行遍历。

HashSet 源码

源码1

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    // 用于存储元素的哈希表
    private transient HashMap<E,Object> map;

    // 哈希表的默认初始容量
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    // 哈希表的默认加载因子
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 构造函数
    public HashSet() {
        map = new HashMap<>(); // 无参构造函数，默认初始容量为16
    }

    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity); // 有参构造函数，可以指定初始容量
    }

    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor); // 有参构造函数，可以指定初始容量和加载因子
    }

    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16)); // 有参构造函数，可以指定一个集合，将集合中的元素添加到HashSet中
        addAll(c);
    }

    // 添加元素
    public boolean add(E e) {
        return map.put(e, PRESENT)==null; // 添加元素，如果元素已经存在，则返回false，否则返回true
    }

    // 删除元素
    public boolean remove(Object o) {
        return map.remove(o)==PRESENT; // 删除元素，如果元素存在，则返回true，否则返回false
    }

    // 获取元素
    public boolean contains(Object o) {
        return map.containsKey(o); // 判断元素是否存在
    }

    // 其他方法
    // ...
}

源码2

//构造器
public HashSet() {
    map = new HashMap<>();
}

public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

//这个构造器是给子类 LinkedHashSet 调用的
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

//add()方法：
public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

//其中，
private transient HashMap<E, Object> map;
private static final Object PRESENT = new Object();

//iterator()方法：
public Iterator<E> iterator() {
    return map.keySet().iterator();
}

        首先定义了一个用于存储元素的哈希表map，以及哈希表的默认初始容量DEFAULT_INITIAL_CAPACITY和默认加载因子DEFAULT_LOAD_FACTOR。

        HashSet的构造函数有四种，

                一种是无参构造函数，默认初始容量为16；

                另一种是有参构造函数，可以指定初始容量；

                还有一种是有参构造函数，可以指定初始容量和加载因子；

                还有一种是有参构造函数，可以指定一个集合，将集合中的元素添加到HashSet中。

        HashSet的add()方法用于添加元素，首先会调用HashMap的put()方法将元素添加到哈希表中，如果元素已经存在，则返回false，否则返回true。

        HashSet的remove()方法用于删除元素，首先会调用HashMap的remove()方法删除元素，如果元素存在，则返回true，否则返回false。

        HashSet的contains()方法用于判断元素是否存在，首先会调用HashMap的containsKey()方法判断元素是否存在。

        HashSet的size()方法用于获取集合的大小，toArray()方法用于将集合转换为数组等。需要注意的是，HashSet是无序的，因此无法按照特定的顺序访问元素。

HashSet其他常用的方法

size()：返回HashSet的大小，即元素的数量。
isEmpty()：判断HashSet是否为空。
clear()：清空HashSet中的所有元素。
containsAll(Collection<?> c)：判断HashSet中是否包含指定集合中的所有元素。
addAll(Collection<? extends E> c)：将指定集合中的所有元素添加到HashSet中。
removeAll(Collection<?> c)：删除HashSet中指定集合中的所有元素。
retainAll(Collection<?> c)：保留HashSet中指定集合中的所有元素，删除其他元素。
equals(Object o)：判断两个HashSet是否相等。
hashCode()：返回HashSet的哈希码。
toArray()：将HashSet转换为数组。
toArray(T[] a)：将HashSet转换为指定类型的数组。
iterator()：返回HashSet的Iterator对象，用于遍历HashSet中的元素。
spliterator()：返回HashSet的Spliterator对象，用于并行处理HashSet中的元素。
parallelStream()：返回HashSet的并行流，用于并行处理HashSet中的元素。

HashSet 概述

• HashSet 是 Set 接口的主要实现类，大多数时候使用 Set 集合时都使用这个实现类。 • HashSet 按 Hash 算法来存储集合中的元素，因此具有很好的存储、查找、删除性能。 • HashSet 具有以下特点： – 不能保证元素的排列顺序 – HashSet 不是线程安全的 – 集合元素可以是 null • HashSet 集合判断两个元素相等的标准：两个对象通过 hashCode() 方法得到的哈希值相等，并且两个对象的 equals() 方法返回值为 true。 • 对于存放在 Set 容器中的对象，对应的类一定要重写 hashCode()和 equals(Object obj)方法 ，以实现对象相等规则。即：“相等的对象必须具有相等的散列码”。 • HashSet 集合中元素的无序性，不等同于随机性。这里的无序性与元素的添加位置有关。具体来说：我们在添加每一个元素到数组中时，具体的存储位置是由元素的hashCode()调用后返回的 hash 值决定的。导致在数组中每个元素不是依次紧密存放的，表现出一定的无序性。

HashSet 中添加元素的过程

• 第 1 步：当向 HashSet 集合中存入一个元素时，HashSet 会调用该对象hashCode() 方法得到该对象的 hashCode 值，然后根据 hashCode 值，通过某个散列函数决定该对象在 HashSet 底层数组中的存储位置。 • 第 2 步：如果要在数组中存储的位置上没有元素，则直接添加成功。 • 第 3 步：如果要在数组中存储的位置上有元素，则继续比较： – 如果两个元素的 hashCode 值不相等，则添加成功； – 如果两个元素的 hashCode()值相等，则会继续调用 equals()方法 • 如果 equals()方法结果为 false，则添加成功。 • 如果 equals()方法结果为 true，则添加失败。第 2 步添加成功，元素会保存在底层数组中。第 3 步两种添加成功的操作，由于该底层数组的位置已经有元素了，则会通过链表的方式继续链接，存储。

重写 hashCode() 方法的基本原则和重写 equals()方法的基本原则

在程序运行时，同一个对象多次调用 hashCode() 方法应该返回相同的值。 • 当两个对象的 equals() 方法比较返回 true 时，这两个对象的 hashCode() 方法的返回值也应相等。 • 对象中用作 equals() 方法比较的 Field，都应该用来计算 hashCode 值。注意：如果两个素的 equals() 方法返回 true，但它们的hashCode() 返回值不相等，hashSet 将会把它们存储在不同的位置，但依然可以添加成功。重写 equals 方法的时候一般都需要同时复写 hashCode 方法。通常参与计算hashCode 的对象的属性也应该参与到 equals()中进行计算。

LinkedHashSet 源码

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    // 构造函数
    public LinkedHashSet() {
        super(16, .75f, true); // 无参构造函数，默认初始容量为16
    }

    public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true); // 有参构造函数，可以指定初始容量
    }

    public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true); // 有参构造函数，可以指定初始容量和加载因子
    }

    public LinkedHashSet(Collection<? extends E> c) {
        super(Math.max(2*c.size(), 11), .75f, true); // 有参构造函数，可以指定一个集合，将集合中的元素添加到LinkedHashSet中
        addAll(c);
    }

}

        首先定义了一个父类HashSet，并重写了父类的构造函数。

        LinkedHashSet的构造函数有四种，

                一种是无参构造函数，默认初始容量为16；

                另一种是有参构造函数，可以指定初始容量；

                还有一种是有参构造函数，可以指定初始容量和加载因子；

                还有一种是有参构造函数，可以指定一个集合，将集合中的元素添加LinkedHashSet中。

        LinkedHashSet的add()、remove()和contains()方法都是调用父类HashSet的方法实现的。

        LinkedHashSet的size()方法用于获取集合的大小，toArray()方法用于将集合转换为数组等。需要注意的是，LinkedHashSet是有序的，因此可以按照插入的顺序访问元素。

LinkedHashSet 源码其他方法

size()：返回LinkedHashSet的大小，即元素的数量。
isEmpty()：判断LinkedHashSet是否为空。
clear()：清空LinkedHashSet中的所有元素。
containsAll(Collection<?> c)：判断LinkedHashSet中是否包含指定集合中的所有元素。
addAll(Collection<? extends E> c)：将指定集合中的所有元素添加到LinkedHashSet中。
removeAll(Collection<?> c)：删除LinkedHashSet中指定集合中的所有元素。
retainAll(Collection<?> c)：保留LinkedHashSet中指定集合中的所有元素，删除其他元素。
equals(Object o)：判断两个LinkedHashSet是否相等。
hashCode()：返回LinkedHashSet的哈希码。
toArray()：将LinkedHashSet转换为数组。
toArray(T[] a)：将LinkedHashSet转换为指定类型的数组。
iterator()：返回LinkedHashSet的Iterator对象，用于遍历LinkedHashSet中的元素。
spliterator()：返回LinkedHashSet的Spliterator对象，用于并行处理LinkedHashSet中的元素。
parallelStream()：返回LinkedHashSet的并行流，用于并行处理LinkedHashSet中的元素。

TreeSet 源码

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    // 用于存储元素的NavigableMap
    private transient NavigableMap<E,Object> m;

    // 构造函数
    public TreeSet() {
        this(new TreeMap<E,Object>()); // 无参构造函数，默认使用TreeMap作为NavigableMap
    }

    public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator)); // 有参构造函数，可以指定一个Comparator，用于比较元素的大小
    }

    public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c); // 有参构造函数，可以指定一个Collection，将Collection中的元素添加到TreeSet中
    }

    public TreeSet(SortedSet<E> s) {
        this(s.comparator());
        addAll(s); // 有参构造函数，可以指定一个SortedSet，将SortedSet中的元素添加到TreeSet中
    }

    // 添加元素
    public boolean add(E e) {
        return m.put(e, PRESENT)==null; // 添加元素，如果元素已经存在，则返回false，否则返回true
    }

    // 删除元素
    public boolean remove(Object o) {
        return m.remove(o)==PRESENT; // 删除元素，如果元素存在，则返回true，否则返回false
    }

    // 获取元素
    public boolean contains(Object o) {
        return m.containsKey(o); // 判断元素是否存在
    }

 
}

        首先定义了一个用于存储元素的NavigableMap m，以及一个默认的构造函数和两个有参构造函数。

        TreeSet的构造函数有四种，

                一种是无参构造函数，默认使用TreeMap作为NavigableMap；

                另一种是有参构造函数，可以指定一个Comparator，用于比较元素的大小；

                还有一种是有参构造函数，可以指定一个Collection，将Collection中的元素添加到TreeSet中；

                还有一种是有参构造函数，可以指定一个SortedSet，将SortedSet中的元素添加到TreeSet中。



         TreeSet的add()、remove()和contains()方法都是调用NavigableMap的方法实现的。

TreeSet还提供了其他一些方法，如size()方法用于获取集合的大小，toArray()方法用于将集合转换为数组等。需要注意的是，TreeSet是有序的，因此可以按照元素的大小顺序访问元素。

6.3Set中常用方法

添加元素：

boolean add(E e): 向集合中添加一个元素。如果集合不包含该元素，则返回true，否则返回false。

移除元素：

boolean remove(Object o): 从集合中移除指定元素。如果集合包含该元素，则返回true，否则返回false。

判断集合是否包含某个元素：

boolean contains(Object o): 判断集合是否包含指定元素。

清空集合：

void clear(): 移除集合中的所有元素。

获取集合的大小：

int size(): 返回集合中的元素个数。

判断集合是否为空：

boolean isEmpty(): 判断集合是否为空。

迭代集合中的元素：

Iterator<E> iterator(): 返回一个迭代器，用于遍历集合中的元素。

将集合转换为数组：

<T> T[] toArray(T[] a): 返回一个包含集合中所有元素的数组。

批量添加元素：

boolean addAll(Collection<? extends E> c): 将指定集合中的所有元素添加到该集合中。

批量移除元素：

boolean removeAll(Collection<?> c): 从该集合中移除指定集合中的所有元素。

保留集合中与指定集合的交集：

boolean retainAll(Collection<?> c): 仅保留该集合中与指定集合的交集元素。

检查集合是否与指定集合相等：

boolean equals(Object o): 如果指定对象与该集合相等，则返回true。

返回集合的哈希码值：

int hashCode(): 返回该集合的哈希码值。

6.4 Set中无序性、不可重复性的理解

>无序性： != 随机性。
添加元素的顺序和遍历元素的顺序不一致,不一定不是就是无序性
无序性：与添加的元素的位置有关，不像ArrayList一样是依次紧密排列的。
这里是根据添加的元素的哈希值，计算的其在数组中的存储位置。此位置不是依次排列的，表现为无序性。

>不可重复性：添加到Set中的元素是不能相同的。
比较的标准，需要判断hashCode()得到的哈希值以及equals()得到的boolean型的结果。
哈希值相同且equals()返回true，则认为元素是相同的。

6.5添加到HashSet/LinkedHashSet中元素的要求

要求元素所在的类要重写两个方法：equals() 和 hashCode()。
同时，要求equals() 和 hashCode()要保持一致性！

可以使用IDEA中自动生成两个方法的重写即可，即能保证两个方法的一致性。

6.6TreeSet的使用

6.61TreeSet底层的数据结构

红黑树

6.62添加数据后的特点

可以按照添加的元素的指定的属性的大小顺序进行遍历

6.63向TreeSet中添加的元素的要求

> 要求添加到TreeSet中的元素必须是同一个类型的对象，否则会报ClassCastException.
> 添加的元素需要考虑排序：① 自然排序 ② 定制排序

6.64判断数据是否相同的标准

        > 不再考虑hashCode()和equals()方法，意味着添加到TreeSet中的元素所在的类不需要重写hashCode()和equals()方法
        > 比较元素大小的或比较元素是否相等的标准就是考虑自然排序或定制排序中，compareTo()或compare()的返回值。
         如果compareTo()或compare()的返回值为0，则认为两个对象是相等的。由于TreeSet中不能存放相同的元素，则后一个相等的元素就不能添加到TreeSet中。

6.7代码案列

person类

public class Person {
    String name;
    int age;

    public Person() {
    }

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        System.out.println("Person equals()...");
        if (this == o) {return true;
        }
        if (o == null || getClass() != o.getClass()) return false;
            Person person = (Person) o;

        return age == person.age && Objects.equals(name, person.name);
    }

//    @Override
//    public int hashCode() {
//        return Objects.hash(name, age);
//    }

}

User类

 implements Comparable {
     private String name;
     private int age;

    public User() {
    }

    public User(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;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        User user = (User) o;
        return age == user.age && Objects.equals(name, user.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

    @Override
    public String toString() {
        return "User{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
    /*
     * 比如：按照年龄从小到大排序
     * */

//    @Override
//    public int compareTo(Object o) {
//        if(this == o){
//            return 0;
//        }
//
//        if (o instanceof User){
//            User u =(User)o;//强转
//            return this.age-u.age;
//        }
//
//        throw new RuntimeException("类型不匹配");
//    }

    /*
     * 比如：先比较年龄从小到大排列，如果年龄相同，则继续比较姓名，从大到小
     * */

    @Override
    public int compareTo(Object o) {
        if(this==o){
            return 0;
        }
        if (o instanceof User){
            User user =(User) o;
            int value =this.age-user.age;
            if (value !=0){
                return value;
            }
            return -this.name.compareTo(user.name);
        }
        throw new RuntimeException("类型不匹配");
    }
}

Set测试

public class SetText {
    @Test
    public void test1(){
        Set set = new HashSet();

        set.add("AA");
        set.add(123);
        set.add("BB");
        set.add(new Person("Tom",12));
        set.add(new Person("Tom",12));

        Iterator iterator = set.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }
        //结果
        //AA
        //BB
        //Person{name='Tom', age=12}
        //123
        System.out.println(set.contains(new Person("Tom", 12)));//false
    }

    @Test
    public void test2(){
        Set set = new LinkedHashSet();

        set.add("AA");
        set.add("AA");
        set.add(new Person("Tom",12));
        set.add(123);
        set.add("BB");

        Iterator iterator = set.iterator();
        while(iterator.hasNext()){
            System.out.println(iterator.next());
        }
            //结果
            //AA
            //Person{name='Tom', age=12}
            //123
            //BB
    }
}

TreeTest

package Exer4;

import org.junit.Test;

import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;

/**
 * packageName Exer4
 * 案例：
 * 定义方法如下：public static List duplicateList(List list)
 * 要求：① 参数List中只存放Integer的对象
 * ② 在List内去除重复数字值，尽量简单
 *
 * @author 曦
 * @version 1.0
 * @version0 JDK 17
 * @className TreeTest
 * @date 2024/11/5 18:51
 * @description TODO
 */
public class TreeTest {
    /*
     * 自然排序
     * */
    /*
     *@description TODO:
     *@description :TreeSet ：添加对象必须是同一类型
     * @param null:
     *@author 曦
     *@throws
     *@return {@link  @return: null}
     *@date 2024/11/5 18:59
     **/
    @Test
    public void test1() {
        TreeSet set = new TreeSet();

        set.add("cc");
        set.add("张军");
        set.add("sunjunxiang");
        set.add("fangronghua");
        //set.add(123);//报错，TreeSet添加对象必须是同一类型
        set.add("123");

        Iterator iterator = set.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }

    }

    /*
     * 自然排序
     * */
    @Test
    public void test2() {
        TreeSet set = new TreeSet();

        User user1 = new User("Tom", 19);
        User user2 = new User("张军", 18);
        User user3 = new User("孙俊祥", 18);
        User user4 = new User("Simi", 999);
        User user5 = new User("李小龙", 19);

        set.add(user1);
        set.add(user2);
        set.add(user3);
        set.add(user4);
        set.add(user5);

        Iterator iterator = set.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }

    /*
     * 定制排序
     * */
    @Test
    public void test3() {
        Comparator comparator = new Comparator() {
            /*
             * 按照姓名从小到大排列，如果姓名相同，继续比较age，按照从大到小排列
             * */
            @Override
            public int compare(Object o1, Object o2) {
                if (o1 instanceof User && o2 instanceof User) {
                    User u1 = (User) o1;
                    User u2 = (User) o2;

                    int value = u1.getName().compareTo(u2.getName());
                    if (value != 0) {
                        return value;
                    }
                    return -(u1.getAge() - u2.getAge());
                }
                throw new RuntimeException("类型不匹配");
            }
        };
        TreeSet set = new TreeSet();
        User user1 = new User("Tom", 19);
        User user2 = new User("张军", 18);
        User user3 = new User("孙俊祥", 18);
        User user4 = new User("Simi", 999);
        User user5 = new User("李小龙", 19);


        set.add(user1);
        set.add(user2);
        set.add(user3);
        set.add(user4);
        set.add(user5);

        Iterator iterator = set.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}

七.Map接口及实现类的使用

7.1Map 接口概述

• Map 与 Collection 并列存在。用于保存具有映射关系的数据：key-value – Collection 集合称为单列集合，元素是孤立存在的（理解为单身）。 – Map 集合称为双列集合，元素是成对存在的(理解为夫妻)。 • Map 中的 key 和 value 都可以是任何引用类型的数据。但常用 String 类作为 Map的“键”。 • Map 接口的常用实现类：HashMap、 LinkedHashMap 、 TreeMap 和 Properties 。其中，HashMap 是 Map 接口使用 频率最高 的实现类。

7.2Map 中 key-value 特点

• Map 中的 key 用 Set 来存放，不允许重复 ，即同一个 Map 对象所对应的类，须重写 hashCode()和 equals()方法 • key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到唯一的、确定的value，不同 key 对应的 value 可以重复。value 所在的类要重写 equals()方法。 • key 和 value 构成一个 entry。所有的 entry 彼此之间是无序的、不可重复的。

7.3Map 接口的常用方法

添加键值对：

V put(K key, V value): 将指定的值与此映射中的指定键关联。如果映射以前包含一个该键的映射关系，则旧值被替换。

获取指定键的值：

V get(Object key): 返回到指定键所映射的值，或null如果此映射包含该键的映射关系。

移除指定键的映射关系：

V remove(Object key): 如果存在一个键的映射关系，则将其从此映射中移除。

判断是否包含指定键：

boolean containsKey(Object key): 如果此映射包含指定键的映射关系，则返回true。

判断是否包含指定值：

boolean containsValue(Object value): 如果此映射将一个或多个键映射到指定值，则返回true。

获取所有键的集合：

Set<K> keySet(): 返回此映射中包含的键的Set视图。

获取所有值的集合：

Collection<V> values(): 返回此映射中包含的值的Collection视图。

获取所有键值对的集合：

Set<Map.Entry<K, V>> entrySet(): 返回此映射中包含的映射关系的Set视图。

清空映射：

void clear(): 从此映射中移除所有映射关系。

获取映射的大小：

int size(): 返回此映射中的键-值映射关系数。

判断映射是否为空：

boolean isEmpty(): 如果此映射未包含键-值映射关系，则返回true。

检查映射是否与指定映射相等：

boolean equals(Object o): 如果指定对象也是一个映射，且两个映射表示相同的映射关系，则返回true。

返回映射的哈希码值：

int hashCode(): 返回此映射的哈希码值。

Map中的常用方法
- 添加、修改操作：
          - Object put(Object key,Object value)：将指定key-value添加到(或修改)当前map对象中
          - void putAll(Map m):将m中的所有key-value对存放到当前map中
- 删除操作：
          - Object remove(Object key)：移除指定key的key-value对，并返回value
          - void clear()：清空当前map中的所有数据
- 元素查询的操作：
          - Object get(Object key)：获取指定key对应的value
          - boolean containsKey(Object key)：是否包含指定的key
          - boolean containsValue(Object value)：是否包含指定的value
          - int size()：返回map中key-value对的个数
          - boolean isEmpty()：判断当前map是否为空
          - boolean equals(Object obj)：判断当前map和参数对象obj是否相等
- 元视图操作的方法：
          - Set keySet()：返回所有key构成的Set集合
          - Collection values()：返回所有value构成的Collection集合
          - Set entrySet()：返回所有key-value对构成的Set集合

小结：
增：
put(Object key,Object value)
putAll(Map m)
删：
Object remove(Object key)
改：
put(Object key,Object value)
putAll(Map m)
查：
Object get(Object key)
长度：
size()
遍历：
遍历key集：Set keySet()
遍历value集：Collection values()
遍历entry集：Set entrySet()

7.4 Map及其实现类对比

java.util.Map:存储一对一对的数据(key-value键值对，(x1,y1)、(x2,y2) --> y=f(x),类似于高中的函数)
|---- HashMap:主要实现类;线程不安全的，效率高;可以添加null的key和value值;底层使用数组+单向链表+红黑树结构存储（jdk8）
|---- LinkedHashMap:是HashMap的子类；在HashMap使用的数据结构的基础上，增加了一对双向链表，用于记录添加的元素的先后顺序，
进而我们在遍历元素时，就可以按照添加的顺序显示。
开发中，对于频繁的遍历操作，建议使用此类。
|---- TreeMap:底层使用红黑树存储;可以按照添加的key-value中的key元素的指定的属性的大小顺序进行遍历。需要考虑使用①自然排序 ②定制排序。
|---- Hashtable:古老实现类;线程安全的，效率低;不可以添加null的key或value值;底层使用数组+单向链表结构存储（jdk8）
|---- Properties:其key和value都是String类型。常用来处理属性文件。

7.41 Map 接口分析

7.41.1哈希表的物理结构

HashMap 和 Hashtable 底层都是哈希表（也称散列表），其中维护了一个长度为 2 的幂次方 的 Entry 类型的数组 table，数组的每一个索引位置被称为一个桶(bucket)，你添加的映射关系(key,value)最终都被封装为一个 Map.Entry 类型的对象，放到某个 table[index]中。使用数组的目的是查询和添加的效率高，可以根据索引直接定位到某个table[index]。

7.41.2HashMap中元素的特点

> HashMap中的所有的key彼此之间是不可重复的、无序的。所有的key就构成一个Set集合。--->key所在的类要重写hashCode()和equals()

> HashMap中的所有的value彼此之间是可重复的、无序的。所有的value就构成一个Collection集合。--->value所在的类要重写equals()

> HashMap中的一个key-value,就构成了一个entry。

> HashMap中的所有的entry彼此之间是不可重复的、无序的。所有的entry就构成了一个Set集合。

HashMap结构图

JDK1.7

JDK1.8

HashMap源码

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
    private static final long serialVersionUID = 362498820763181265L;

    // 默认初始容量
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    // 最大容量
    static final int MAXIMUM_CAPACITY = 1 << 30;

    // 默认加载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    // 转换为红黑树的阈值
    static final int TREEIFY_THRESHOLD = 8;

    // 从红黑树转换为链表的阈值
    static final int UNTREEIFY_THRESHOLD = 6;

    // 最小树形化容量阈值
    static final int MIN_TREEIFY_CAPACITY = 64;

    // 存储元素的数组
    transient Node<K,V>[] table;

    // HashMap中实际存储的键值对数量
    transient int size;

    // HashMap结构被修改的次数
    transient int modCount;

    // 临界值，当实际存储的键值对数量超过临界值时，会进行扩容
    int threshold;

    // 加载因子
    final float loadFactor;

    // 链表节点
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

    // 红黑树节点
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // 父节点
        TreeNode<K,V> left;    // 左子节点
        TreeNode<K,V> right;   // 右子节点
        TreeNode<K,V> prev;    // 前一个节点
        boolean red;           // 颜色

        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

        // 省略其他方法...
    }

    // 构造方法
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

}

JDK7中的HashMap的源码

实例化过程

HashMap<String,Integer> map = new HashMap<>();

应的源码

public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

public HashMap(int initialCapacity, float loadFactor) {
   

    //通过此循环，得到capacity的最终值，此最终值决定了Entry数组的长度。此时的capacity一定是2的整数倍
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;

    this.loadFactor = loadFactor; //确定了加载因子的值
    threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);  //确定了临界值
    table = new Entry[capacity]; //初始化数组，长度为capacity

其中

static final int DEFAULT_INITIAL_CAPACITY = 16;
static final float DEFAULT_LOAD_FACTOR = 0.75f;

final float loadFactor; //加载因子
int threshold;//临界值
transient Entry<K,V>[] table; //存储数组的数组

put(key,value)的过程

public V put(K key, V value) {
    //HashMap允许添加key为null的值。将此(key,value)存放到table索引0的位置。
    if (key == null)
        return putForNullKey(value);
    //将key传入hash()，内部使用了key的哈希值1，此方法执行结束后，返回哈希值2
    int hash = hash(key);
    //确定当前key，value在数组中的存放位置i
    int i = indexFor(hash, table.length);
    
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;  //如果put是修改操作，会返回原有旧的value值。
        }
    }

    //.....
    addEntry(hash, key, value, i); //将key,value封装为一个Entry对象，并将此对象保存在索引i位置。
    return null; //如果put是添加操作，会返回null.
}

其中

final int hash(Object k) {
    int h = 0;
    if (useAltHashing) {
        if (k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
        h = hashSeed;
    }

    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

static int indexFor(int h, int length) {
    return h & (length-1);
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    //扩容的条件
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length); //默认扩容为原有容量的2倍
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }

    createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

Entry的定义

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;  //使用key得到的哈希值2进行赋值。

    /**
         * Creates new entry.
         */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
}

HashMap使用哈希表（数组+链表+红黑树）来实现，其中Node类表示链表节点，TreeNode类表示红黑树节点。

HashMap的构造方法允许指定初始容量和加载因子，put方法用于添加键值对，get方法用于获取指定键的值，remove方法用于移除指定键的映射关系，size方法用于获取HashMap中的元素数量，clear方法用于清空HashMap。

HashMap jdk7中创建对象和添加数据过程

//创建对象的过程中，底层会初始化数组Entry[] table = new Entry[16];
HashMap<String,Integer> map = new HashMap<>();
...
map.put("AA",78); //"AA"和78封装到一个Entry对象中，考虑将此对象添加到table数组中。
...

添加/修改的过程：
将(key1,value1)添加到当前的map中：
        首先，需要调用key1所在类的hashCode()方法，计算key1对应的哈希值1，此哈希值1经过某种算法(hash())之后，得到哈希值2。
        哈希值2再经过某种算法(indexFor())之后，就确定了(key1,value1)在数组table中的索引位置i。
1.1 如果此索引位置i的数组上没有元素，则(key1,value1)添加成功。 ---->情况1
1.2 如果此索引位置i的数组上有元素(key2,value2),则需要继续比较key1和key2的哈希值2 --->哈希冲突
2.1 如果key1的哈希值2与key2的哈希值2不相同，则(key1,value1)添加成功。 ---->情况2
2.2 如果key1的哈希值2与key2的哈希值2相同，则需要继续比较key1和key2的equals()。要调用key1所在类的equals(),将key2作为参数传递进去。
3.1 调用equals()，返回false: 则(key1,value1)添加成功。 ---->情况3
3.2 调用equals()，返回true: 则认为key1和key2是相同的。默认情况下，value1替换原有的value2。

说明：情况1：将(key1,value1)存放到数组的索引i的位置
情况2,情况3：(key1,value1)元素与现有的(key2,value2)构成单向链表结构，(key1,value1)指向(key2,value2)

随着不断的添加元素，在满足如下的条件的情况下，会考虑扩容：
(size >= threshold) && (null != table[i])

        当元素的个数达到临界值(-> 数组的长度 * 加载因子)时，就考虑扩容。默认的临界值 = 16 * 0.75 --> 12.

        默认扩容为原来的2倍。

HashMap jdk8中创建对象和添加数据过程

① 在jdk8中，当我们创建了HashMap实例以后，底层并没有初始化table数组。当首次添加(key,value)时，进行判断，
如果发现table尚未初始化，则对数组进行初始化。
② 在jdk8中，HashMap底层定义了Node内部类，替换jdk7中的Entry内部类。意味着，我们创建的数组是Node[]
③ 在jdk8中，如果当前的(key,value)经过一系列判断之后，可以添加到当前的数组角标i中。如果此时角标i位置上有
元素。在jdk7中是将新的(key,value)指向已有的旧的元素（头插法），而在jdk8中是旧的元素指向新的
(key,value)元素（尾插法）。 "七上八下"
④ jdk7:数组+单向链表
jk8:数组+单向链表 + 红黑树
什么时候会使用单向链表变为红黑树：如果数组索引i位置上的元素的个数达到8，并且数组的长度达到64时，我们就将此索引i位置上的多个元素改为使用红黑树的结构进行存储。（为什么修改呢？红黑树进行put()/get()/remove()操作的时间复杂度为O(logn)，比单向链表的时间复杂度O(n)的好。性能更高。
什么时候会使用红黑树变为单向链表：当使用红黑树的索引i位置上的元素的个数低于6的时候，就会将红黑树结构退化为单向链表。

HashMap属性/字段：

        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认的初始容量 16

        static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量 1 << 30

        static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认加载因子

        static final int TREEIFY_THRESHOLD = 8; //默认树化阈值8，当链表的长度达到这个值后，要考虑树化

        static final int UNTREEIFY_THRESHOLD = 6;//默认反树化阈值6，当树中结点的个数达到此阈值后，要考虑变为链表

        //当单个的链表的结点个数达到8，并且table的长度达到64，才会树化。

        //当单个的链表的结点个数达到8，但是table的长度未达到64，会先扩容

        static final int MIN_TREEIFY_CAPACITY = 64; //最小树化容量64

        transient Node<K,V>[] table; //数组

        transient int size; //记录有效映射关系的对数，也是Entry对象的个数

        int threshold; //阈值，当size达到阈值时，考虑扩容

        final float loadFactor; //加载因子，影响扩容的频率

LinkedHashMap结构图

LinkedHashMap源码

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V> {
    private static final long serialVersionUID = 3801124242820219131L;

    // 双向链表的头节点
    transient LinkedHashMap.Entry<K,V> head;

    // 双向链表的尾节点
    transient LinkedHashMap.Entry<K,V> tail;

    // 是否按访问顺序排序
    final boolean accessOrder;

    // 链表节点
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;

        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }

    }

    // 构造方法
    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
}

LinkedHashMap继承自HashMap，并添加了一个双向链表来维护元素的插入顺序或访问顺序。

LinkedHashMap的构造方法允许指定初始容量、加载因子和是否按访问顺序排序，put方法用于添加键值对，get方法用于获取指定键的值，remove方法用于移除指定键的映射关系，size方法用于获取LinkedHashMap中的元素数量，clear方法用于清空LinkedHashMap

LinkedHashMap 与 HashMap 的关系

> LinkedHashMap 是 HashMap的子类。
> LinkedHashMap在HashMap使用的数组+单向链表+红黑树的基础上，又增加了一对双向链表，记录添加的(key,value)的先后顺序。便于我们遍历所有的key-value。

LinkedHashMap重写了HashMap的如下方法：
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}

底层结构：LinkedHashMap内部定义了一个Entry

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after; //增加的一对双向链表
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

HashSet和LinkedHashSet的源码分析

HashSet的基本结构和一些常用方法。HashSet使用HashMap来实现，其中HashMap的键是集合中的元素，值是一个哨兵值PRESENT。HashSet的构造方法允许指定一个初始容量，add方法用于添加元素，remove方法用于移除元素，contains方法用于判断是否包含指定元素，size方法用于获取HashSet中的元素数量，clear方法用于清空HashSet

LinkedHashSet继承自HashSet，并添加了一个双向链表来维护元素的插入顺序。LinkedHashSet的构造方法允许指定初始容量和加载因子，add方法用于添加元素，remove方法用于移除元素，contains方法用于判断是否包含指定元素，size方法用于获取LinkedHashSet中的元素数量，clear方法用于清空LinkedHashSet

总结：

> HashSet底层使用的是HashMap > LinkedHashSet底层使用的是LinkedHashMap

7.5区别HashMap和Hashtable、区别HashMap和LinkedHashMap、HashMap的底层实现

HashMap和Hashtable的区别：

线程安全性：HashMap是非同步的，不是线程安全的。如果多个线程同时访问一个HashMap，而其中至少一个线程修改了该映射，则必须手动同步。Hashtable是同步的，是线程安全的。

Null值：HashMap允许一个null键和多个null值。Hashtable不允许任何null键或值。

性能：由于Hashtable的同步性，它在单线程环境下性能较低，而HashMap在单线程环境下性能较高。

HashMap和LinkedHashMap的区别：

顺序：HashMap不保证元素的顺序。LinkedHashMap维护一个双向链表，可以保持元素的插入顺序或访问顺序。

性能：由于LinkedHashMap维护了一个双向链表，它在插入和删除操作上比HashMap稍慢，但在遍历访问时更快。

HashMap的底层实现：（① new HashMap() ② put(key,value)）

HashMap的底层实现是使用哈希表（数组+链表+红黑树）。哈希表是一个数组，数组的每个元素是一个链表的头节点。当插入一个元素时，首先计算其哈希值，然后根据哈希值找到对应的数组位置，如果该位置已经有元素，则将新元素插入到链表的末尾。如果链表的长度超过了阈值（默认为8），则将链表转换为红黑树以提高查找性能。当删除一个元素时，首先计算其哈希值，然后根据哈希值找到对应的数组位置，如果该位置有元素，则从链表或红黑树中删除该元素。当访问一个元素时，首先计算其哈希值，然后根据哈希值找到对应的数组位置，如果该位置有元素，则从链表或红黑树中查找该元素。

LinkedHashMap的底层实现：

LinkedHashMap是HashMap的一个子类，它在HashMap的基础上增加了一个双向链表，用于维护元素的插入顺序或访问顺序。链表的节点中除了存储键值对，还存储了指向前一个和后一个节点的引用。当插入一个元素时，除了在哈希表中插入，还会在链表中插入一个新节点。当访问一个元素时，除了在哈希表中查找，还会更新链表中的节点顺序，将访问的节点移动到链表的末尾。当删除一个元素时，除了在哈希表中删除，还会在链表中删除对应的节点。

        HashMap:线程不安全的,可以添加null的key和value值;底层使用数组+单向链表+红黑树结构存储
        Hashtable:线程安全的,不可以添加null的key或value值;底层使用数组+单向链表结构存储

        HashMap:底层使用数组+单向链表+红黑树结构存储
        LinkedHashMap:增加了一对双向链表，用于记录添加的元素的先后顺序，

7.6HashMap中元素的特点

键值对：HashMap中的每个元素都是一个键值对，键和值可以是任意类型的对象。

键的唯一性：在HashMap中，每个键都是唯一的，不能有重复的键。

值的可重复性：HashMap中的值可以重复，可以有多个键映射到同一个值。

无序性：HashMap不保证元素的顺序，即元素的迭代顺序可能与插入顺序不同。

允许null键和null值：HashMap允许一个null键和多个null值。

基于哈希表：HashMap的底层实现是哈希表，它使用哈希函数将键映射到哈希表的索引位置，从而实现快速的查找、插入和删除操作。

线程不安全：HashMap不是线程安全的，如果多个线程同时访问一个HashMa

    HashMap中的所有的key彼此之间是不可重复的、无序的。所有的key就构成一个Set集合。--->key所在的类要重写hashCode()和equals()

HashMap中的所有的value彼此之间是可重复的、无序的。所有的value就构成一个Collection集合。--->value所在的类要重写equals()

    HashMap中的一个key-value,就构成了一个entry。

    HashMap中的所有的entry彼此之间是不可重复的、无序的。所有的entry就构成了一个Set集合。

7.7TreeMap的使用

> 底层使用红黑树存储;

> 可以按照添加的key-value中的key元素的指定的属性的大小顺序进行遍历。

> 需要考虑使用①自然排序 ②定制排序。

> 要求:向TreeMap中添加的key必须是同一个类型的对象。

7.8Hashtable与Properties的使用

Hashtable实现了Map接口，表示一个键值对的集合。Hashtable中的元素按照键的自然顺序进行排序，或者根据创建Hashtable时提供的Comparator进行排序。

添加键值对：

Object put(Object key, Object value): 将指定的值与此映射中的指定键关联。如果映射以前包含一个该键的映射关系，则旧值被替换。

获取指定键的值：

Object get(Object key): 返回到指定键所映射的值，或null如果此映射包含该键的映射关系。

移除指定键的映射关系：

Object remove(Object key): 如果存在一个键的映射关系，则将其从此映射中移除。

判断是否包含指定键：

boolean containsKey(Object key): 如果此映射包含指定键的映射关系，则返回true。

判断是否包含指定值：

boolean containsValue(Object value): 如果此映射将一个或多个键映射到指定值，则返回true。

获取所有键的集合：

Set<Object> keySet(): 返回此映射中包含的键的Set视图。

获取所有值的集合：

Collection<Object> values(): 返回此映射中包含的值的Collection视图。

获取所有键值对的集合：

Set<Map.Entry<Object, Object>> entrySet(): 返回此映射中包含的映射关系的Set视图。

清空映射：

void clear(): 从此映射中移除所有映射关系。

获取映射的大小：

int size(): 返回此映射中的键-值映射关系数。

判断映射是否为空：

boolean isEmpty(): 如果此映射未包含键-值映射关系，则返回true。

检查映射是否与指定映射相等：

boolean equals(Object o): 如果指定对象也是一个映射，且两个映射表示相同的映射关系，则返回true。

返回映射的哈希码值：

int hashCode(): 返回此映射的哈希码值。

Properties：

Properties是Hashtable的子类，它表示一个持久的属性集，属性列表中每个键及其对应值都是一个字符串。下面是一些常用的Properties方法：

加载属性文件：

void load(InputStream inStream): 从输入流中读取属性列表（键和元素对）。

保存属性文件：

void store(OutputStream out, String comments): 将此属性列表（键和元素对）写入输出流。

获取属性值：

String getProperty(String key): 用指定的键在此属性列表中搜索属性。

获取属性值，如果找不到则返回默认值：

String getProperty(String key, String defaultValue): 用指定的键在此属性列表中搜索属性。

设置属性值：

Object setProperty(String key, String value): 调用Hashtable的put方法来设置属性。

获取所有属性键的集合：

Set<String> stringPropertyNames(): 返回此属性列表中的键集，其中键和元素都是字符串。

总结：Properties:是Hashtable的子类，其key和value都是String类型的，常用来处理属性文件。

7.9代码案列

Person类

public class Person {
    String name;
    int age;

    public Person() {
    }

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return age == person.age && Objects.equals(name, person.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

User类

public class User implements Comparable {
     private String name;
     private int age;

    public User() {
    }

    public User(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;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        User user = (User) o;
        return age == user.age && Objects.equals(name, user.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

    @Override
    public String toString() {
        return "User{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
    /*
     * 比如：按照年龄从小到大排序
     * */

//    @Override
//    public int compareTo(Object o) {
//        if(this == o){
//            return 0;
//        }
//
//        if (o instanceof User){
//            User u =(User)o;//强转
//            return this.age-u.age;
//        }
//
//        throw new RuntimeException("类型不匹配");
//    }

    /*
     * 比如：先比较年龄从小到大排列，如果年龄相同，则继续比较姓名，从大到小
     * */

    @Override
    public int compareTo(Object o) {
        if(this==o){
            return 0;
        }
        if (o instanceof User){
            User user =(User) o;
            int value =this.age-user.age;
            if (value !=0){
                return value;
            }
            return -this.name.compareTo(user.name);
        }
        throw new RuntimeException("类型不匹配");
    }
}

MapTest类

public class MapTest {
    @Test
    public void test1() {
        Map map = new HashMap();

        map.put(null, null);
        System.out.println(map);
    }

    @Test
    public void test2() {
        Map map = new Hashtable();

//        map.put(null,123);//空指针异常
        map.put("AA", null);//空指针异常
        System.out.println(map);
    }

    @Test
    public void test3() {
        LinkedHashMap map = new LinkedHashMap();
        map.put("Tom", 23);
        map.put(34, 23);
        map.put("CC", new Date());
        System.out.println(map);
    }

    /*
     增：
        put(Object key,Object value)
        putAll(Map m)
    删：
        Object remove(Object key)
    改：
        put(Object key,Object value)
        putAll(Map m)
    查：
        Object get(Object key)
    长度：
        size()
    遍历：
       遍历key集：Set keySet()
       遍历value集：Collection values()
       遍历entry集：Set entrySet()
       */
    @Test
    public void test4() {
        //增加
        HashMap map = new HashMap();
        map.put("AA", 56);
        map.put("Tom", 23);
        map.put(33, "SIMI");
        map.put("BB", 23);
        map.put(new Person("Tom", 12), 67);

        System.out.println(map);

        //size
        System.out.println(map.size());//4

        //Object get(Object key)
        Object value = map.remove("BB");//23
        System.out.println(value);//23

        System.out.println(map);//没有BB了

//        修改：
//        put(Object key,Object value)
        Object oldValuemap = map.put("AA", 99);
        System.out.println(oldValuemap);//56 查看原来的值
        System.out.println(map);//AA修改为99

        //get(Object key)
        Object value3 = map.get(33);
        System.out.println(value3);
    }

    //map遍历操作
    //遍历：
    //       遍历key集：Set keySet()
    //       遍历value集：Collection values()
    //       遍历entry集：Set entrySet()
    //       */
    @Test
    public void test5() {
        //遍历key集；Set keySet()
        HashMap map = new HashMap();
        map.put("AA", 56);
        map.put("Tom", 23);
        map.put(33, "SIMI");
        map.put("BB", 23);
        map.put("Tom", 67);

        Set keySet = map.keySet();
        Iterator value = keySet.iterator();

        //方法1 使用迭代器
        while (value.hasNext()) {
            System.out.println(value.next());
        }

        System.out.println("**********************");

        //方法2：使用增强for
        for (Object obj : keySet) {
            System.out.println(obj);
        }

        //遍历value集：Collection values()
        Collection values = map.values();

        System.out.println("**********************");
        //方法1 使用迭代器
        Iterator iterator = values.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
        System.out.println("**********************");

        //方法2：使用增强for
        for (Object o : values) {
            System.out.println(o);
        }
        System.out.println("**********************");

        Set keySet1 = map.keySet();
        for (Object key : keySet1) {
//            Object value1 =map.get(key);
            System.out.println(map.get(key));
        }

    }

    @Test
    public void test6() {
        HashMap map = new HashMap();
        map.put("AA", 56);
        map.put("Tom", 23);
        map.put(33, "SIMI");
        map.put("BB", 23);
        map.put(new Person("Tom", 12), 67);

        //方式1
        //遍历entry集：Set entrySet()
        Set entrySet = map.entrySet();
        Iterator iterator = entrySet.iterator();
        while (iterator.hasNext()) {
            //方法1
            System.out.println(iterator.next());

            //方法2
//            Map.Entry entry=(Map.Entry)iterator.next();
//            System.out.println(entry.getKey()+"------>"+entry.getValue());


        }

        //方式2：遍历entry集：keySet().get(key)
        Set keySet1 = map.keySet();
        for (Object key:keySet1){
            System.out.println(key+"---->"+map.get(key));
        }
    }
}

PropertiesTest类

public class PropertiesTest {

    //方式1：数据和代码耦合度高；如果修改的话，需要重写的编译代码、打包发布，繁琐
    @Test
    public void test() throws IOException { //注意：因为设计到流的操作，为了确保流能关闭，建议使用try-catch-finally
        //方式1：数据和代码耦合度高；如果修改的话，需要重写的编译代码、打包发布，繁琐
        //数据
//        String name = "Tom";
//        String password = "abc123";

        //代码：用于操作name,password
        //...

        //方式2：将数据封装到具体的配置文件中，在程序中读取配置文件中的信息。实现了
        //数据和代码的解耦；由于我们没有修改代码，就省去了重新编译和打包的过程。
        File file = new File("info.properties"); //注意，要提前创建好
//        System.out.println(file.getAbsolutePath());
        FileInputStream fis = new FileInputStream(file);

        Properties pros = new Properties();
        pros.load(fis); //加载流中的文件中的数据

        //读取数据
        String name = pros.getProperty("name");
        String pwd = pros.getProperty("password");

        System.out.println(name + ":" + pwd);

        fis.close();
    }
    //    public static void main(String[] args) {
//        File file =new File("info.properties");
//        System.out.println(file.getAbsoluteFile());
}

TreeMapTest类

public class TreeMapTest {

    @Test
    public void test1(){
        TreeMap map = new TreeMap();
        map.put("CC",89);
        map.put("BB",78);
        map.put("JJ",65);
        map.put("WW",78);

//        map.put(67,78);//报错。因为key的类型（Integer)与之前的key的类型（String）不一致
        //自然排序
        Set entrySet =map.entrySet();
        for (Object entry:entrySet){
            System.out.println(entry);
        }
    }
    @Test
    public void test2(){
        TreeMap map = new TreeMap();
        User u1 = new User("Tom",23);
        User u2 = new User("Jerry",43);
        User u3 = new User("Rose",13);
        User u4 = new User("Jack",23);
        User u5 = new User("Tony",33);

        map.put(u1,78);
        map.put(u2,76);
        map.put(u3,88);
        map.put(u4,45);
        map.put(u5,99);


        Set entrySet =map.entrySet();
        for (Object entry:entrySet){
            System.out.println(entry);
        }
    }

    /*
     * 定制排序
     * */
    @Test
    public void test3() {
        Comparator comparator = new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                if (o1 instanceof User && o2 instanceof User) {
                    User u1 = (User) o1;
                    User u2 = (User) o2;

                    int value = u1.getName().compareTo(u2.getName());
                    if (value != 0) {
                        return value;
                    }
                    return -(u1.getAge() - u2.getAge());
                }
                throw new RuntimeException("类型不匹配");
            }


        };
        TreeMap map = new TreeMap(comparator);
        User u1 = new User("Tom", 23);
        User u2 = new User("Jerry", 43);
        User u3 = new User("Rose", 13);
        User u4 = new User("Jack", 23);
        User u5 = new User("Tony", 33);

        map.put(u1, 78);
        map.put(u2, 76);
        map.put(u3, 88);
        map.put(u4, 45);
        map.put(u5, 99);

        Set entrySet = map.entrySet();
        for (Object entry : entrySet) {
            System.out.println(entry);
        }
    }
}

八. Collections工具类的使用

Arrays，Collections 是一个操作 Set、List 和 Map 等集合的工具类。

8.1常用方法

排序操作：

        - reverse(List)：反转 List 中元素的顺序
        - shuffle(List)：对 List 集合元素进行随机排序
        - sort(List)：根据元素的自然顺序对指定 List 集合元素按升序排序
        - sort(List，Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
        - swap(List，int， int)：将指定 list 集合中的 i 处元素和 j 处元素进行交换

查找

        - Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素
        - Object max(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最大元素
        - Object min(Collection)：根据元素的自然顺序，返回给定集合中的最小元素
        - Object min(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最小元素
        - int binarySearch(List list,T key)在List集合中查找某个元素的下标，但是List的元素必须是T或T的子类对象，而且必须是可比较大小的，即支持自然排序的。而且集合也事先必须是有序的，否则结果不确定。
        - int binarySearch(List list,T key,Comparator c)在List集合中查找某个元素的下标，但是List的元素必须是T或T的子类对象，而且集合也事先必须是按照c比较器规则进行排序过的，否则结果不确定。
        - int frequency(Collection c，Object o)：返回指定集合中指定元素的出现次数

复制、替换

        - void copy(List dest,List src)：将src中的内容复制到dest中
        - boolean replaceAll(List list，Object oldVal，Object newVal)：使用新值替换 List 对象的所有旧值
        - 提供了多个unmodifiableXxx()方法，该方法返回指定 Xxx的不可修改的视图。

添加

        - boolean addAll(Collection c,T... elements)将所有指定元素添加到指定 collection 中。

同步

        - Collections 类中提供了多个 synchronizedXxx() 方法，该方法可使将指定集合包装成线程同步的集合，从而可以解决多线程并发访问集合时的线程安全问题

排序：

static <T extends Comparable<? super T>> void sort(List<T> list): 根据元素的自然顺序对指定列表进行升序排序。

反转：

static void reverse(List<?> list): 反转指定列表中元素的顺序。

洗牌：

static void shuffle(List<?> list): 使用默认的随机源对指定列表进行随机排序。

查找：

static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key): 使用二分搜索法搜索指定列表，以获得指定对象。

替换：

static void fill(List<? super T> list, T obj): 用指定的元素替换指定列表中的所有元素。

复制：

static <T> void copy(List<? super T> dest, List<? extends T> src): 将指定列表中的所有元素复制到目标列表中。

旋转：

static void rotate(List<?> list, int distance): 根据指定的距离旋转指定列表中的元素。

反转：

static void swap(List<?> list, int i, int j): 交换指定列表中指定位置的元素。

同步：

static <T> List<T> synchronizedList(List<T> list): 返回指定列表支持的同步（线程安全的）列表。

不可变：

static <T> List<T> unmodifiableList(List<? extends T> list): 返回指定列表支持的不可修改列表。

空列表：

static <T> List<T> emptyList(): 返回一个空的不可变列表。

单元素列表：

static <T> List<T> singletonList(T o): 返回一个只包含指定对象的不可变列表。

最大值和最小值：

static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll): 根据元素的自然顺序返回给定集合的最大元素。

最小值：

static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll): 根据元素的自然顺序返回给定集合的最小元素。

8.2代码案列

package Exer6;

import org.junit.Test;

import java.util.*;

public class CollectionsTest {
    /*
    * 排序操作：
        - reverse(List)：反转 List 中元素的顺序
        - shuffle(List)：对 List 集合元素进行随机排序
        - sort(List)：根据元素的自然顺序对指定 List 集合元素按升序排序
        - sort(List，Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
        - swap(List，int， int)：将指定 list 集合中的 i 处元素和 j 处元素进行交换
    * */
    @Test
    public void test1(){
        List list = Arrays.asList(45, 43, 65, 6, 43, 2, 32, 45, 56, 34, 23);
        System.out.println(list);
        //reverse(List)：反转 List 中元素的顺序
        Collections.reverse(list);

        //shuffle(List)：对 List 集合元素进行随机排序
        Collections.shuffle(list);

        //sort(List)：根据元素的自然顺序对指定 List 集合元素按升序排序
        Collections.sort(list);

        //sort(List，Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
        Collections.sort(list, new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                if(o1 instanceof Integer && o2 instanceof Integer){
                    Integer i1 = (Integer) o1;
                    Integer i2 = (Integer) o2;

//                    return i1 - i2;
                    return -(i1.intValue() - i2.intValue());
                }
                throw new RuntimeException("类型不匹配");
            }
        });
        System.out.println(list);
    }

    /*
    * 查找
    - Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素
    - Object max(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最大元素
    - Object min(Collection)：根据元素的自然顺序，返回给定集合中的最小元素
    - Object min(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最小元素
    - int binarySearch(List list,T key)在List集合中查找某个元素的下标，但是List的元素必须是T或T的子类对象，而且必须是可比较大小的，即支持自然排序的。而且集合也事先必须是有序的，否则结果不确定。
    - int binarySearch(List list,T key,Comparator c)在List集合中查找某个元素的下标，但是List的元素必须是T或T的子类对象，而且集合也事先必须是按照c比较器规则进行排序过的，否则结果不确定。
    - int frequency(Collection c，Object o)：返回指定集合中指定元素的出现次数
    *
    * */

    @Test
    public void test2(){
        List list = Arrays.asList(45, 43, 65, 6, 43, 2, 32, 45, 56, 34, 23);
        System.out.println(list);

        Object max = Collections.max(list);


        Object max1 = Collections.max(list,new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                if(o1 instanceof Integer && o2 instanceof Integer){
                    Integer i1 = (Integer) o1;
                    Integer i2 = (Integer) o2;

//                    return i1 - i2;
                    return -(i1.intValue() - i2.intValue());
                }
                throw new RuntimeException("类型不匹配");
            }
        });

        System.out.println(max);
        System.out.println(max1);

        int count = Collections.frequency(list, 45);
        System.out.println("45出现了" + count + "次");
    }

    @Test
    public void test3(){
        List src = Arrays.asList(45, 43, 65, 6, 43, 2, 32, 45, 56, 34, 23);
        //void copy(List dest,List src)：将src中的内容复制到dest中
        //错误的写法：
//        List dest = new ArrayList();//dest长度是0；src是11，无法copy
        //正确的写法：
        List dest = Arrays.asList(new Object[src.size()]);


        Collections.copy(dest,src);

        System.out.println(dest);
    }

    @Test
    public void test4(){
        //提供了多个unmodifiableXxx()方法，该方法返回指定 Xxx的不可修改的视图。

        List list1 = new ArrayList();
        //list1可以写入数据
        list1.add(34);
        list1.add(12);
        list1.add(45);

        List list2 = Collections.unmodifiableList(list1);
        //此时的list2只能读，不能写
        list2.add("AA");//不能写
        System.out.println(list2.get(0));//34
    }

    @Test
    public void test5(){
        //Collections 类中提供了多个 synchronizedXxx() 方法
        List list1 = new ArrayList();
        //返回的list2就是线程安全的
        List list2 = Collections.synchronizedList(list1);
        list2.add(123);

        HashMap map1 = new HashMap();
        //返回的map2就是线程安全的
        Map map2 = Collections.synchronizedMap(map1);

    }
}

标签：Object,java,int,元素,add,源码,集合,public
From： https://blog.csdn.net/2403_87725694/article/details/144066560