一、集合概述
- 集合类体系结构
二、Collection 接口
- 2.1 Collection集合概述
- 2.2 Collection集合常用方法
三、Iterator 迭代器
- 3.1 Iterator 接口
- 3.2 迭代器实现原理
- 3.3 使用 Iterator 迭代器删除元素
- 3.4 并发修改异常（ ConcurrentModificationException ）
- 3.6 增强for循环
- 3.7 java.lang.Iterable 接口
- 3.8 小结
四、List 接口
- 4.1 概述
- 4.2 List集合的特有方法
- 4.3 List 特有的迭代器 ListIterator（了解）
- 4.4 List接口实现类之-ArrayList
- 4.5 List接口实现类之-LinkList
五、泛型
- 5.1 泛型的概述
- 5.2 自定义泛型结构
- 5.3 类型通配符
六、数据结构
- 6.1 概述：
- 6.2 栈
- 6.3 队列
- 6.4 数组
- 6.5 链表
- 6.6 树
七、Set 接口
- 7.1 概述
- 7.2 Set 的实现类之一：TreeSet
- 7.3 Set 的实现类之二：HashSet
  - 7.3.1 哈希值
  - 7.3.2 哈希表结构
- 7.4 Set 的实现类之二：LinkedHashSet
八、Collections 工具类
- 8.1 概述
- 8.2 常用方法
- 8.3 Collections 的同步控制方法
九、Map 接口
- 9.1 概述
- 9.2 Map 接口常用的方法
  - 9.2.1 Map集合的基本功能
  - 9.2.2 Map集合的获取功能
- 9.3 Map 集合的遍历方式
- 9.4 Map 的实现类之一：HashMap
- 9.5 Map 的实现类之二：LinkedHashMap
- 9.6 Map 的实现类之三：Hashtable
- 9.7 Map 的实现类之四：TreeMap
- 9.8 Map 的实现类之五：Properties

一、集合概述

集合是 Java 提供的一种容器，可以用来存储多个数据。
集合的本质是用来**存储对象**（有时，你会看到直接向集合中插入基本类型数据，会很疑惑，不是只能存储对象吗？其实不然，因为 JDK5 的新特性自动装箱和拆箱，所以在存储基本类型的数据的时候，会转换为对应的包装类型对象）。
数组和集合的区别
- 相同点
  - 都是容器,可以存储多个数据
- 不同点
  - 数组的长度是不可变的,集合的长度是可变的
  - 数组可以存基本数据类型和引用数据类型
  - 集合只能存引用数据类型,如果要存基本数据类型,需要存对应的包装类
集合主要分为两大类型：
- ① Collection（单列集合）：表示一组对象。
- ② Map（双列集合）：表示一组映射关系或键值对。
  集合类体系结构

二、Collection 接口

2.1 Collection集合概述

是单例集合的顶层接口,它表示一组对象,这些对象也称为Collection的元素
JDK 不提供此接口的任何直接实现.它提供更具体的子接口(如Set和List)实现
在JDK 5 之前，Java 集合会丢失容器中所有的对象的数据类型，将所有对象都当成Object类型来处理；但是，从JDK 5 增加了 **泛型** 以后，Java 集合就可以记住容器中对象的数据类型。
创建Collection集合的对象
- 多态的方式
- 具体的实现类ArrayList、LinkList等等
```
public interface Collection<E> extends Iterable<E> {
...
}
```
  2.2 Collection集合常用方法
  | 方法名 | 说明 | | —- | —- | | boolean add(E e) | 添加元素 | | boolean addAll(Collection<? extends E> c); | 添加另一个集合中的所有元素到当前集合中： | | boolean remove(Object o) | 从集合中移除指定的元素 | | boolean removeAll(Collection<?> c) | 从当前集合中删除所有与 coll 集合中相同的元素 | | default boolean removeIf(Predicate<? super E> filter) | 根据条件进行移除 | | void clear() | 清空集合中的元素 | | boolean contains(Object o) | 判断集合中是否存在指定的元素 | | boolean isEmpty() | 判断集合是否为空 | | int size() | 集合的长度，也就是集合中元素的个数 | | boolean retainAll(Collection<?> c) | 当前集合仅保留与 c 集合中的元素相同的元素，即当前集合中仅保留两个集合的交集 | | Object[] toArray() | 返回包含当前集合中所有元素的数组 | | T[] toArray(T[] a) | 返回包含当前集合中所有元素的数组 |

package com.lhl.collection;
import java.util.ArrayList;
/**
 * @author lhl
 * @ClassName CollectionDemo01
 * @description TODO
 * @data 2022/03/25 10:23
 * @Version V1.0
 **/
public class CollectionDemo01 {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("a");
        list.add("b");
        list.add("b");
        list.add("c");
        list.add("d");
        for (int i = 0; i < list.size(); i++) {
            String s = list.get(i);
            if ("b".equals(s)){
                //public E remove(int index) 注意这里是根据索引删除
                list.remove(i);
            }
        }
        System.out.println(list);
    }
}

输出：

[a, b, c, d]

导致原因：我们集合是动态变化的，删除完之后集合长度变小，索引会发生变化
优化：

        for (int i = 0; i < list.size(); i++) {
            String s = list.get(i);
            if ("b".equals(s)){
                //public E remove(int index) 注意这里是根据索引删除
                list.remove(i);
                //在成功之后删除之后进行一个i--
                i--;
            }
        }

三、Iterator 迭代器

3.1 Iterator 接口

在程序开发中，经常需要遍历集合中的所有元素。针对这种需求，JDK 专门提供了一个接口

**java.util.Iterator** 。

Iterator 接口也是 Java 集合中的医院，但是它和 Collection 、Map 接口有所不同，Collection 接口和 Map 接口主要用来存储元素，而 Iterator 接口主要用于迭代访问（即遍历）Collection 中的元素，因此 Iterator 对象也称为迭代器。

获取迭代器的方法（Collection 接口中提供的方法）：

Iterator<E> iterator();//返回集合中迭代器对象，该迭代器默认指向当前集合0索引

Iterator中的常用方法

判断是否有元素可以迭代，如果有，返回 true ；否则，返回 false ：

//boolean hasNext(): 判断当前位置是否有元素可以被取出
boolean hasNext();

返回迭代的下一个元素：

//    E next(): 获取当前位置的元素,将迭代器对象移向下一个索引位置 
E next();

Collection集合的遍历实例

public class IteratorDemo1 {
  public static void main(String[] args) {
      //创建集合对象
      Collection<String> c = new ArrayList<>();
      //添加元素
      c.add("hello");
      c.add("world");
      c.add("java");
      c.add("javaee");
          //Iterator<E> iterator()：返回此集合中元素的迭代器，通过集合的iterator()方法得到
      Iterator<String> it = c.iterator();
      //判断集合中是否有元素
      while (it.hasNext()) {
          // 获取当前位置的元素,将迭代器对象移向下一个索引位置 
          String s = it.next();
          System.out.println(s);
      }
  }
}

注意：在使用迭代器进行遍历集合的时候，如果集合中已经没有元素了，还使用迭代器的 next 方法，将会抛出 java.util.NoSuchElementException 异常。

3.2 迭代器实现原理

每个集合容器的内部结构都是不同的，但是迭代器都可以进行统一的遍历是实现，是怎么做到的？
Collection 接口提供了获取 Iterator 的方法：
```
Iterator<E> iterator();
```
那么，Collection 接口的每个子类都必须重写这个方法。

以 ArrayList 为例：

public class ArrayList<E> extends AbstractList<E>
      implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
  // 重写了iterator方法
  public Iterator<E> iterator() {
      return new Itr();
  }
  private class Itr implements Iterator<E> {
      ...
  }
  ...
}

3.3 使用 Iterator 迭代器删除元素

Iterator 接口中有一个删除的默认方法：

default void remove() {
  throw new UnsupportedOperationException("remove");
}

既然，Collection 接口中已经有了 remove(xxx) 的方法，为什么 Iterator 迭代器中还要提供 remove() 方法？
因为Collection 接口的 remove(xxx) 方法无法根据指定条件删除。

注意：不要在使用 Iterator 迭代器迭代元素的时候，调用 Collection 的 remove(xxx) 方法，否则会报 java.util.ConcurrentModificationException 异常或出现其他不确定的行为。

实例：删除指定元素

public class IteratorDemo2 {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("a");
        list.add("b");
        list.add("b");
        list.add("c");
        list.add("d");
        Iterator<String> it = list.iterator();
        while(it.hasNext()){
            String s = it.next();
            if("b".equals(s)){
                //我们迭代器底层好比一个箭头，指向谁,那么此时就删除谁.
                it.remove();
            }
        }
        System.out.println(list);
    }
}

示例二：删除集合中的偶数元素

public class IteratorDemo3 {
    public static void main(String[] args) {
        Collection<Integer> collection = new ArrayList<>();
        collection.add(1);
        collection.add(2);
        collection.add(3);
        collection.add(4);
        System.out.println("原来集合中的元素 = " + collection); // 原来集合中的元素 = [1, 2, 3, 4]
        for (Iterator<Integer> iterator = collection.iterator(); iterator.hasNext();) {
            Integer ele = iterator.next();
            if (ele % 2 == 0) {
                iterator.remove();
            }
        }
        System.out.println("后来集合中的元素 = " + collection); // 后来集合中的元素 = [1, 3]
    }
}

3.4 并发修改异常（ ConcurrentModificationException ）

异常的产生原因：在迭代器遍历集合的过程中，调用集合自身的功能（例如：调用集合的 add 和 remove 方法），改变集合的长度。
示例：并发修改异常 ```java package com.lhl;

import java.util.ArrayList; import java.util.Collection; import java.util.Iterator;

/**

@author lhl
@ClassName Test
@description TODO
@data 2022/03/22 11:52

@Version V1.0 **/ public class IteratorDemo4 { public static void main(String[] args) {

 Collection<String> collection = new ArrayList<>();
 collection.add("aa");
 collection.add("bb");
 collection.add("cc");
 collection.add("dd");
 for (Iterator<String> iterator = collection.iterator(); iterator.hasNext();) {
     String ele = iterator.next();
     System.out.println("ele = " + ele);
     collection.add("ee");
 }

} }

![image.png](https://cdn.nlark.com/yuque/0/2022/png/26775128/1647921218407-9cc9869c-22c0-4fe2-976f-91e2aecd913d.png#clientId=u19d5c3b5-fecb-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=177&id=uaae621b8&margin=%5Bobject%20Object%5D&name=image.png&originHeight=221&originWidth=1064&originalType=binary&ratio=1&rotation=0&showTitle=false&size=29767&status=done&style=none&taskId=ua50e2c3c-061e-4b56-ad25-fcfe697a9c6&title=&width=851.2)

-  如果在 Iterator、ListIterator 迭代器创建后的任意时间从结构上修改了集合（通过迭代器自身的remove或add方法之外的任何其他方式），则迭代器会抛出 ConcurrentModificationException 异常。因此，面对并发的修改，迭代器很快会失败，而不是冒着在将来不确定的时间发生不确定行为的风险。 
-  这样设计时因此，迭代器代表集合中的某个元素的位置，内部会存储某些能够代表该位置的信息。当集合发生改变的时候，该信息的含义可能会发生变化，这个时候操作迭代器就有可能造成不可预料的后果。因此，果断抛出异常阻止，是最好的方法，这就是 Iterator 迭代器的**快速失败机制**。 
-  需要注意的是，迭代器的快速失败机制行文不能得到保证，一般来说，存在不同步的并发修改时，不可能做出任何坚决的保证。快速失败机制尽最大努力抛出 ConcurrentModificationException 。因此，`迭代器的快速失败行文应该仅仅用于检测bug` 。 
-  快速失败机制的实现原理： 
   - ① 在 ArrayList 等集合类中都有一个 modCount 变量，它用来记录集合的结构被修改的次数。
   - ② 当我们给集合添加或删除元素的时候，会导致 modCount++ 。
   - ③ 当我们使用 Iterator 迭代器遍历集合的时候，会使用一个变量记录当前集合的 modCount 。例如：`int expectedModCount = modCount;`，并且，在迭代器每次 next() 迭代元素的时候，都要检查 `expectedModCount != modCount` ，如果不相等，则说明调用了 Iterator 迭代器以外的 Collection 的 add 、remove 等方法，修改了集合的结构，使得 modCount++ ，值变了，就会抛出 ConcurrentModificationException 。

<a name="tdeEL"></a>
## 3.5 集合存储自定义对象并迭代
```java
package com.lhl.collection.demo5;

/**
 * @author lhl
 * @ClassName Person
 * @description TODO
 * @data 2022/03/22 14:55
 * @Version V1.0
 **/
public class Person {
    private String name;
    private Integer age;

    public Person() {
    }

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

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

package com.lhl.collection.demo5;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;

/**
 * @author lhl
 * @ClassName Test
 * @description TODO
 * @data 2022/03/22 14:56
 * @Version V1.0
 **/
public class Test {
    public static void main(String[] args) {
        Collection<Person> collection = new ArrayList<>();

        collection.add(new Person("张三", 11));
        collection.add(new Person("李四", 59));
        collection.add(new Person("王五", 19));
        collection.add(new Person("赵六", 42));
        collection.add(new Person("田七", 8));
        collection.add(new Person("王八", 2));

        for (Iterator<Person> iterator = collection.iterator(); iterator.hasNext();) {
            Person next = iterator.next();
            System.out.println(next);
        }
    }
}

3.6 增强for循环

介绍
- 它是JDK5之后出现的,其内部原理是一个Iterator迭代器 , 专门用来遍历数组和集合
- 实现Iterable接口的类才可以使用迭代器和增强for
  - public interface Collection extends Iterable
  - public interface Map

格式

for(集合/数组中元素的数据类型 变量名 :  集合/数组名) {
 // 已经将当前遍历到的元素封装到变量中了,直接使用变量即可
}

示例：遍历数组（不要在遍历数组的时候对数组的元素进行修改）

public class Test {
  public static void main(String[] args) {
      // 创建数组
      int[] arr = {1, 2, 3, 4, 5};
      // 遍历数组
      for (int i : arr) {
          System.out.println("i = " + i);
      }
  }
}

示例：遍历集合（不要在遍历集合的时候对集合中的元素进行增加、删除、替换等操作）

public class MyCollectonDemo1 {
  public static void main(String[] args) {
      ArrayList<String> list =  new ArrayList<>();
      list.add("a");
      list.add("b");
      list.add("c");
      list.add("d");
      list.add("e");
      list.add("f");

      //1,数据类型一定是集合或者数组中元素的类型
      //2,str仅仅是一个变量名而已,在循环的过程中,依次表示集合或者数组中的每一个元素
      //3,list就是要遍历的集合或者数组
      for(String str : list){
          System.out.println(str);
      }
  }
}

str仅仅是一个变量名而已,在循环的过程中,依次表示集合或者数组中的每一个元素
它是一个第三方变量，修改str并不会影响集合中的值

3.7 java.lang.Iterable 接口

**java.lang.Iterable** 接口，实现这个接口，允许对象称为 “for each” 语句的目标。
●JDK 5 的时候，Collection 接口继承了 java.lang.Iterable 接口，因此 Collection 系列的集合就可以直接使用 foreach 循环。
●java.lang.Iterable 接口的抽象方法：

// 获取对应的迭代器，用来遍历数组或集合中的元素的。
Iterator<T> iterator();

foreach 循环遍历集合的本质就是使用 Iterator 迭代器进行遍历的。

注意：不要在使用 foreach 循环遍历集合的时候，使用 Collection 的 remove() 等方法。否则，要么报 java.util.ConcurrentModificationException 异常，要么行为不确定。

3.8 小结

如果需要操作索引，使用普通For
如果在遍历过程中需要删除元素，请使用迭代器
如果仅仅想遍历元素，使用增强for

四、List 接口

4.1 概述
鉴于 Java 中数组用来存储数据的局限性，我们通常使用 List 来代替数组。
List 集合类中 **元素有序**（元素存储和取出的顺序一致）、**且可重复** ，集合中的每个元素都有其对应的顺序索引。
List 容器中的元素都对应一个整数类型的序号记载其在容器中的位置，根据根据序号存取容器中的元素。也就是说**可以通过索引操作元素**
List 接口的常用类：
- ArrayList ：底层是数组结构实现，查询快、增删慢
- LinkedList ：底层是链表结构实现，查询慢、增删快
- Vector（已过时）。
  4.2 List集合的特有方法
  | 方法名 | 描述 | | —- | —- | | void add(int index,E element) | 在此集合中的指定位置插入指定的元素 | | E remove(int index) | 删除指定索引处的元素，返回被删除的元素 | | E set(int index,E element) | 修改指定索引处的元素，返回被修改的元素 | | E get(int index) | 返回指定索引处的元素 | | int indexOf(Object o) | 从前往后根据元素查找其索引，如果找到，返回该元素的索引；否则，返回 -1 |

4.2.1 添加元素

4.2.2 获取元素

4.2.3 获取元素索引

4.2.4 删除元素

4.2.5 替换元素

4.3 List 特有的迭代器 ListIterator（了解）

List 接口提供了获取 ListIterator 的方法，该方法返回一个 ListIterator 对象：

ListIterator<E> listIterator();

// 如果从后向前遍历，index就是最后一个元素的索引，即list的size()
ListIterator<E> listIterator(int index);

ListIterator 接口继承了 Iterator 接口，提供了专门操作 List 的方法：
- 是否有下一个元素：
```
boolean hasNext();
```
- 返回下一个元素：
```
E next();
```
- 返回后一个元素的索引：
```
int nextIndex();
```
- 返回前一个元素的索引：
```
int previousIndex();
```
- 逆向遍历集合，向前是否还有元素：
```
boolean hasPrevious();
```
- 获取前一个元素：
```
E previous();
```
- 通过迭代器添加元素到集合中：
```
void add(E e);
```
- 通过迭代器替换元素：
```
void set(E e);
```

4.4 List接口实现类之-ArrayList

4.4.1 概述

ArrayList 具备了List接口的特性（有序、重复、索引）。
ArrayList 集合底层的实现原理是数组，大小可变。
ArrayList 的特点：查询速度快、增删慢。
ArrayList 在 JDK8 前后的实现区别：
- JDK7 ：ArrayList 像饿汉式，直接创建了一个初始容量为 10 的数组，每次扩容是原来长度的 1.5 倍。
- JDK8 ：ArrayList 像懒汉式，一开始创建一个长度为 0 的数组，当添加第一个元素的时候再创建一个容器为 10 的数组，每次扩容是原来长度的 1.5 倍。
ArrayList 是线程不安全的集合，运行速度快。

4.4.2 ArrayList的类成员变量

默认容量：

private static final int DEFAULT_CAPACITY = 10;

空数组：

private static final Object[] EMPTY_ELEMENTDATA = {};

默认容量的空数组：

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

ArrayList 集合中的核心数组：
```
transient Object[] elementData;
```
记录数组中存储个数：
```
private int size;
```

数组扩容的最大值：

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

4.4.3 ArrayList 类的构造方法

public ArrayList()	创建一个空的集合对象
ArrayList (int initialCapacity)	构造具有指定初始容量的空列表。

无参构造方法：

public ArrayList() {
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

传入指定容量的构造方法：

public ArrayList(int initialCapacity) {
  if (initialCapacity > 0) {
      this.elementData = new Object[initialCapacity];
  } else if (initialCapacity == 0) {
      this.elementData = EMPTY_ELEMENTDATA;
  } else {
      throw new IllegalArgumentException("Illegal Capacity: "+
                                         initialCapacity);
  }
}

4.4.4 ArrayList 类的 add 方法

public boolean add(E e)	将指定的元素追加到此集合的末尾

public boolean add(E e) {
    // 检查容量 size初始化的时候是0，那么size+1就是1
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将元素添加到数组中，size计数器++
    elementData[size++] = e;
    return true;
}

// minCapacity此时是1
private void ensureCapacityInternal(int minCapacity) {
    // 如果存储元素的数据 == 默认的空的数组，无参构造器中赋值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 返回DEFAULT_CAPACITY=10和minCapacity=1的最大值，即10
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 扩容
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    // 10- 数组的长度0 > 0
    if (minCapacity - elementData.length > 0)
        // 传入10
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    // 数组的原来长度 0 
    int oldCapacity = elementData.length;
    // 新容量 = 数组原来的长度 + 数组原来的长度 / 2
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 0
    if (newCapacity - minCapacity < 0) // 0 -10 < 0
        newCapacity = minCapacity; // 新容量 = 10
    if (newCapacity - MAX_ARRAY_SIZE > 0) // 判断是否超过最大容量
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity); // 数组的复制
}

4.4.5 ArrayList 类的 get 方法

public E get(int index) {
    // 检查索引
    rangeCheck(index);
    // 返回数组中指定索引处的元素
    return elementData(index);
}

4.4.6 ArrayList 类的 set 方法

public E set(int index, E element) {
    // 检查索引
    rangeCheck(index);
    // 获取旧的元素
    E oldValue = elementData(index);
    // 将新的元素设置到指定的索引处
    elementData[index] = element;
    // 返回旧的元素
    return oldValue;
}

4.4.7 ArrayList 类的 remove 方法

public E remove(int index) {
    // 检查索引
    rangeCheck(index);

    modCount++;
    // 获取旧的元素
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 将index后面的元素依次复制到前面
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 最后一个元素设置为null
    elementData[--size] = null; // clear to let GC do its work
    // 返回旧的元素
    return oldValue;
}

4.4.8 ArrayList类方法总结

方法	说明
public boolean remove(Object o)	删除指定的元素，返回删除是否成功
public E remove(int index)	删除指定索引处的元素，返回被删除的元素
public E set(int index,E element)	修改指定索引处的元素，返回被修改的元素
public E get(int index)	返回指定索引处的元素
public int size()	返回集合中的元素的个数

示例代码 :

public class ArrayListDemo02 {
    public static void main(String[] args) {
        //创建集合
        ArrayList<String> array = new ArrayList<String>();

        //添加元素
        array.add("hello");
        array.add("world");
        array.add("java");

        //public boolean remove(Object o)：删除指定的元素，返回删除是否成功
        //System.out.println(array.remove("world"));
        //System.out.println(array.remove("javaee"));

        //public E remove(int index)：删除指定索引处的元素，返回被删除的元素
        //System.out.println(array.remove(1));

        //IndexOutOfBoundsException
        //System.out.println(array.remove(3));

        //public E set(int index,E element)：修改指定索引处的元素，返回被修改的元素
        //System.out.println(array.set(1,"javaee"));

        //IndexOutOfBoundsException
        //System.out.println(array.set(3,"javaee"));

        //public E get(int index)：返回指定索引处的元素
        //System.out.println(array.get(0));
        //System.out.println(array.get(1));
        //System.out.println(array.get(2));
        //System.out.println(array.get(3)); //自己测试

        //public int size()：返回集合中的元素的个数
        System.out.println(array.size());

        //输出集合
        System.out.println("array:" + array);
    }
}

思考：为什么在打印一个ArrayList对象时,输出的不是此对象的地址,而是该集合中的值?是如何实现的? ArrayList的父类的父类当中AbstractCollection重写了toString()方法

4.4.9 ArrayList存储字符串并遍历

案例需求 :

创建一个存储字符串的集合，存储3个字符串元素，使用程序实现在控制台遍历该集合

实现步骤 :

1:创建集合对象
2:往集合中添加字符串对象
3:遍历集合，首先要能够获取到集合中的每一个元素，这个通过get(int index)方法实现
4:遍历集合，其次要能够获取到集合的长度，这个通过size()方法实现
5:遍历集合的通用格式

代码实现 :

/*
    思路：
        1:创建集合对象
        2:往集合中添加字符串对象
        3:遍历集合，首先要能够获取到集合中的每一个元素，这个通过get(int index)方法实现
        4:遍历集合，其次要能够获取到集合的长度，这个通过size()方法实现
        5:遍历集合的通用格式
 */
public class ArrayListTest01 {
    public static void main(String[] args) {
        //创建集合对象
        ArrayList<String> array = new ArrayList<String>();

        //往集合中添加字符串对象
        array.add("刘正风");
        array.add("左冷禅");
        array.add("风清扬");

        //遍历集合，其次要能够获取到集合的长度，这个通过size()方法实现
        //System.out.println(array.size());

        //遍历集合的通用格式
        for(int i=0; i<array.size(); i++) {
            String s = array.get(i);
            System.out.println(s);
        }
    }
}

4.4.10 ArrayList存储学生对象并遍历

案例需求 :

创建一个存储学生对象的集合，存储3个学生对象，使用程序实现在控制台遍历该集合

实现步骤 :

1:定义学生类<br />    2:创建集合对象<br />    3:创建学生对象<br />    4:添加学生对象到集合中<br />    5:遍历集合，采用通用遍历格式实现

代码实现 :

/*
    思路：
        1:定义学生类
        2:创建集合对象
        3:创建学生对象
        4:添加学生对象到集合中
        5:遍历集合，采用通用遍历格式实现
 */
public class ArrayListTest02 {
    public static void main(String[] args) {
        //创建集合对象
        ArrayList<Student> array = new ArrayList<>();

        //创建学生对象
        Student s1 = new Student("林青霞", 30);
        Student s2 = new Student("风清扬", 33);
        Student s3 = new Student("张曼玉", 18);

        //添加学生对象到集合中
        array.add(s1);
        array.add(s2);
        array.add(s3);

        //遍历集合，采用通用遍历格式实现
        for (int i = 0; i < array.size(); i++) {
            Student s = array.get(i);
            System.out.println(s.getName() + "," + s.getAge());
        }
    }
}

4.4.11 键盘录入学生信息到集合

案例需求 :

创建一个存储学生对象的集合，存储3个学生对象，使用程序实现在控制台遍历该集合<br />        学生的姓名和年龄来自于键盘录入

实现步骤 :

1:定义学生类，为了键盘录入数据方便，把学生类中的成员变量都定义为String类型<br />    2:创建集合对象<br />    3:键盘录入学生对象所需要的数据<br />    4:创建学生对象，把键盘录入的数据赋值给学生对象的成员变量<br />    5:往集合中添加学生对象<br />    6:遍历集合，采用通用遍历格式实现

代码实现 :

/*
    思路：
        1:定义学生类，为了键盘录入数据方便，把学生类中的成员变量都定义为String类型
        2:创建集合对象
        3:键盘录入学生对象所需要的数据
        4:创建学生对象，把键盘录入的数据赋值给学生对象的成员变量
        5:往集合中添加学生对象
        6:遍历集合，采用通用遍历格式实现
 */
public class ArrayListTest {
    public static void main(String[] args) {
        //创建集合对象
        ArrayList<Student> array = new ArrayList<Student>();

        //为了提高代码的复用性，我们用方法来改进程序
        addStudent(array);
        addStudent(array);
        addStudent(array);

        //遍历集合，采用通用遍历格式实现
        for (int i = 0; i < array.size(); i++) {
            Student s = array.get(i);
            System.out.println(s.getName() + "," + s.getAge());
        }
    }

    /*
        两个明确：
            返回值类型：void
            参数：ArrayList<Student> array
     */
    public static void addStudent(ArrayList<Student> array) {
        //键盘录入学生对象所需要的数据
        Scanner sc = new Scanner(System.in);

        System.out.println("请输入学生姓名:");
        String name = sc.nextLine();

        System.out.println("请输入学生年龄:");
        String age = sc.nextLine();

        //创建学生对象，把键盘录入的数据赋值给学生对象的成员变量
        Student s = new Student();
        s.setName(name);
        s.setAge(age);

        //往集合中添加学生对象
        array.add(s);
    }
}

4.4.12 ArrayList扩容

ArrayList第一次添加元素的源码解析.png

4.5 List接口实现类之-LinkList

4.5.1 概述

LinkedList 具备了 List 接口的特性（有序、重复、索引）。
LinkedList 地城实现原理是双向链表。
LinkedList 的增删速度快、查询慢。
LinkedList 是线程不安全的集合，运行速度快。

4.5.2 LinkedList 集合特有方法
特有方法
| 方法名 | 说明 | | —- | —- | | public void addFirst(E e) | 在该列表开头插入指定的元素 | | public void addLast(E e) | 将指定的元素追加到此列表的末尾 | | public E getFirst() | 返回此列表中的第一个元素 | | public E getLast() | 返回此列表中的最后一个元素 | | public E removeFirst() | 从此列表中删除并返回第一个元素 | | public E removeLast() | 从此列表中删除并返回最后一个元素 |

示例代码：

public class Test {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();

        linkedList.add("aa");
        linkedList.add("bb");
        linkedList.add("cc");
        linkedList.add("dd");

        System.out.println("linkedList = " + linkedList); // linkedList = [aa, bb, cc, dd]

        linkedList.addFirst("你好啊");

        System.out.println("linkedList = " + linkedList); // linkedList = [你好啊, aa, bb, cc, dd]

        linkedList.addLast("你好呢");

        System.out.println("linkedList = " + linkedList); // linkedList = [你好啊, aa, bb, cc, dd, 你好呢]

        System.out.println(linkedList.getFirst()); // 你好啊

        System.out.println(linkedList.getLast()); // 你好呢

        linkedList.removeFirst();

        System.out.println("linkedList = " + linkedList); // linkedList = [aa, bb, cc, dd, 你好呢]

        linkedList.removeLast();

        System.out.println("linkedList = " + linkedList); // linkedList = [aa, bb, cc, dd]
    }
}

4.5.3 LinkedList 的类成员变量

集合中存储元素个数的计数器：
```
transient int size = 0;
```

第一个元素：

transient Node<E> last;

4.5.4 LinkedList 的成员内部类 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;
  }
}

4.5.5 LinkedList 类的 add 方法

```java public boolean add(E e) { linkLast(e); return true; }

void linkLast(E e) { // 声明新的节点对象 = last final Node l = last; // l = null // 创建新的节点对象 final Node newNode = new Node<>(l, e, null); // 新的节点赋值给最后一个节点 last = newNode; if (l == null) // 将新的节点赋值给first first = newNode; else // 将新的节点赋值给最后一个节点的最后 l.next = newNode; size++; modCount++; }

<a name="e6239825"></a>
### 4.5.6 LinkedList 类的 get 方法
```java
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
Node<E> node(int index) {
    // assert isElementIndex(index);
    // 索引是否小于长度的一半，二分查找
    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;
    }
}

五、泛型

5.1 泛型的概述

5.1.1 泛型设计的背景

集合容器类在设计阶段/声明阶段不能确定这个容器到底存的是什么。
因为这个时候除了元素的类型不确定，其他的部分是确定的，例如：关于这个元素如何保存，如何管理等是确定的，因此，此时可以将元素的类型设置成一个参数，这个类型参数叫做泛型。比如：Collection<E> 、List<E> 中的 <E> 就是类型参数，即泛型。

5.1.2 泛型概念

所谓泛型，就是运行在定义类、接口或方法时通过一个标识表示类中某个属性的类型或者某个方法的返回值以及参数类型。这个参数将在使用的时候确定。
从 JDK 5 以后，Java 引入了参数化类型（ Parameterized type ）的概念，允许我们在创建集合的时候指定集合元素的类型，如：List<String> ，这表明该 List 只能保存 String 类型的元素。
JDK 5 改写了集合框架中的全部接口和类，为这些接口和类增加了泛型支持，从而可以在声明集合变量、创建集合对象时传入类型实参。
泛型带来的好处
1. 提供了编译时类型安全检测机制，把运行时期的问题提前到了编译期间
2. 避免了强制类型转换
泛型的定义格式
- **<类型>**: 指定一种类型的格式.尖括号里面可以任意书写,一般只写一个字母.例如:
```
<类型>
```
  指定一种类型的格式，尖括号里面可以任意书写，按照变量的定义规则即可，一般只写一个字母。比如：<E> 、<T> 等。
- **<类型1,类型2…>**: 指定多种类型的格式,多种类型之间用逗号隔开.例如:
```
<类型1,类型2,……>
```
  指定多种类型的格式，多种类型之间用逗号隔开。比如：<K,V> 等。

泛型可以使用的地方：
- 类后面 ———— 泛型类
- 方法申明上 ———— 泛型方法
- 接口后面 ———— 泛型接口

5.1.3 为什么要有泛型？

泛型解决了如下的问题：
① 解决元素存储的安全性问题。
② 解决获取数据元素时，需要类型强制转换的问题。

Java 泛型可以保证如果程序在编译的时候没有发出警告，运行的时候就不会产生 ClassCastException 异常。同时，代码更加简洁、健壮。

5.1.4 泛型的相关名词

自从有了泛型以后，Java 的数据类型就更加丰富了。

Class ：Class 类的实例表示正在运行的 Java 应用程序中的类和接口。枚举是一种类，注解是一种接口。每个数组被映射为 Class 对象的一个类，所有具有相同元素类型和维数的数组都共享该 Class 对象。基本的Java数据类型（byte 、short 、int 、long 、double 、float 、char ）和关键字 void 也表示为 Class 对象。
GenericArrayType ：泛化的数组类型，即 T[] 。
ParameterizedType ：参数化类型，例如：Comparator<String> 。
TypeVariable ：类型变量，例如：Comparator<T> 中的 T 。
WildcardType ：通配符类型，例如：Comparator<?> 等。

5.2 自定义泛型结构

5.2.1 概述

泛型可以声明在类、接口和方法上。

5.2.2 泛型类【应用】

定义格式

【修饰符】 class 类名<类型变量列表> 【extends 父类】 【implements 父接口们】{
 ...
}

示例代码

泛型类

public class Generic<T> {
private T t;

public T getT() {
  return t;
}

public void setT(T t) {
  this.t = t;
}
}

测试类

public class GenericDemo1 {
public static void main(String[] args) {
  Generic<String> g1 = new Generic<String>();
  g1.setT("杨幂");
  System.out.println(g1.getT());

  Generic<Integer> g2 = new Generic<Integer>();
  g2.setT(30);
  System.out.println(g2.getT());

  Generic<Boolean> g3 = new Generic<Boolean>();
  g3.setT(true);
  System.out.println(g3.getT());
}
}

5.2.3 泛型接口【应用】

定义格式

【修饰符】 interface 接口名<类型变量列表> 【implements 父接口们】{
 ...
}

示例代码

泛型接口

public interface Generic<T> {
void show(T t);
}

泛型接口实现类1
定义实现类时,定义和接口相同泛型,创建实现类对象时明确泛型的具体类型
```
public class GenericImpl1<T> implements Generic<T> {
@Override
public void show(T t) {
  System.out.println(t);
}
}
```

泛型接口实现类2
定义实现类时,直接明确泛型的具体类型

public class GenericImpl2 implements Generic<Integer>{
@Override
public void show(Integer t) {
    System.out.println(t);
}
}

测试类

public class GenericDemo3 {
public static void main(String[] args) {
  GenericImpl1<String> g1 = new GenericImpl<String>();
  g1.show("林青霞");
  GenericImpl1<Integer> g2 = new GenericImpl<Integer>();
  g2.show(30);

  GenericImpl2 g3 = new GenericImpl2();
    g3.show(10);
}
}

注意：

<类型变量列表> ：可以是一个或多个类型变量，一般都使用单个的大写字母表示，如：<T> 、<E> 等。
<类型变量列表> 中的类型变量不能作用于静态成员上。

5.2.4 泛型类泛型接口使用

什么时候使用泛型类或泛型接口？
① 当某个类的非静态实例变量的类型不确定，需要在创建对象或子类继承的时候才能确定。
② 当某个类的非静态方法的形参类型不确定，需要在创建对象或子类继承的时候才能确定。

示例：我们要声明一个学生类，该学生包含姓名、成绩，而此时学生的成绩类型不确定，为什么呢，因为，语文老师希望成绩是“优秀”、“良好”、“及格”、“不及格”，数学老师希望成绩是 89.5 , 65.0，英语老师希望成绩是 ‘A’ , ‘B’ , ‘C’ , ‘D’ , ‘E’ 。那么我们在设计这个学生类时，就可以使用泛型。

示例：

public class Student<T> {
private String name;

private T score;

public Student() {}

public Student(String name, T score) {
   this.name = name;
   this.score = score;
}

public String getName() {
   return this.name;
}

public void setName(String name) {
   this.name = name;
}

public T getScore() {
   return this.score;
}

public void setScore(T score) {
   this.score = score;
}

@Override
public String toString() {
   return "Student{" + "name='" + this.name + '\'' + ", score=" + this.score + '}';
}
}

在使用泛型类和泛型接口的时候，我们需要指定泛型变量的实际类型参数：
① 实际类型参数必须是引用数据类型，不能是基本数据类型。

② 在创建类的对象时指定类型变量对应的实际类型参数。

public class Test {
 public static void main(String[] args) {
     // 语文老师
     Student<String> stu1 = new Student<>("张三", "良好");
     System.out.println("stu1 = " + stu1); // stu1 = Student{name='张三', score=良好}
     // 数学老师
     Student<Double> stu2 = new Student<>("李四", 80.0);
     System.out.println("stu2 = " + stu2); // stu2 = Student{name='李四', score=80.0}
     // 英语老师
     Student<Character> stu3 = new Student<>("王五", 'A');
     System.out.println("stu3 = " + stu3); // stu3 = Student{name='王五', score=A}
 }
}

5.2.5 类型变量的上限

当在声明类型变量的时候，如果不希望这个类型变量代表任意的数据类型，而是某个系列的引用数据类型，那么可以设定类型变量的上限。
语法：
```
<类型变量 extends 上限>
```
```
<类型变量 extends 上限1 & 上限2>
```
注意：
- ① 如果多个上限中有类和接口，那么只能有一个类，并且必须写在左边。
- ② 如果多个上限中都是接口，且有多个，没有顺序要求。
- ③ 如果在声明 <类型变量> 时没有指定任何上限，则默认上下是 java.lang.Object 。

示例：声明一个两个数求和的工具类，要求两个加数必须是 Number 数字类型，并且实现 Comparable 接口。

public class SumTools<T extends Number & Comparable<T>> {
  private T t1;

  private T t2;

  public SumTools(T t1, T t2) {
      this.t1 = t1;
      this.t2 = t2;
  }

  public T getSum() {
      if (this.t1 instanceof BigInteger) {
          return (T)((BigInteger)this.t1).add((BigInteger)this.t2);
      } else if (this.t1 instanceof BigDecimal) {
          return (T)((BigDecimal)this.t1).add((BigDecimal)this.t2);
      } else if (this.t1 instanceof Integer) {
          return (T)(Integer.valueOf((Integer)this.t1 + (Integer)this.t2));
      } else if (this.t1 instanceof Long) {
          return (T)(Long.valueOf((Long)this.t1 + (Long)this.t2));
      } else if (this.t1 instanceof Float) {
          return (T)(Float.valueOf((Float)this.t1 + (Float)this.t2));
      } else if (this.t1 instanceof Double) {
          return (T)(Double.valueOf((Double)this.t1 + (Double)this.t2));
      }
      throw new UnsupportedOperationException("不支持该操作");
  }
}

public class Test {
  public static void main(String[] args) {
      SumTools<Integer> sumTools = new SumTools<>(1, 2);
      Integer sum = sumTools.getSum();
      System.out.println("sum = " + sum);
  }
}

5.2.6 泛型擦除

当使用参数化类型的类或接口时，如果没有指定泛型，会发生泛型擦除，自动按照最左边的第一个上限处理。如果没有指定上限，上限即为 Object 。

5.2.7 泛型方法【应用】

在定义类、接口时可以声明 <类型变量> ，在该类的方法和属性定义、接口的方法定义中，这些 <类型变量> 可被当成普通类型来用。但是，在另外一些情况下，
- ① 如果我们定义类、接口时没有使用 <类型变量> ，但是某个方法形参类型不确定时，可以单独这个方法定义 <类型变量> ；
- ② 另外我们之前说类和接口上的类型形参是不能用于静态方法中，那么当某个静态方法的形参类型不确定时，可以单独定义 <类型变量> 。
JDK1.5 之后，还提供了泛型方法的支持。

定义格式

【修饰符】 <类型变量列表> 返回值类型 方法名(【形参列表】)【throws 异常列表】{
 //...
}

示例代码

带有泛型方法的类

public class Generic {
public <T> void show(T t) {
  System.out.println(t);
}
}

测试类

public class GenericDemo2 {
public static void main(String[] args) {
  Generic g = new Generic();
  g.show("柳岩");
  g.show(30);
  g.show(true);
  g.show(12.34);
}
}

示例代码2

public class MyArrays {

 /**
  * 排序
  * 
  * @param arr
  * @param <T>
  */
 public static <T extends Comparable<T>> void sort(T[] arr) {
     for (int i = 1; i < arr.length - 1; i++) {
         for (int j = 0; j < arr.length - i - 1; j++) {
             if (arr[j].compareTo(arr[j + 1]) > 0) {
                 T temp = arr[j];
                 arr[j] = arr[j + 1];
                 arr[j + 1] = temp;
             }
         }
     }
 }
}

5.3 类型通配符

5.3.1 `<?>` 任意类型

<?> 表示元素类型可以是任意类型的。
注意事项：
- 读取 List<?> 的对象 list 中的元素时，永远是安全的，因为不管 list 的真实类型是什么，它包含的都是 Object 。
- 写入 List<?> 中的元素时，不行。因为我们不知道 List 的元素类型，我们不能向其中添加对象。唯一的例外是 null ，它是所有类型的成员。
- **<?>** 不能用来泛型方法声明上。
```
// 编译错误
public static <?> void test(ArrayList<?> list){
}
```
- <?> 不能用来泛型类的声明上。
```
// 编译错误
public GenericTypeClass<?>{
}
```
- <?> 不能用在创建对象上，右边属于创建集合对象。
```
// 编译错误
ArrayList<?> list2 = new ArrayList<?>();
```
  5.3.2 <? extends 类型> 类型通配符上限
ArrayListList <? extends Number>: 它表示的类型是Number或者其子类型

示例：

public class Student<T> {
  private String name;

  private T score;

  public Student() {}

  public Student(String name, T score) {
      this.name = name;
      this.score = score;
  }

  public String getName() {
      return this.name;
  }

  public void setName(String name) {
      this.name = name;
  }

  public T getScore() {
      return this.score;
  }

  public void setScore(T score) {
      this.score = score;
  }

  @Override
  public String toString() {
      return "Student{" + "name='" + this.name + '\'' + ", score=" + this.score + '}';
  }
}

public class StudentService {
  public static Student<? extends Comparable> max(Student<? extends Comparable>[] arr) {
      Student<? extends Comparable> max = arr[0];
      for (int i = 0; i < arr.length; i++) {
          if (arr[i].getScore().compareTo(max.getScore()) > 0) {
              max = arr[i];
          }
      }
      return max;
  }
}

public class Test {
  public static void main(String[] args) {
      Student<? extends Double>[] arr = new Student[3];
      arr[0] = new Student<>("张三", 90.5);
      arr[1] = new Student<>("李四", 80.5);
      arr[2] = new Student<>("王五", 94.5);

      Student<? extends Comparable> max = StudentService.max(arr);
      System.out.println(max);
  }
}

5.3.3 `<? super类型>` 类型通配符下限

ArrayListList <? super Number>: 它表示的类型是Number或者其父类型 ```java import java.util.Comparator;

public class MyArrays{ public static void sort(T[] arr, Comparator<? super T> c){ for (int i = 1; i < arr.length; i++) { for (int j = 0; j < arr.length-i; j++) { if(c.compare(arr[j], arr[j+1])>0){ T temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } } }

<a name="VOKYr"></a>
###  ![image.png](https://cdn.nlark.com/yuque/0/2022/png/26775128/1648056934107-32fd606b-d63e-4f00-a1d5-63bb537c2224.png#clientId=u1db55008-5133-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=417&id=y2aJk&margin=%5Bobject%20Object%5D&name=image.png&originHeight=521&originWidth=1166&originalType=binary&ratio=1&rotation=0&showTitle=false&size=36619&status=done&style=none&taskId=udd6aaad3-720b-4f45-ac9a-7d9a88e3664&title=&width=932.8)
<a name="wetUs"></a>
### 5.3.4  泛型通配符的使用 
```java
public class GenericDemo4 {
    public static void main(String[] args) {
        ArrayList<Integer> list1 = new ArrayList<>();
        ArrayList<String> list2 = new ArrayList<>();
        ArrayList<Number> list3 = new ArrayList<>();
        ArrayList<Object> list4 = new ArrayList<>();

        method(list1);
        method(list2);
        method(list3);
        method(list4);

        getElement1(list1);
        getElement1(list2);//报错
        getElement1(list3);
        getElement1(list4);//报错

        getElement2(list1);//报错
        getElement2(list2);//报错
        getElement2(list3);
        getElement2(list4);
    }

    // 泛型通配符: 此时的泛型?,可以是任意类型
    public static void method(ArrayList<?> list){}
    // 泛型的上限: 此时的泛型?,必须是Number类型或者Number类型的子类
    public static void getElement1(ArrayList<? extends Number> list){}
    // 泛型的下限: 此时的泛型?,必须是Number类型或者Number类型的父类
    public static void getElement2(ArrayList<? super Number> list){}

}

六、数据结构

6.1 概述：

数据结构是计算机存储、组织数据的方式。是指相互之间存在一种或多种特定关系的数据元素的集合通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率

常用的数据结构有：数组，栈，链表，队列，树，图，堆，散列表等，如图所示：

6.2 栈

栈结构（弹夹形式）：先进后出

6.3 队列

队列结构（购票形式）：先进先出

6.4 数组

查询快、增删慢

6.5 链表

查询慢、增删快（相对于数组）

6.6 树

6.6.1 二叉树

6.6.2 二叉树查找树

6.6.1 平衡二叉树

6.6.1 红黑树

七、Set 接口

7.1 概述

Set 接口是 Collection 接口的子接口，Set 接口没有提供额外的方法。
Set 集合不允许包含相同的元素，如果试着将两个相同的元素加入同一个 Set 集合中，则会添加失败（不会抛出异常）。
Set 判断两个对象是否相同不是使用==运算符，而是根据 equals方法。
Set 集合支持的遍历方式和 Collection 集合一样：foreach 和 Iterator。
没有索引,不能使用普通for循环遍历
Set 的常用实现类：HashSet 、TreeSet 、LinkedHashSet 。

示例：

public class Test {
 public static void main(String[] args) {
     Set<String> set = new HashSet<>();

     set.add("aa");
     set.add("bb");
     set.add("cc");
     set.add("aa");

     System.out.println("set = " + set); // set = [aa, bb, cc]

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

     // foreach
     for (String s : set) {
         System.out.println(s);
     }

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

     // iterator
     for (Iterator<String> iterator = set.iterator(); iterator.hasNext();) {
         String next = iterator.next();
         System.out.println(next);
     }
 }
}

7.2 Set 的实现类之一：TreeSet

7.2.1 概述

TreeSet 是 SortedSet 接口的实现类，TreeSet 可以确保集合元素处于排序状态。
TreeSet 底层使用红黑树结构存储数据，在内部使用的是 TreeMap 来实现的。
不可以存储重复元素
没有索引
可以将元素按照规则进行排序
- TreeSet()：根据其元素的自然排序进行排序
- TreeSet(Comparator comparator) ：根据指定的比较器进行排序

TreeSet 有两种排序方法：自然排序和定制排序。默认情况下，TreeSet 采用自然排序。

7.2.2 自然排序

自然排序：TreeSet 会调用集合元素的**compareTo(Object obj)**方法来比较元素之间的大小关系，然后将集合元素按升序（默认情况）排列。
如果视图将一个对象添加到 TreeSet 中，则该对象所属的类必须实现**Comparable **接口。
Comparable 的实现：
- BigDecimal 、BigInteger 以及所有的数值型对应的包装类：按照它们对应的数值大小进行比较。
- Character ：按照字符的 Unicode 值进行比较。
- Boolean ：true 对应的包装类实例大于 false 对应的包装类实例。
- String ：按照字符串中字符的 Unicode 值进行比较。
- Date 、Time ：后面的时间、日期比前面的时间、日期大。

示例：

public class Test {
 public static void main(String[] args) {
     Set<String> set = new TreeSet<>();

     set.add("g");
     set.add("b");
     set.add("d");
     set.add("c");
     set.add("f");

     System.out.println("set = " + set); // set = [b, c, d, f, g]
 }
}

7.2.2.1 自然排序Comparable的使用

案例需求
- 存储学生对象并遍历，创建TreeSet集合使用无参构造方法
- 要求：按照年龄从小到大排序，年龄相同时，按照姓名的字母顺序排序
实现步骤
1. 使用空参构造创建TreeSet集合
  - 用TreeSet集合存储自定义对象，无参构造方法使用的是自然排序对元素进行排序的
2. 自定义的Student类实现Comparable接口
  - 自然排序，就是让元素所属的类实现Comparable接口，重写compareTo(T o)方法
3. 重写接口中的compareTo方法
  - 重写方法时，一定要注意排序规则必须按照要求的主要条件和次要条件来写
代码实现：

学生类

public class Student implements Comparable<Student>{
    private String name;
    private int age;

    public Student() {
    }

    public Student(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 String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
    public int compareTo(Student o) {
        //按照对象的年龄进行排序
        //主要判断条件: 按照年龄从小到大排序
        int result = this.age - o.age;
        //次要判断条件: 年龄相同时，按照姓名的字母顺序排序
        result = result == 0 ? this.name.compareTo(o.getName()) : result;
        return result;
    }
}

测试类：

public class MyTreeSet2 {
    public static void main(String[] args) {
        //创建集合对象
        TreeSet<Student> ts = new TreeSet<>();
        //创建学生对象
        Student s1 = new Student("zhangsan",28);
        Student s2 = new Student("lisi",27);
        Student s3 = new Student("wangwu",29);
        Student s4 = new Student("zhaoliu",28);
        Student s5 = new Student("qianqi",30);
        //把学生添加到集合
        ts.add(s1);
        ts.add(s2);
        ts.add(s3);
        ts.add(s4);
        ts.add(s5);
        //遍历集合
        for (Student student : ts) {
            System.out.println(student);
        }
    }
}

结果：

Student{name='lisi', age=27}
Student{name='zhangsan', age=28}
Student{name='zhaoliu', age=28}
Student{name='wangwu', age=29}
Student{name='qianqi', age=30}

7.2.2.2 自然排序原理图

如果返回值为负数，表示当前存入的元素是较小值，
存左边如果返回值为0，表示当前存入的元素跟集合中元素重复了，不存
如果返回值为正数，表示当前存入的元素是较大值，存右边

7.2.3 定制排序

定制排序，通过 Comparator 接口来实现。需要重写 **compare(T o1,T o2) **方法。
利用** int compare(T o1,T o2) **方法，比较 o1 和 o2 的大小：
- 如果方法返回正整数，则表示 o1 大于 o2 ；
- 如果返回 0 ，表示相等；
- 返回负整数，表示 o1 小于 o2 。
要实现定制排序，需要将实现 Comparator 接口的实例作为形参传递给 TreeSet 的构造器。
使用定制排序判断两个元素相等的标准是：通过 Comparator 比较两个元素返回了 0 。

7.2.3.1 比较器排序Comparator的使用

案例需求
- 存储老师对象并遍历，创建TreeSet集合使用带参构造方法
- 要求：按照年龄从小到大排序，年龄相同时，按照姓名的字母顺序排序
实现步骤
- 用TreeSet集合存储自定义对象，带参构造方法使用的是比较器排序对元素进行排序的
- 比较器排序，就是让集合构造方法接收Comparator的实现类对象，重写compare(T o1,T o2)方法
- 重写方法时，一定要注意排序规则必须按照要求的主要条件和次要条件来写

代码实现

public class Teacher {
 private String name;
 private int age;

 public Teacher() {
 }

 public Teacher(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 String toString() {
     return "Teacher{" +
             "name='" + name + '\'' +
             ", age=" + age +
             '}';
 }
}

public class MyTreeSet4 {
 public static void main(String[] args) {
       //创建集合对象
     TreeSet<Teacher> ts = new TreeSet<>(new Comparator<Teacher>() {
         @Override
         public int compare(Teacher o1, Teacher o2) {
             //o1表示现在要存入的那个元素
             //o2表示已经存入到集合中的元素

             //主要条件
             int result = o1.getAge() - o2.getAge();
             //次要条件
             result = result == 0 ? o1.getName().compareTo(o2.getName()) : result;
             return result;
         }
     });
     //创建老师对象
     Teacher t1 = new Teacher("zhangsan",23);
     Teacher t2 = new Teacher("lisi",22);
     Teacher t3 = new Teacher("wangwu",24);
     Teacher t4 = new Teacher("zhaoliu",24);
     //把老师添加到集合
     ts.add(t1);
     ts.add(t2);
     ts.add(t3);
     ts.add(t4);
     //遍历集合
     for (Teacher teacher : ts) {
         System.out.println(teacher);
     }
 }
}

7.2.4 两种排序总结

两种比较方式小结

自然排序: 自定义类实现Comparable接口,重写compareTo方法,根据返回值进行排序
比较器排序: 创建TreeSet对象的时候传递Comparator的实现类对象,重写compare方法,根据返回值进行排序
在使用的时候,默认使用自然排序,当自然排序不满足现在的需求时,必须使用比较器排序

7.3 Set 的实现类之二：HashSet

HashSet 是 Set 接口的典型实现，大多数时候使用 Set 集合的时候都使用这个实现类。
HashSet 按照 Hash 算法来存储集合中的元素，因此具有很好的存取、查找、删除性能。
HashSet 的底层实现原理是哈希表，在内部使用的是 HashMap 来实现的。
HashSet 具有以下的特点：
- ① 不能保证元素的顺序（元素存储顺序和取出顺序不一定相同）。
- ② HashSet 不是线程安全的。
- ③ 集合元素可以为 null 。
- ④ 没有索引，不能使用for循环
- ⑤ 不可以存储重复元素
HashSet集合判断两个元素相等的标准：两个对象的 hashCode() 方法比较相等，并且两个对象的 equals() 方法返回值也相等。

基本使用示例：

public class HashSetDemo {
 public static void main(String[] args) {
     //创建集合对象
     HashSet<String> set = new HashSet<String>();

     //添加元素
     set.add("hello");
     set.add("world");
     set.add("java");
     //不包含重复元素的集合
     set.add("world");

     //遍历
     for(String s : set) {
         System.out.println(s);
     }
 }
}

7.3.1 哈希值

哈希值简介
是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值
如何获取哈希值
Object类中的public int hashCode()：返回对象的哈希码值
哈希值的特点
- 如果没有重写hashCode方法，那么是根据对象的地址值计算出的哈希值
  同一个对象多次调用hashCode()方法返回的哈希值是相同的
  不同对象的哈希值是不一样的
- 如果重写的hashCode方法，一般是通过对象的属性值计算出哈希值。
  如果不同对象的属性值是一样的，那么计算出来的哈希值也是一样的
- 默认情况下，不同对象的哈希值是不同的。而重写hashCode()方法，可以实现让不同对象的哈希值相同
  7.3.2 哈希表结构
  JDK1.8以前
  底层采用数组 + 链表实现
  
  JDK1.8以后
节点个数少于等于8个
数组 + 链表
节点个数多于8个
数组 + 红黑树

7.4 Set 的实现类之二：LinkedHashSet

LinkedHashSe t是 HashSet 的子类。
LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，但是它同时使用双向链表维护元素的次序，这使得元素看起来是以插入顺序保存的。
LinkedHashSet 的插入性能略低于 HashSet ，但是在迭代访问Set里面的全部元素的时候有很好的性能。
LinkedHashSet 不允许集合元素重复。

示例：

public class Test {
 public static void main(String[] args) {
     Set<String> set = new LinkedHashSet<>();

     set.add("aa");
     set.add("cc");
     set.add("bb");
     set.add("aa");

     System.out.println("set = " + set); // [aa, cc, bb]
 }
}

八、Collections 工具类

8.1 概述

Collections 是一个操作 Set 、List 和 Map 等集合的工具类。
Collections 中提供了一系列的静态的方法对集合元素进行排序、查询和修改等操作，还提供了对集合对象设置不可变、对集合对象实现同步控制等方法。

8.2 常用方法

反转 List 中元素的顺序：

public static void reverse(List<?> list) {}

对 List 集合中的元素进行随机排序：
```
public static void shuffle(List<?> list) {}
```

根据元素的自然顺序对 List 集合中的元素进行排序：

public static <T extends Comparable<? super T>> void sort(List<T> list) {}

根据指定的 Comparator 对 List 集合元素进行排序：

public static <T> void sort(List<T> list, Comparator<? super T> c) {}

根据元素的自然顺序，返回给定集合中的最大元素：

public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) {}

根据指定的 Comparator，返回给定集合中的最大元素：

public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp) {}

根据元素的自然顺序，返回给定集合中的最小元素：

public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll) {}

根据指定的 Comparator，返回给定集合中的最小元素：

public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp) {}

返回指定集合中指定元素出现的次数：

public static int frequency(Collection<?> c, Object o) {}

集合元素的复制：

public static <T> void copy(List<? super T> dest, List<? extends T> src) {}

使用新值替换 List 集合中的所有旧值：

public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal) {}

示例：

public class Test {
  public static void main(String[] args) {
      List<String> list = new ArrayList<>();

      list.add("aa");
      list.add("dd");
      list.add("hh");
      list.add("bb");

      System.out.println("list = " + list); // list = [aa, dd, hh, bb]

      Collections.reverse(list);

      System.out.println("list = " + list); // list = [bb, hh, dd, aa]

      String max = Collections.max(list);
      System.out.println("max = " + max); // max = hh

      int gg = Collections.binarySearch(list, "gg");
      System.out.println("gg = " + gg); // gg = -2

  }
}

8.3 Collections 的同步控制方法

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

将 Collection 集合转换为线程安全的集合：

public static <T> Collection<T> synchronizedCollection(Collection<T> c) {}

将 Set 集合转换为线程安全的集合：

public static <T> Set<T> synchronizedSet(Set<T> s) {}

将 List 集合转换为线程安全的集合：

public static <T> List<T> synchronizedList(List<T> list) {}

将 Map 集合转换为线程安全的集合：

public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {}

示例：

public class Test {
  public static void main(String[] args) {
      List<String> list = Collections.synchronizedList(new ArrayList<>());

      list.add("aa");
      list.add("bb");
      list.add("cc");
      list.add("dd");
      list.add("ee");

      System.out.println("list = " + list);
  }
}

九、Map 接口

9.1 概述

Map 和 Collection 并列存在。用于保存具有映射关系的数据：**key - value **。
Map 中的 key 和 value 可以是任何引用类型的数据。通常情况下，使用 String 作为 Map 的 key 。
Map 中的 key 和 value 之间存在单向一对一的关系，即通过指定的 key 能找到唯一的、确定的 value
Map 中的 key不允许重复，值可以重复，即同一个 Map 对象所对应的类，必须重写 equals() 和 hashCode() 方法。
(键+值)这个整体我们称之为”键值对“或者”键值对对象“，在Java 中叫做”Entry对象“
```
interface Map<K,V>  K：键的类型；   V：值的类型
```
Map 接口的常用实现类：HashMap 、TreeMap 、LinkedHashMap 和 Properties 。其中，HashMap 是 Map 接口使用频率最高的实现类。

集合 - 图24

9.2 Map 接口常用的方法

9.2.1 Map集合的基本功能

方法名	说明
V put(K key,V value)	添加元素
void putAll(Map<? extends K, ? extends V> m)	将 m 中所有的 key - value 存放到当前的 Map 对象中：
V remove(Object key)	根据键删除键值对元素
void clear()	移除所有的键值对元素
boolean containsKey(Object key)	判断集合是否包含指定的键
boolean containsValue(Object value)	判断集合是否包含指定的值
boolean isEmpty()	判断集合是否为空
int size()	集合的长度，也就是集合中键值对的个数

示例代码：

public class MapDemo02 {
    public static void main(String[] args) {
        //创建集合对象
        Map<String,String> map = new HashMap<String,String>();

        //V put(K key,V value)：添加元素
        map.put("张无忌","赵敏");
        map.put("郭靖","黄蓉");
        map.put("杨过","小龙女");

        //V remove(Object key)：根据键删除键值对元素
        //System.out.println(map.remove("郭靖"));
        //System.out.println(map.remove("郭襄"));

        //void clear()：移除所有的键值对元素
        //map.clear();

        //boolean containsKey(Object key)：判断集合是否包含指定的键
//        System.out.println(map.containsKey("郭靖"));
//        System.out.println(map.containsKey("郭襄"));

        //boolean isEmpty()：判断集合是否为空
//        System.out.println(map.isEmpty());

        //int size()：集合的长度，也就是集合中键值对的个数
        System.out.println(map.size());

        //输出集合对象
        System.out.println(map);
    }
}

注意：如果添加的键不存在，那么会把键值对都添加到集合中
如果添加的键是存在的，那么会覆盖原先的值，把原先值当做返回值进行返回

9.2.2 Map集合的获取功能

V get(Object key);	根据指定的 key 获取对应的 value ：
Set keySet();	返回所有 key 构成的 Set 集合
Collection values();	返回所有 value 构成的 Collection 集合
Set> entrySet();	返回所有 key - value 构成的 Set 集合：

public class MapDemo03 {
    public static void main(String[] args) {
        //创建集合对象
        Map<String, String> map = new HashMap<String, String>();

        //添加元素
        map.put("张无忌", "赵敏");
        map.put("郭靖", "黄蓉");
        map.put("杨过", "小龙女");

        //V get(Object key):根据键获取值
//        System.out.println(map.get("张无忌"));
//        System.out.println(map.get("张三丰"));

        //Set<K> keySet():获取所有键的集合
//        Set<String> keySet = map.keySet();
//        for(String key : keySet) {
//            System.out.println(key);
//        }

        //Collection<V> values():获取所有值的集合
        Collection<String> values = map.values();
        for(String value : values) {
            System.out.println(value);
        }
    }
}

9.3 Map 集合的遍历方式

9.3.1 Map集合的遍历1—entrySet方式

遍历思路
- 我们刚才存储的元素都是成对出现的，所以我们把Map看成是一个夫妻对的集合
  - 获取所有结婚证的集合
  - 遍历结婚证的集合，得到每一个结婚证
  - 根据结婚证获取丈夫和妻子
步骤分析
- 获取所有键值对对象的集合
  - **Set<Map.Entry<K,V>> entrySet()**：获取所有键值对对象的集合
- 遍历键值对对象的集合，得到每一个键值对对象
  - 用增强for实现，得到每一个Map.Entry
- 根据键值对对象获取键和值
  - 用getKey()得到键
  - 用getValue()得到值

代码实现

public class MapDemo02 {
 public static void main(String[] args) {
     //创建集合对象
     Map<String, String> map = new HashMap<String, String>();

     //添加元素
     map.put("张无忌", "赵敏");
     map.put("郭靖", "黄蓉");
     map.put("杨过", "小龙女");

     //获取所有键值对对象的集合
     Set<Map.Entry<String, String>> entrySet = map.entrySet();
     //遍历键值对对象的集合，得到每一个键值对对象
     for (Map.Entry<String, String> me : entrySet) {
         //根据键值对对象获取键和值
         String key = me.getKey();
         String value = me.getValue();
         System.out.println(key + "," + value);
     }
 }
}

9.3.2 Map集合的遍历—keySet方式

遍历思路
- 我们刚才存储的元素都是成对出现的，所以我们把Map看成是一个夫妻对的集合
  - 把所有的丈夫给集中起来
  - 遍历丈夫的集合，获取到每一个丈夫
  - 根据丈夫去找对应的妻子
步骤分析
- 获取所有键的集合。用keySet()方法实现
- 遍历键的集合，获取到每一个键。用增强for实现
- 根据键去找值。用get(Object key)方法实现

代码实现

public class MapDemo01 {
 public static void main(String[] args) {
     //创建集合对象
     Map<String, String> map = new HashMap<String, String>();

     //添加元素
     map.put("张无忌", "赵敏");
     map.put("郭靖", "黄蓉");
     map.put("杨过", "小龙女");

     //获取所有键的集合。用keySet()方法实现
     Set<String> keySet = map.keySet();
     //遍历键的集合，获取到每一个键。用增强for实现
     for (String key : keySet) {
         //根据键去找值。用get(Object key)方法实现
         String value = map.get(key);
         System.out.println(key + "," + value);
     }
 }
}

keySet其实是遍历了2次，一次是转为Iterator对象，另一次是从hashMap中取出key所对应的value，效率较低。

9.3.3 通过Iterator迭代器遍历循环Map.entrySet().iterator();

Map<String,String> map = new HashMap<>(3);
    map.put("111", "aaa");
    map.put("222", "bbb");
    map.put("333", "ccc");
    Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
    while (it.hasNext()) {
        Map.Entry<String, String> entry = it.next();
        System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
    }

9.3.3 如果是 JDK 8，推荐使用Map.foreach 方法。

    Map<String,String> map = new HashMap<>(3);
    map.put("111", "aaa");
    map.put("222", "bbb");
    map.put("333", "ccc");
    map.forEach((k,v)->{System.out.println(k + v);});

9.4 Map 的实现类之一：HashMap

7.2.1 概述

HashMap 是 Map 接口使用频率较高的实现类。
允许使用 null 键和 null 值，和 HashSet 一样，不能保证映射的顺序。
所有的 key 构成的集合是 Set：不重复的。所以，key 所在的类需要重写 equals() 和 hashCode() 方法。
所有的 value 构成的集合是 Collection：可以重复的。所以，value 所在的类需要重写 equals() 方法。
一个 key - value 构成一个 entry 。
HashMap 判断两个 key 相等的标准：两个 key 的 hashCode() 和 equals() 分别都相等。
HashMap 判断两个 value 相等的标准：两个 value 的 equals() 相等。
7.2.2 HashMap 的成员变量

哈希表数组的初始化容量：

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;

7.2.3 HashMap 的内部类Node

```java public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {

// Node节点 static class Node implements Map.Entry {

  final int hash; // 对象的hash值
  final K key; // 存储对象
  V value; // 使用Set的时候，是Object的对象
  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;
  }

}

…

}



<a name="GZYBI"></a>
### 7.2.4 HashMap 的 put 方法
```java
// HashMap存储对象的方法
public V put(K key, V value) {
    // 存储值 参数：传递新计算的hash值，要存储的元素
    return putVal(hash(key), key, value, false, true);
}

/**
* 存储值
* @param hash 重新计算的hash值
* @param key 键
* @param value 值
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // Node类型的数组；Node类型的节点；n，i
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // tab = Node[] = null
    if ((tab = table) == null || (n = tab.length) == 0)
        // n = (tab数组 = resize()扩容后返回的数组）的长度，默认为16
        n = (tab = resize()).length;
    // (n - 1) & hash：数组的长度-1 & hash，确定存储的位置
    // 判断数组的索引上是不是null，并赋值给p
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 数组的索引 = 赋值新的节点对象
        tab[i] = newNode(hash, key, value, null);
    else { // 数组的索引不为null，说明，要存储的对象已经有了
        Node<K,V> e; K k;
        // 判断已经存在的对象和要存储对象的hash值、equals方法
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else { // 遍历该索引下的链表，和每个元素比较hashCode和equals，替换
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

// 将存储的对象，再次计算哈希值
// 尽量降低哈希值的碰撞
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 数组的扩容
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

7.2.5 JDK 7 和 JDK 8 的 HashMap 的区别

JDK7 及以前版本：HashMap 是数组+链表结构。

集合 - 图25

JDK8 ：HashMap 是数组+链表+红黑树。

集合 - 图26
链表转红黑树的条件：

① 链表长度 > 8 。
② 数组长度 > 64 。

红黑树转链表的条件：链表的长度 < 6 。

9.2.6 HashMap集合应用案例

案例需求

创建一个HashMap集合，键是学生对象(Student)，值是居住地 (String)。存储多个元素，并遍历。
要求保证键的唯一性：如果学生对象的成员变量值相同，我们就认为是同一个对象

代码实现：

public class Student {
    private String name;
    private int age;

    public Student() {
    }

    public Student(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;

        Student student = (Student) o;

        if (age != student.age) return false;
        return name != null ? name.equals(student.name) : student.name == null;
    }

    @Override
    public int hashCode() {
        int result = name != null ? name.hashCode() : 0;
        result = 31 * result + age;
        return result;
    }
}

测试类

public class HashMapDemo {
    public static void main(String[] args) {
        //创建HashMap集合对象
        HashMap<Student, String> hm = new HashMap<Student, String>();

        //创建学生对象
        Student s1 = new Student("林青霞", 30);
        Student s2 = new Student("张曼玉", 35);
        Student s3 = new Student("王祖贤", 33);
        Student s4 = new Student("王祖贤", 33);

        //把学生添加到集合
        hm.put(s1, "西安");
        hm.put(s2, "武汉");
        hm.put(s3, "郑州");
        hm.put(s4, "北京");

        //遍历集合
        Set<Student> keySet = hm.keySet();
        for (Student key : keySet) {
            String value = hm.get(key);
            System.out.println(key.getName() + "," + key.getAge() + "," + value);
        }
    }
}

9.5 Map 的实现类之二：LinkedHashMap

LinkedHashMap 是 HashMap 的子类。
在 HashMap 存储结构的基础上，使用了一对双向链表来记录添加元素的顺序。
和 LinkedHashSet 类似，LinkedHashMap 可以维护 Map 的迭代顺序：迭代顺序和 key - value 对的插入顺序一致。

示例：

public class Test {
 public static void main(String[] args) {
     Map<String, Integer> map = new LinkedHashMap<>();

     map.put("张三", 18);
     map.put("李四", 19);
     map.put("王五", 20);
     map.put("赵六", 21);

     for (Map.Entry<String, Integer> entry : map.entrySet()) {
         String key = entry.getKey();
         Integer value = entry.getValue();
         System.out.println("key：" + key + "，value：" + value);
     }
 }
}

9.6 Map 的实现类之三：Hashtable

Hashtable 是个古老的 Map 实现类，JDK1.0 就提供了。不同于 HashMap ，Hashtable 是线程安全的。
Hashtable 的实现原理和 HashMap 相同，功能相同。底层都是使用哈希表结构，查询速度快，很多情况下可以互用。
和 HashMap 不同的是，Hashtable 不允许使用 null 作为 key 和 value 。
和 HashMap 相同的是，Hashtable 不能保证 key - value 对的顺序。
Hashtable 判断两个 key 相等、两个 value 相等的标准，与 HashMap 一致。

9.7 Map 的实现类之四：TreeMap

TreeMap 存储 Key - Value 对时，需要根据 key - value 对进行排序。
TreeMap 可以保证所有的 key - value 对处于有序状态。
TreeMap 底层使用红黑树结构存储数据。
TreeMap 的 key 的排序：
- 自然排序：TreeMap 的所有的 key 必须实现 Comparable 接口，而且所有的 key 应该是同一个类的对象，否则将会抛出 ClasssCastException 。
- 定制排序：创建 TreeMap 时，传入一个Comparator 对象，该对象负责对TreeMap中的所有key进行排序。此时不需要 Map 的 key 实现 Comparable 接口。
TreeMap 判断两个 key 相等的标准：两个 key 通过 compareTo() 方法或者 compare() 方法返回 0 。

示例1：

public class Test {
 public static void main(String[] args) {
     Map<String, Integer> map = new TreeMap<>();

     map.put("c", 25);
     map.put("h", 18);
     map.put("a", 21);
     map.put("b", 98);

     System.out.println("map = " + map);
 }
}

示例2：
- 创建一个TreeMap集合,键是学生对象(Student),值是籍贯(String),学生属性姓名和年龄,按照年龄进行排序并遍历
- 要求按照学生的年龄进行排序,如果年龄相同则按照姓名进行排序

代码实现

public class Student implements Comparable<Student>{
  private String name;
  private int age;

  public Student() {
  }

  public Student(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 String toString() {
      return "Student{" +
              "name='" + name + '\'' +
              ", age=" + age +
              '}';
  }

  @Override
  public int compareTo(Student o) {
      //按照年龄进行排序
      int result = o.getAge() - this.getAge();
      //次要条件，按照姓名排序。
      result = result == 0 ? o.getName().compareTo(this.getName()) : result;
      return result;
  }
}

public class Test1 {
  public static void main(String[] args) {
        // 创建TreeMap集合对象
      TreeMap<Student,String> tm = new TreeMap<>();

      // 创建学生对象
      Student s1 = new Student("xiaohei",23);
      Student s2 = new Student("dapang",22);
      Student s3 = new Student("xiaomei",22);

      // 将学生对象添加到TreeMap集合中
      tm.put(s1,"江苏");
      tm.put(s2,"北京");
      tm.put(s3,"天津");

      // 遍历TreeMap集合,打印每个学生的信息
      tm.forEach(
              (Student key, String value)->{
                  System.out.println(key + "---" + value);
              }
      );
  }
}

示例3:

  public class Test {
  public static void main(String[] args) {
      Map<Person, String> map = new TreeMap<>(new Comparator<Person>() {
          @Override
          public int compare(Person o1, Person o2) {
              return o1.getAge() - o2.getAge();
          }
      });

      map.put(new Person("张三", 18), "大一");
      map.put(new Person("李四", 20), "大一");
      map.put(new Person("王五", 19), "大二");
      map.put(new Person("赵六", 23), "大四");
      map.put(new Person("田七", 17), "大一");

      System.out.println("map = " + map);
  }
}

9.8 Map 的实现类之五：Properties

Properties 类是 Hashtable 的子类，该对象是用来处理属性文件的。
由于属性文件的 key 和 value 都是字符串类型，所以 Properties 里的 key 和 value 都是字符串类型。
存取数据的时候，建议使用 setProperty和 getProperty 方法。

示例：

public class Test {
 public static void main(String[] args) {
     Properties properties = new Properties();

     properties.setProperty("hello", "你好");
     properties.setProperty("world", "世界");

     String hello = properties.getProperty("hello");
     System.out.println("hello = " + hello);

     String world = properties.getProperty("world");
     System.out.println("world = " + world);

     Enumeration<?> enumeration = properties.propertyNames();
     while (enumeration.hasMoreElements()) {
         Object key = enumeration.nextElement();
         Object value = properties.get(key);
         System.out.println("key = " + key + "，value = " + value);
     }

     for (String name : properties.stringPropertyNames()) {
         String property = properties.getProperty(name);
         System.out.println("key = " + name + "，value = " + property);
     }
 }
}

集合

一、集合概述

集合类体系结构

二、Collection 接口

2.1 Collection集合概述

2.2 Collection集合常用方法

三、Iterator 迭代器

3.1 Iterator 接口

3.2 迭代器实现原理

3.3 使用 Iterator 迭代器删除元素

3.4 并发修改异常（ ConcurrentModificationException ）

3.6 增强for循环

3.7 java.lang.Iterable 接口

3.8 小结

四、List 接口

4.1 概述

4.2 List集合的特有方法

4.2.1 添加元素

4.2.2 获取元素

4.2.3 获取元素索引

4.2.4 删除元素

4.2.5 替换元素

4.3 List 特有的迭代器 ListIterator（了解）

4.4 List接口实现类之-ArrayList

4.4.1 概述

4.4.2 ArrayList的类成员变量

4.4.3 ArrayList 类的构造方法

4.4.4 ArrayList 类的 add 方法

4.4.5 ArrayList 类的 get 方法

4.4.6 ArrayList 类的 set 方法

4.4.7 ArrayList 类的 remove 方法

4.4.8 ArrayList类方法总结

4.4.9 ArrayList存储字符串并遍历

4.4.10 ArrayList存储学生对象并遍历

4.4.11 键盘录入学生信息到集合

4.4.12 ArrayList扩容

4.5 List接口实现类之-LinkList

4.5.1 概述

4.5.2 LinkedList 集合特有方法

4.5.3 LinkedList 的类成员变量

4.5.4 LinkedList 的成员内部类 Node

4.5.5 LinkedList 类的 add 方法

五、泛型

5.1 泛型的概述

5.1.1 泛型设计的背景

5.1.2 泛型概念

5.1.3 为什么要有泛型？

5.1.4 泛型的相关名词

5.2 自定义泛型结构

5.2.1 概述

5.2.2 泛型类【应用】

5.2.3 泛型接口【应用】

5.2.4 泛型类泛型接口使用

5.2.5 类型变量的上限

5.2.6 泛型擦除

5.2.7 泛型方法【应用】

5.3 类型通配符

5.3.1 <?> 任意类型

5.3.2 <? extends 类型> 类型通配符上限

5.3.3 <? super类型> 类型通配符下限

六、数据结构

6.1 概述：

6.2 栈

6.3 队列

6.4 数组

6.5 链表

6.6 树

6.6.1 二叉树

6.6.2 二叉树查找树

6.6.1 平衡二叉树

6.6.1 红黑树

七、Set 接口

7.1 概述

7.2 Set 的实现类之一：TreeSet

7.2.1 概述

7.2.2 自然排序

7.2.2.1 自然排序Comparable的使用

7.2.2.2 自然排序原理图

7.2.3 定制排序

7.2.3.1 比较器排序Comparator的使用

5.3.1 `<?>` 任意类型

5.3.2 `<? extends 类型>` 类型通配符上限

5.3.3 `<? super类型>` 类型通配符下限