集合体系结构、Collection集合、List、ArrayList、LinkedList、Set、TreeSet、HashSet、LinkedHashSet；Map、HashMap、TreeMap、Collections类

一、集合框架

1.1 概述

所有的集合类和集合接口都在java.util包下；

在内存中申请一块空间用来存储数据，在Java中集合就是替换掉定长数组的一种引用数据类型。

1.2 数组和集合的区别

• 相同点

  都是容器,可以存储多个数据

• 不同点

  • 存储方式：数组使用连续的内存空间来存储元素，并且每个元素在数组中的位置（索引）是固定的。数组的索引通常是整数，从0开始；集合（如Java中的List、Set、Queue等）则不一定使用连续的内存空间，它们通常通过引用和指针来管理元素，并且元素的顺序（对于某些集合如List）或唯一性（如Set）可能有所不同
  • 长度/大小：数组的长度是不可变的，长度不够用、或者开辟很大的长度会导致空间浪费，虽然有些编程语言允许动态数组（如Java中的ArrayList），但它们实际上是通过在需要时创建新的更大数组并复制元素来实现的；集合的大小通常是动态的，可以随着元素的添加和删除而改变
  • 元素类型：数组可以存基本数据类型和引用数据类型，其元素类型在创建时就必须确定，并且整个数组中的所有元素都必须是同一类型；集合只能存引用数据类型（对象的内存地址），如果要存基本数据类型，需要存对应的包装类，list.add(18) 自动装箱，集合中可以存储不同类型数据（一般情况下也只存储同一种类型的数据）
  • 方法区别：数组中提供的方法非常有限，添加、删除、插入等操作 效率很低（为了保证元素的内存地址连续，添加或删除元素时，涉及到前移或者后移），无法获取数据中实际元素的个数；
  • 数组存储数据的特点——有序、可重复，对于无序、不可重复的需求，不能满足；

1.3 Java集合框架体系

1.4 数据结构

常见的数据结构：栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树

每种数据结构长什么样子？如何添加数据？如何删除数据？

1.4.1 栈、队列、数组、队列

• 栈结构：先进后出
• 队列结构：先进先出
• 数组结构：查询快、增删慢
• 队列结构：查询快、增删快

1.4.2 二叉树【理解】

• 二叉树的特点

  • 二叉树中,任意一个节点的度要小于等于2
    • 节点: 在树结构中,每一个元素称之为节点
    • 度: 每一个节点的子节点数量称之为度

• 二叉树结构图

  

1.4.3 二叉查找树【理解】

• 二叉查找树的特点

  • 二叉查找树,又称二叉排序树或者二叉搜索树
  • 每一个节点上最多有两个子节点
  • 左子树上所有节点的值都小于根节点的值
  • 右子树上所有节点的值都大于根节点的值

• 二叉查找树结构图

  

• 二叉查找树和二叉树对比结构图

  

• 二叉查找树添加节点规则

  • 小的存左边
  • 大的存右边
  • 一样的不存

  

1.4.4 平衡二叉树【理解】

• 平衡二叉树的特点

  • 二叉树左右两个子树的高度差不超过1
  • 任意节点的左右两个子树都是一颗平衡二叉树

• 平衡二叉树旋转

  • 旋转触发时机

    • 当添加一个节点之后，该树不再是一颗平衡二叉树

  • 左旋

    • 就是将根节点的右侧往左拉，原先的右子节点变成新的父节点，并把多余的左子节点出让，给已经降级的根节点当右子节点

    

    

  • 右旋

    • 就是将根节点的左侧往右拉，左子节点变成了新的父节点，并把多余的右子节点出让，给已经降级根节点当左子节点

      

      

• 平衡二叉树和二叉查找树对比结构图

  

• 平衡二叉树旋转的四种情况

  • 左左

    • 左左: 当根节点左子树的左子树有节点插入，导致二叉树不平衡

    • 如何旋转: 直接对整体进行右旋即可

      

  • 左右

    • 左右: 当根节点左子树的右子树有节点插入，导致二叉树不平衡

    • 如何旋转: 先在左子树对应的节点位置进行左旋，在对整体进行右旋

      

  • 右右

    • 右右: 当根节点右子树的右子树有节点插入，导致二叉树不平衡

    • 如何旋转: 直接对整体进行左旋即可

      

  • 右左

    • 右左:当根节点右子树的左子树有节点插入，导致二叉树不平衡

    • 如何旋转: 先在右子树对应的节点位置进行右旋，在对整体进行左旋

      

1.4.5 红黑树【理解】

红黑树（Red Black Tree）：也是一种自平衡的二叉搜索树(BST)，之前叫做平衡二叉B树（Symmetric Binary B-Tree）。

红黑树的时间复杂度：查找、添加、删除都是O(logn)

• 红黑树的特点

  • 平衡二叉B树
  • 每一个节点可以是红或者黑
  • 红黑树不是高度平衡的，它的平衡是通过"自己的红黑规则"进行实现的

• 红黑树的红黑规则有哪些（在添加或删除节点的时候，如果不符合这些性质会发生旋转，以达到所有的性质）

  1. 每一个节点或是红色的，或者是黑色的

  2. 根节点必须是黑色

  3. 如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，每个叶节点(Nil)是黑色的空节点

  4. 如果某一个节点是红色，那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)

  5. 对每一个节点,从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点

     

• 红黑树添加节点的默认颜色

  • 添加节点时，默认为红色，效率高

• 红黑树添加节点后如何保持红黑规则

  • 根节点位置
    • 直接变为黑色
  • 非根节点位置
    • 父节点为黑色
      • 不需要任何操作，默认红色即可
    • 父节点为红色
      • 叔叔节点为红色
        1. 将"父节点"设为黑色，将"叔叔节点"设为黑色
        2. 将"祖父节点"设为红色
        3. 如果"祖父节点"为根节点，则将根节点再次变成黑色
      • 叔叔节点为黑色
        1. 将"父节点"设为黑色
        2. 将"祖父节点"设为红色
        3. 以"祖父节点"为支点进行旋转

1.5 泛型

• 泛型的介绍

  ​ 泛型是JDK5中引入的特性，它提供了编译时类型安全检测机制

• 泛型的好处

  1. 把运行时期的问题提前到了编译期间
  2. 避免了强制类型转换

• 泛型的定义格式

  • <类型>: 指定一种类型的格式.尖括号里面可以任意书写,一般只写一个字母.例如:
  • <类型1,类型2…>: 指定多种类型的格式,多种类型之间用逗号隔开.例如: <E,T> <K,V>

• 泛型的细节

  • 泛型中不能写基本数据类型
  • 指定泛型的具体类型后，传递数据时 可以传入该类类型或者其子类类型
  • 如果不写泛型，类型默认是Object

伪泛型：存入集合内部是Object，基本数据类型无法转Object

二、Collection集合

红色的是接口，蓝色的是实现类；List的有序 指的是存和取的顺序是一样的

2.1 Collection 集合概述和使用【应用】

• Collection集合概述

  • 是单例集合的顶层接口，它表示一组对象，这些对象也称为Collection的元素。
  • JDK 不提供此接口的任何直接实现。它提供更具体的子接口(如Set和List)实现

• 创建Collection集合的对象

  • 多态的方式
  • 具体的实现类ArrayList

• Collection集合常用方法。（由于是单例集合的顶层接口）它的功能是全部单列集合都可以继承使用的。

方法名	说明
boolean add(E e)	添加元素。细节：如果往List系列集合中添加数据，方法永远返回true；如果往Set系列集合中添加数据，若当前添加元素不存在 方法返回true 表示添加成功，若当前要添加的元素已存在 方法返回false 表示添加失败
boolean remove(Object o)	从集合中移除指定的元素
boolean removeIf(Object o)	根据条件进行移除
void clear()	清空集合中的元素
boolean contains(Object o)	判断集合中是否存在指定的元素。底层是依赖equals判断是否存在，所以如果集合中存储的是自定义对象 若想通过contains方法来判断是否包含，在javabean中一定要重写equals方法
boolean isEmpty()	判断集合是否为空
int size()	集合的长度，也就是集合中元素的个数

contails方法在底层依赖equals方法判断两对象是否一致。【自定义Javabean时，重写equals方法 —— 如果存的是自定义对象，没有重写equals方法，那么默认调用Object类中的equals方法进行判断，而Object类中equals，依赖地址值进行判断】

String底层也是依赖equal判断是否相等，只不过在字符串里面 java已重写了equals方法

2.2 Collection集合的遍历

共有三种方法遍历Collection集合：迭代器遍历、增强for、lambda表达式。

2.2.1 迭代器遍历

• 迭代器介绍

  • 迭代器，集合的专用遍历方式
  • Iterator iterator()：返回此集合中元素的迭代器，通过集合对象的iterator()方法得到

Collection集合获取迭代器

方法名称	说明
Iterator iterator()	返回该集合的迭代器对象（可视为指针），默认指向当前集合的0索引

• Iterator中的常用方法

方法名称	说明
boolean hasNext()	判断当前位置是否有元素，有元素返回true，没有元素返回false
E next()	获取当前位置的元素,将迭代器对象移向下一个索引位置（获取元素，移动指针）

• Collection集合的遍历

  public class IteratorDemo1 {public static void main(String[] args) {//创建集合对象Collection<String> c = new ArrayList<>();//添加元素c.add("money");c.add("study");c.add("honor");c.add("happy");//Iterator<E> iterator()：返回此集合中元素的迭代器，通过集合的iterator()方法得到Iterator<String> it = c.iterator();//用while循环改进元素的判断和获取while (it.hasNext()) {String s = it.next();System.out.println(s);}}
  }
  

• 迭代器中删除的方法

  ​ void remove(): 删除迭代器对象当前指向的元素

  public class IteratorDemo2 {public static void main(String[] args) {Collection<String> c = new ArrayList<>();c.add("money");c.add("study");c.add("honor");c.add("happy");Iterator<String> it = c.iterator();while (it.hasNext()) {String s = it.next();if ("study".equals(s)) {//报错java.util.ConcurrentModificationException
  //                c.remove(s);//使用迭代器删除。指向谁,那么此时就删除谁.it.remove();}}System.out.println(c);}
  }
  

• 迭代器总结

1.迭代器在遍历集合的时候是不需要依赖索引的

2.迭代器需要掌握三个方法：

Iterator<String> it = list.iterator();
while(it.hasNext()){String str = it.next();System.out.println(str);
}

3.迭代器的四个细节:

如果当前位置没有元素，还要强行获取，会报NoSuchElementException

迭代器遍历完毕，指针不会复位

循环中只能用一次next方法

迭代器遍历时，不能用集合的方法进行增加或者删除

public class IteratorDemo3 {public static void main(String[] args) {Collection<String> c = new ArrayList<>();c.add("money");c.add("study");c.add("honor");c.add("happy");//获取迭代器对象。迭代器就好比是一个箭头，默认指向集合的0索引处Iterator<String> it = c.iterator();while (it.hasNext()) {String s = it.next();System.out.println(s);}//当上面循环结束之后，迭代器的指针已经指向了最后没有元素的位置//System.out.println(it.next());//报错NoSuchElementException//迭代器遍历完毕，指针不会复位System.out.println(it.hasNext());  //false//如果我们要继续第二次遍历集合，只能再次获取一个新的迭代器对象Iterator<String> it2 = c.iterator();while (it2.hasNext()) {String str = it2.next();System.out.println(str);}}
}

2.2.2 增强for遍历

idea中快捷键 集合名字.for

• 介绍
  • 它是JDK5之后出现的，其内部原理是一个Iterator迭代器（增强for的底层就是迭代器，为了简化迭代器的代码书写的）
  • 实现Iterable接口的类才可以使用迭代器和增强for（所有的单列集合和数组才能用增强for进行遍历）
  • 简化数组和Collection集合的遍历
• 格式

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

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

• 代码

public class IteratorFor {public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("money");list.add("study");list.add("honor");list.add("happy");//1,数据类型一定是集合或者数组中元素的类型//2,str仅仅是一个变量名而已,在循环的过程中,依次表示集合或者数组中的每一个元素//3,list就是要遍历的集合或者数组for (String str : list) {System.out.println(str);}}
}

• 细节点注意

如果当前位置没有元素，还要强行获取，会报NoSuchElementException

迭代器遍历完毕，指针不会复位

循环中只能用一次next方法

迭代器遍历时，不能用集合的方法进行增加或者删除。如果我实在要删除：那么可以用迭代器提供的remove方法进行删除；如果我要添加，暂时没有办法(只是暂时)

2.2.3 lambda表达式

得益于JDK8开始的新技术Lambda表达式，提供了一种更简单、更直接的遍历集合的方式。利用forEach方法，再结合lambda表达式的方式进行遍历

方法名称	说明
default void forEach(Consumer<? super T> action)	结合lambda遍历集合

public class IteratorLambda {public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("money");list.add("study");list.add("honor");list.add("happy");//法一：利用匿名内部类的形式//底层原理：其实也会自己遍历集合，依次得到每一个元素。把得到的每一个元素，传递给下面的accept方法，s依次表示集合中的每一个数据list.forEach(new Consumer<String>() {@Overridepublic void accept(String s) {System.out.println(s);}});System.out.println("~~~~~~~~");//法二：lambda表达式list.forEach( s -> System.out.println(s));}
}

三、List集合

List集合添加的元素：有序、可重复、有索引

Set集合添加的元素：无序、不重复、无索引

3.1 List集合的概述和特点【记忆】

• List集合的概述

  • 有序集合，这里的有序指的是存取顺序
  • 用户可以精确控制列表中每个元素的插入位置，用户可以通过整数索引访问元素，并搜索列表中的元素
  • 与Set集合不同，列表通常允许重复的元素

• List集合的特点

  • 存取有序
  • 可以重复
  • 有索引

• Collection与List区别

  • Collection是无序的，不支持索引操作；而List是有序的，支持索引操作
  • 由上推导 List可以进行排序，所以List接口支持使用sort方法
  • List中Iterator为ListIterator

3.2 List集合的特有方法【应用】

• Collection的方法 List都继承了
• List集合因为有索引，所以多了很多索引操作的方法

方法名	描述
void add(int index,E element)	在此集合中的指定位置插入指定的元素。原来索引上的元素会依次往后移
E remove(int index)	删除指定索引处的元素，返回被删除的元素。细节——在调用方法的时候，如果方法出现了重载现象 优先调用，实参跟形参类型一致的那个方法
E set(int index,E element)	修改指定索引处的元素，返回被修改的元素
E get(int index)	返回指定索引处的元素

• 示例代码

public class ListFunction {public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("money");list.add("study");list.add("honor");list.add("happy");method1(list);method2(list);method3(list);}// add, setprivate static void method1(List<String> list) {//void add(int index,E element)	在此集合中的指定位置插入指定的元素//原来位置上的元素往后挪一个索引list.add(1, "health");System.out.println("使用add方法后： " + list);//E set(int index,E element)	修改指定索引处的元素，返回被修改的元素String setStr = list.set(0, "wealth");System.out.println("被修改的元素： " + setStr);System.out.println("使用set方法后： " + list);}// removeprivate static void method2(List<String> list) {//在List集合中有两个删除的方法//第一个 删除指定的元素,返回值表示当前元素是否删除成功（继承自Collection的remove方法）//第二个 删除指定索引的元素,返回值表示实际删除的元素String s = list.remove(1);System.out.println("实际删除的元素： " + s);System.out.println("使用remove方法后： " + list);}// getprivate static void method3(List<String> list) {String s = list.get(0);System.out.println("get(0)获取的元素： " + s);}
}

3.3 List集合的五种遍历方式【应用】

1. 迭代器
2. 增强for
3. lambda表达式
4. 普通for循环（因为List集合存在索引）
5. 列表迭代器：迭代器遍历完后 指针不会复位，但是ListIterator遍历完毕 指针可往前移动（有局限性 迭代器初始创建时 指针默认在0索引 直接调用previous 到-1 会报错，只能先往后运动 再往前动）

代码示例

public class ListTraverse {public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("money");list.add("study");list.add("honor");list.add("happy");//1.迭代器Iterator<String> it = list.iterator();while (it.hasNext()) {String str = it.next();System.out.println(str);}System.out.println("~~~~~~~~~");//2.增强for//下面的变量s，其实就是一个第三方的变量而已。在循环的过程中，依次表示集合中的每一个元素for (String s : list) {System.out.println(s);}System.out.println("~~~~~~~~~");//3.lambda表达式//forEach方法的底层其实就是一个循环遍历，依次得到集合中的每一个元素，并把每一个元素传递给下面的accept方法。accept方法的形参s，依次表示集合中的每一个元素list.forEach( s -> System.out.println(s));System.out.println("~~~~~~~~~");//4.普通for循环（因为List集合存在索引）//size方法跟get方法还有循环结合的方式，利用索引获取到集合中的每一个元素for (int i = 0; i < list.size(); i++) {String s = list.get(i);  //i:依次表示集合中的每一个索引System.out.println(s);}System.out.println("~~~~~~~~~");//5.列表迭代器//获取一个列表迭代器的对象，里面的指针默认也是指向0索引的。//额外添加了一个方法：在遍历的过程中，可以添加元素。不能用集合的add方法添加、删除ListIterator<String> it1 = list.listIterator();while (it1.hasNext()) {String str1 = it1.next();if ("study".equals(str1)) {it1.add("learn");}}System.out.println(list);}
}

3.4 细节点注意

List集合的索引从0开始

List系列集合中的两个删除的方法：直接删除元素、通过索引进行删除

public class ListDelete {public static void main(String[] args) {List<Integer> list = new ArrayList<>();list.add(1);list.add(2);list.add(3);//此时删除的是1这个元素，还是1索引上的元素？为什么？//删除1索引上的元素。因为在调用方法的时候，如果方法出现了重载现象，优先调用 实参跟形参类型一致的那个方法//此时remove方法是不会自动装箱的（结论，本质如上）
//        list.remove(1);
//        System.out.println(list);   //[1, 3]//如果就是想删除1 可以通过索引。
//        list.remove(0);
//        System.out.println(list);   //[2, 3]//手动装箱，手动把基本数据类型的1，变成Integer类型Integer i = Integer.valueOf(1);list.remove(i);System.out.println(list);     //[2, 3]}
}

参考JDK API中文文档

四、List集合的实现类 ArrayList、LinkedList

4.1 List集合子类的特点【记忆】

• ArrayList集合

  ​ 底层是数组结构实现，查询快、增删慢

• LinkedList集合

  ​ 底层是链表结构实现，查询慢、增删快

4.2 ArrayList

• ArrayList继承关系

• ArrayList组成

private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}
//真正存放元素的数组
transient Object[] elementData; // non-private to simplify nested class access
private int size;

一定要记住ArrayList中的transient Object[] elementData，该elementData是真正存放元素的容器，可见ArrayList是基于数组实现的。

• ArrayList构造函数

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);}
}public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

Object[] elementData 是ArrayList真正存放数据的数组。

ArrayList支持默认大小构造，和空构造，当空构造的时候存放数据的Object[] elementData是一个空数组{}。

• ArrayList添加元素

public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;
}private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);
}private void grow(int minCapacity) {int oldCapacity = elementData.length;//采用右移运算，就是原来的一般，所以是扩容1.5倍。比如10的二进制是1010，右移后变成101就是5int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);elementData = Arrays.copyOf(elementData, newCapacity);
}

注意ArrayList中有一个modCount的属性，表示该实例修改的次数。（所有集合中都有modCount这样一个记录修改次数的属性），每次增改添加都会增加一次该ArrayList修改次数，而上边的add(E e)方法是将新元素添加到list尾部。

• ArrayList扩容

• 数组copy

Java 是无法自己分配空间的，是底层C和C++的实现。以 C 为例，我们知道 C 中数组是一个指向首部的指针，比如我们 C 语言对数组进行分配内存。Java 就是通过 arraycopy 这个 native 方法实现的数组的复制。

public static native void arraycopy(Object src,  int  srcPos,Object dest, int destPos,int length);

p = (int *)malloc(len*sizeof(int));

这样的好处何在呢？Java里内存是由jvm管理的，而数组是分配的连续内存，而arrayList不一定是连续内存，当然jvm会帮我们做这样的事，jvm会有内部的优化，会在后续的例子中结合问题来说明。

• elementData为什么用transient修饰

1. transient的作用是该属性不参与序列化。
2. ArrayList继承了标示序列化的Serializable接口
3. 对arrayList序列化的过程中进行了读写安全控制。是如何实现序列化安全的呢?

private void writeObject(java.io.ObjectOutputStream s)throws java.io.IOException{// Write out element count, and any hidden stuffint expectedModCount = modCount;s.defaultWriteObject();// Write out size as capacity for behavioural compatibility with clone()s.writeInt(size);// Write out all elements in the proper order.for (int i=0; i<size; i++) {s.writeObject(elementData[i]);}if (modCount != expectedModCount) {throw new ConcurrentModificationException();}
}/*** Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,* deserialize it).*/
private void readObject(java.io.ObjectInputStream s)throws java.io.IOException, ClassNotFoundException {elementData = EMPTY_ELEMENTDATA;// Read in size, and any hidden stuffs.defaultReadObject();// Read in capacitys.readInt(); // ignoredif (size > 0) {// be like clone(), allocate array based upon size not capacityint capacity = calculateCapacity(elementData, size);SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);ensureCapacityInternal(size);Object[] a = elementData;// Read in all elements in the proper order.for (int i=0; i<size; i++) {a[i] = s.readObject();}}
}

在序列化方法writeObject()方法中可以看到，先用默认写方法，然后将size写出，最后遍历写出elementData，因为该变量是transient修饰的，所有进行手动写出，这样它也会被序列化了。那是不是多此一举呢？

protected transient int modCount = 0;

当然不是，其中有一个关键的modCount, 该变量是记录list修改的次数的，当写入完之后如果发现修改次数和开始序列化前不一致就会抛出异常，序列化失败。这样就保证了序列化过程中是未经修改的数据,保证了序列化安全。（java集合中都是这样实现）

4.3 LinkedList

• LinkedList继承关系

可见LinkedList既是List接口的实现也是Queue的实现（Deque），故其和ArrayList相比LinkedList支持的功能更多，其可视作队列来使用，当然下文中不强调其队列的实现。

• LinkedList结构

transient int size = 0;/*** Pointer to first node.* Invariant: (first == null && last == null) ||*            (first.prev == null && first.item != null)*/
transient Node<E> first;/*** Pointer to last node.* Invariant: (first == null && last == null) ||*            (last.next == null && last.item != null)*/
transient Node<E> last;//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;}
}

LinkedList由一个头节点和一个尾节点组成，分别指向链表的头部和尾部。

LinkedList中Node由当前值item，和指向上一个节点prev和指向下个节点next的指针组成。并且只含有一个构造方法，按照(prev, item, next)这样的参数顺序构造。

数据结构中链表的头插法linkFirst和尾插法linkLast

/*** Links e as first element.*/
private void linkFirst(E e) {final Node<E> f = first;final Node<E> newNode = new Node<>(null, e, f);first = newNode;if (f == null)last = newNode;elsef.prev = newNode;size++;modCount++;
}/*** Links e as last element.*/
void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;modCount++;
}

• LinkedList查询方法

按照下标获取某一个节点：get方法，获取第index个节点。

public E get(int index) {checkElementIndex(index);return node(index).item; //node(index)方法是怎么实现的呢？判断index是更靠近头部还是尾部，靠近哪段从哪段遍历获取值。
}Node<E> node(int index) {// assert isElementIndex(index);//判断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;}
}

查询索引修改方法，先找到对应节点，将新的值替换掉老的值。

public E set(int index, E element) {checkElementIndex(index);Node<E> x = node(index);E oldVal = x.item;x.item = element;return oldVal;
}

这个也是为什么ArrayList随机访问比LinkedList快的原因**，LinkedList要遍历找到该位置才能进行修改，而ArrayList是内部数组操作会更快。

• LinkedList修改方法

public boolean add(E e) {linkLast(e);return true;
}public void add(int index, E element) {checkPositionIndex(index);if (index == size)linkLast(element);elselinkBefore(element, node(index));
}

• 特有方法

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

• 示例代码

public class MyLinkedListDemo1 {public static void main(String[] args) {LinkedList<String> list = new LinkedList<>();list.add("money");list.add("study");list.add("honor");list.add("happy");method1(list);}private static void method1(LinkedList<String> list) {list.addFirst("excellence");System.out.println("使用addFirst方法后： " + list);list.addLast("health");System.out.println("使用addLast方法后：  " + list);System.out.println("getFirst、getLast：  " + list.getFirst() + ", " + list.getLast());String first = list.removeFirst();String last = list.removeLast();System.out.println("removeFirst、removeLast：  " + first + ", " + last);System.out.println(list);}
}

五、List相关源码分析

5.1 ArrayList源码分析

核心步骤：

1. 创建ArrayList对象的时候，他在底层先创建了一个长度为0的数组。

   数组名字：elementDate，定义变量size。

   size这个变量有两层含义：
   ①：元素的个数，也就是集合的长度
   ②：下一个元素的存入位置

2. 添加元素，添加完毕后，size++

扩容时机一：

3. 当存满时候，会创建一个新的数组，新数组的长度，是原来的1.5倍，也就是长度为15.再把所有的元素，全拷贝到新数组中。如果继续添加数据，这个长度为15的数组也满了，那么下次还会继续扩容，还是1.5倍。

扩容时机二：

4. 一次性添加多个数据，扩容1.5倍不够，怎么办呀？

   如果一次添加多个元素，1.5倍放不下，那么新创建数组的长度以实际为准。

举个例子：
在一开始，如果默认的长度为10的数组已经装满了，在装满的情况下，我一次性要添加100个数据很显然，10扩容1.5倍，变成15，还是不够，

怎么办？

此时新数组的长度，就以实际情况为准，就是110

具体分析过程可以参见视频讲解。

添加一个元素时的扩容：

添加多个元素时的扩容：

5.2 LinkedList源码分析

底层是双向链表结构

核心步骤如下：

1. 刚开始创建的时候，底层创建了两个变量：一个记录头结点first，一个记录尾结点last，默认为null
2. 添加第一个元素时，底层创建一个结点对象，first和last都记录这个结点的地址值
3. 添加第二个元素时，底层创建一个结点对象，第一个结点会记录第二个结点的地址值，last会记录新结点的地址值

具体分析过程可以参见视频讲解。

5.3 迭代器源码分析

迭代器遍历相关的三个方法：

• Iterator iterator() ：获取一个迭代器对象

• boolean hasNext() ：判断当前指向的位置是否有元素

• E next() ：获取当前指向的元素并移动指针

六、Set集合

java中的Set接口和Colletion是完全一样的定义。

public interface Set<E> extends Collection<E> {// Query Operationsint size();boolean isEmpty();boolean contains(Object o);Object[] toArray();<T> T[] toArray(T[] a);// Modification Operationsboolean add(E e);boolean remove(Object o);boolean containsAll(Collection<?> c);boolean addAll(Collection<? extends E> c);boolean retainAll(Collection<?> c);boolean removeAll(Collection<?> c);void clear();boolean equals(Object o);int hashCode();//此处和Collection接口有区别Spliterator<E> spliterator() {return Spliterators.spliterator(this, Spliterator.DISTINCT);}
}

6.1 Set集合概述和特点【应用】

• 不可以存储重复元素
• 没有索引，不能使用普通for循环遍历

6.2 Set集合的使用【应用】

存储字符串并遍历

public class MySet1 {public static void main(String[] args) {Set<String> set = new TreeSet<>();set.add("money");set.add("study");set.add("honor");set.add("happy");set.add("study");//        for (int i = 0; i < set.size(); i++) {
//            //Set集合是没有索引的，所以不能使用通过索引获取元素的方法
//        }//遍历集合Iterator<String> it = set.iterator();while (it.hasNext()) {String s = it.next();System.out.println(s);}System.out.println("~~~~~~~~");for (String s : set) {System.out.println(s);}System.out.println("~~~~~~~~");set.forEach(s -> System.out.println(s));}
}

七、TreeSet集合

7.1 TreeSet集合概述和特点【应用】

• 不可以存储重复元素
• 没有索引
• 可以将元素按照规则进行排序
  • TreeSet()：根据其元素的自然排序进行排序
  • TreeSet(Comparator comparator) ：根据指定的比较器进行排序

7.2 TreeSet集合基本使用【应用】

存储Integer类型的整数并遍历

public class TreeSetDemo01 {public static void main(String[] args) {TreeSet<Integer> ts = new TreeSet<>();ts.add(20);ts.add(10);ts.add(40);ts.add(50);ts.add(30);for (Integer t : ts) {System.out.println(t);}System.out.println(ts);  //[10, 20, 30, 40, 50]}
}

注意输出顺序 10 20 30 40 50

7.3 自然排序Comparable的使用【应用】

• 案例需求

  • 存储学生对象并遍历，创建TreeSet集合使用无参构造方法
  • 要求：按照年龄从小到大排序，年龄相同时，按照姓名的字母顺序排序

• 实现步骤

  1. 使用空参构造创建TreeSet集合
     • 用TreeSet集合存储自定义对象，无参构造方法使用的是自然排序对元素进行排序的
  2. 自定义的Student类实现Comparable接口
     • 自然排序，就是让元素所属的类实现Comparable接口，重写compareTo(To)方法
  3. 重写接口中的compareTo方法
     • 重写方法时，一定要注意排序规则必须按照要求的主要条件和次要条件来写

• 代码实现

学生类

//不加implements Comparable<Student>【加implements Comparable<Student> 需重写compareTo(Student o)方法】    报错ClassCastException： com.ywj.collection.MySet.Student cannot be cast to java.lang.Comparable
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;}@Overridepublic String toString() {return "Student{" +"name='" + name + '\'' +", age=" + age +'}';}@Overridepublic 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.4 比较器排序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;}@Overridepublic String toString() {return "Teacher{" +"name='" + name + '\'' +", age=" + age +'}';}
}

测试类

public class TeacherTreeSet {public static void main(String[] args) {//创建集合对象TreeSet<Teacher> ts = new TreeSet<>(new Comparator<Teacher>() {@Overridepublic 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);}}
}

输出结果

Teacher{name=‘lisi’, age=22}
Teacher{name=‘zhangsan’, age=23}
Teacher{name=‘wangwu’, age=24}
Teacher{name=‘zhaoliu’, age=24}

7.5 两种比较方式总结【理解】

• 两种比较方式小结
  • 自然排序：自定义类实现Comparable接口，重写compareTo方法，根据返回值进行排序
  • 比较器排序：创建TreeSet对象的时候传递Comparator的实现类对象，重写compare方法，根据返回值进行排序
  • 在使用的时候，默认使用自然排序，当自然排序不满足现在的需求时，必须使用比较器排序
• 两种方式中关于返回值的规则
  • 如果返回值为负数，表示当前存入的元素是较小值，存左边
  • 如果返回值为0，表示当前存入的元素跟集合中元素重复了，不存
  • 如果返回值为正数，表示当前存入的元素是较大值，存右边

八、HashSet集合

8.1 HashSet集合概述和特点【应用】

是一种Hash实现的集合，使用的底层结构是HashMap。其特点如下：

1. 底层数据结构是哈希表
2. 存取无序
3. 不可以存储重复元素
4. 没有索引，不能使用普通for循环遍历

• HashSet继承关系

• HashSet源码

public class HashSet<E>extends AbstractSet<E>implements Set<E>, Cloneable, java.io.Serializable
{static final long serialVersionUID = -5024744406713321676L;private transient HashMap<E,Object> map;private static final Object PRESENT = new Object();public HashSet() {map = new HashMap<>();}public HashSet(Collection<? extends E> c) {map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));addAll(c);}//...public Iterator<E> iterator() {return map.keySet().iterator();}public int size() {return map.size();}public boolean contains(Object o) {return map.containsKey(o);}public boolean add(E e) {return map.put(e, PRESENT)==null;}public boolean remove(Object o) {return map.remove(o)==PRESENT;}public void clear() {map.clear();}}

可以看到HashSet内部其实是一个HashMap。

• HashSet是如何保证不重复的呢？

可见HashSet的add方法，插入的值会作为HashMap的key，所以是HashMap保证了不重复。map的put方法新增一个原来不存在的值会返回null，如果原来存在的话会返回原来存在的值。关于HashMap是如何实现的，见后续！

8.2 HashSet集合的基本应用【应用】

public class HashSetDemo1 {public static void main(String[] args) {//创建集合对象HashSet<String> set = new HashSet<String>();//添加元素set.add("money");set.add("study");set.add("honor");set.add("happy");//不包含重复元素的集合set.add("study");//遍历for (String s : set) {System.out.println(s);}//输出 [study, money, honor, happy]System.out.println(set);}
}

8.3 哈希值【理解】

Set集合的去重原理使用的是哈希值。

• 哈希值简介

  ​ 是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值

• 如何获取哈希值

  ​ Object类中的public int hashCode()：返回对象的哈希码值

• 哈希值的特点

  • 同一个对象多次调用hashCode()方法返回的哈希值是相同的
  • 默认情况下，不同对象的哈希值是不同的。而重写hashCode()方法，可以实现让不同对象的哈希值相同

8.4 哈希表结构【理解】

• JDK1.8以前

  ​ 数组 + 链表

• JDK1.8以后

  • 节点个数少于等于8个

    ​ 数组 + 链表

  • 节点个数多于8个

    ​ 数组 + 红黑树

8.5 HashSet集合存储学生对象并遍历【应用】

• 案例需求

  • 创建一个存储学生对象的集合，存储多个学生对象，使用程序实现在控制台遍历该集合
  • 要求：学生对象的成员变量值相同，我们就认为是同一个对象

• 代码实现

学生类

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;}//是否重写equals、hashCode方法，HashSet的值有所不同@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Student student = (Student) o;return age == student.age && Objects.equals(name, student.name);}@Overridepublic int hashCode() {return Objects.hash(name, age);}}

测试类

public class HashSetDemo02 {public static void main(String[] args) {//创建HashSet集合对象HashSet<Student> hs = new HashSet<>();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("zhangsan",28);//把学生添加到集合hs.add(s1);hs.add(s2);hs.add(s3);hs.add(s4);hs.add(s5);System.out.println(hs);//遍历集合(增强for)for (Student s : hs) {System.out.println(s.getName() + "," + s.getAge());}}
}

如果不重写Student类的equals和hashCod方法，名字为"zhangsan"的对象不同，输出如下：

重写Student类的equals和hashCod方法，能保证"zhangsan"对象的唯一性，输出如下：

• 总结

HashSet集合存储自定义类型元素，要想实现元素的唯一，要求必须重写hashCode方法和equals方法

九、LinkedHashSet

LinkedHashSet用的也比较少，其也是基于Set的实现。

9.1 LinkedHashSet继承关系

9.2 LinkedHashSet源码

public class LinkedHashSet<E>extends HashSet<E>implements Set<E>, Cloneable, java.io.Serializable {private static final long serialVersionUID = -2851667679971038690L;public LinkedHashSet(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor, true);}public LinkedHashSet(int initialCapacity) {super(initialCapacity, .75f, true);}public LinkedHashSet() {super(16, .75f, true);}public LinkedHashSet(Collection<? extends E> c) {super(Math.max(2*c.size(), 11), .75f, true);addAll(c);}@Overridepublic Spliterator<E> spliterator() {return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);}
}

其操作方法和HashSet完全一样，那么二者区别是什么呢？1.首先LinkedHashSet是HashSet的子类；2.LinkedHashSet中用于存储值的实现LinkedHashMap，而HashSet使用的是HashMap。LinkedHashSet中调用的父类构造器，可以看到其实列是一个LinkedHashMap。

HashSet(int initialCapacity, float loadFactor, boolean dummy) {map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

参考黑马程序员相关视频与笔记、【查漏补缺】Java 集合详解！