为什么需要学习集合框架？

集合：存放多个元素内容

框架：底层封装好，提供简单的API给开发人员使用

集合框架：JDK帮助我们封装好，可以直接简单使用集合

下面让我们看一下这段代码

public static void main(String[] args) {
    //创建一个数组 存放三个元素
    String[] arrs= new String[3];
    arrs[0]="王昭君";
    arrs[1]="嫦娥";
    arrs[2]="伽罗";
    arrs[3]="诸葛亮";//数组下标越界ArrayIndexOutOfBoundsException
    System.out.println(arrs[3]);
}

原生数组在定义时就已经规定死了数组大小，当我们添加元素超过数组大小时就会出现数组下标越界

那么，我们应该如何定义一个动态数组呢？即可以无限地存放元素。这时就需要使用到集合框架API

集合类特点：提供一种存储空间可变的存储模型，存储的数据容量可以动态发生改变

常见的集合框架底层设计会使用大量的数据结构

• 数组
• 链表
• 树
• 队列

集合框架入门

首先我们通过下图来看一下集合框架的分类构成

集合框架中，单列与多列的区别：

• 单列：从图中很好理解，每一行只有一列数据
• 多列：每一行有两列数据：第一列为key，第二列为value；即第一列为键，第二列为值

接下来让我们通过源码的类图来证实一下上图

首先来看一下ArrayList实现类

public static void main(String[] args) {
   	//new 一个ArrayList实现类
    Collection collection= new ArrayList<String>();
    collection.add("王昭君");
}

其中第2行的<String>存放泛型，表示此ArrayList集合容器只能够存放String类型

接下来我们直接看一下ArrayList源码的类图

可以看到，ArrayList实现类实现了List接口，而List接口又实现了Collection接口

让我们看一下Map实现类HashMap

public static void main(String[] args) {
    Map map = new HashMap<String,String>();
    map.put("Legend1","王昭君");
}

不难发现，HashMap需要两个泛型，一个代表key键类型，一个代表value值类型

接下来看一下HashMap源码的类图

HashMap实现了Map接口。

总结一下集合框架组成结构：

• Collection接口：存放单列数据
  • List接口：存放的数据允许重复，保证存入数据的有序性
    • ArrayList：底层基于数组实现
    • LinkedList：底层基于链表实现
  • Set接口：不允许存入重复的数据，也就是Set集合可以对数据做去重，且存入的数据无序
    • HashSet：底层基于Map集合实现
    • TreeSet
• Map接口：存入多列数据key、value
  • HashMap：在JDK1.7底层基于数组+链表实现，而在JDK1.8以后数组+链表+红黑树实现
  • HashTable

ArrayList

ArrayList类是一个可以动态修改的数组，与普通数组的区别就是它没有固定大小的限制

ArrayList继承类AbstractList，并实现了List接口

ArrayList类位于java.util包中，使用前需要导包，语法格式如下

import java.util.ArrayList;//引入ArrayList类

public class Test {
    public static void main(String[] args) {
        ArrayList<E> objectName = new ArrayList<E>();//初始化
    }
}

其中第五行的E为泛型数据类型，用于设置objectName的元素数据类型，只能为引用数据类型

ArrayList中的元素实际上是对象，在第二节的实例中元素都是字符串String类型，如果我们要存储其他类型，而<E>只能为引用数据类型，这时就需要使用到基本类型的包装类

在new了一个ArrayList后，底层通过数组实现。源码如下

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

transient Object[] elementData; // non-private to simplify nested class access

默认的初始容量为10，当添加元素超过10个时，会自动进行扩容。

ArrayList集合框架的常见方法：

各个方法使用示例：

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

    arrayList.add("王昭君");//向元素中存放元素 index=0
    arrayList.add("嫦娥");//向元素中存放元素 index=1
    arrayList.add("伽罗");//向元素中存放元素 index=2

    //size()方法获取集合的元素个数
    System.out.println("集合中存入的元素个数：" + arrayList.size());

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

    //get()方法取出元素
    System.out.println("第一个元素是" + arrayList.get(0));
    System.out.println("第二个元素是" + arrayList.get(1));
    System.out.println("第三个元素是" + arrayList.get(2));

    //        System.out.println("第三个元素是"+arrayList.get(5));//数组下标越界IndexOutOfBoundsException

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

    //遍历
    for (int i = 0; i < arrayList.size(); i++) {
      System.out.println("第" + i + "个元素是" + arrayList.get(i));
    }

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

    //set()方法修改集合元素
    arrayList.set(2, "李元芳");

    for (int i = 0; i < arrayList.size(); i++) {
      System.out.println("修改后第" + i + "个元素是" + arrayList.get(i));
    }

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

    //remove()方法删除集合元素
    arrayList.remove(1);

    for (int i = 0; i < arrayList.size(); i++) {
      System.out.println("删除后第" + i + "个元素是" + arrayList.get(i));
    }
}

remove()方法删除元素的过程如下图所示

在删除一个元素后，该元素后面的元素会向前移动一位

集合的遍历

在第三节的程序中遍历使用了for循环，而集合有自己专门的遍历方式，即迭代器

Iterator：迭代器，集合的专用遍历方式

在之前我们都通过for循环遍历集合：

public static void main(String[] args) {
    List<String> arrayList = new ArrayList<>();
    arrayList.add("王昭君");
    arrayList.add("诸葛亮");
    arrayList.add("貂蝉");
    for (int i = 0; i < arrayList.size(); i++) {
      	System.out.println(arrayList.get(i)); 
    }
}

我们可以使用迭代器更加便捷地遍历集合

Iterator<String> iterator = arrayList.iterator();
System.out.println(iterator.next());//调用第一次next方法，取出第一个元素
System.out.println(iterator.next());//调用第二次next方法，取出第二个元素
System.out.println(iterator.next());//调用第三次next方法，取出第三个元素

迭代器底层实现原理：底层使用一个计数器count，初始值为0，每次调用.next方法的时候，调用get(count++)

当List中数据较多时，我们可以使用while循环

int count = 0;
while (true){
    count++;
    String next = iterator.next();
    System.out.println(next);
    if (count >= arrayList.size()){
        break;
    }
}

上述遍历太过繁琐，可以使用hasnext()方法做优化

hasnext：判断元素值是否可以获取 如果可以获取 则返回true 否则返回false

while (iterator.hasNext()){ //如果迭代器能够获取到元素，返回true
    System.out.println(iterator.next());
}

手写Iterator迭代器

public class MyIterator {
    private List list;

    /**
     * 有参构造方法
     * @param list
     */
    public MyIterator(List list) {
        this.list = list;
    }

    /**
     * 迭代器 计数器 初始值为0
     */
    private int count = 0;

    public Object next() {
        if (list == null) {
            throw new MyIteratorException("list为空");
        }

        if (count >= list.size()) {
            //说明集合中没有可以获取到的元素
            //访问下标越界
            throw new MyIteratorException("无法继续向下获取元素");
        }
        return list.get(count++);
    }

    public boolean hasNext() {
        /*
        if(count == list.size()){
            //获取次数与集合中元素个数相等，即不能向下获取
        }
        */
        return count != list.size();
    }
}

ListIterator

ListIterator：列表迭代器，是List特有的迭代器，该迭代器继承了Iterator迭代器，所以可以直接使用next()和hasNext()方法。

特有功能：

• Object previous()：获取上一个元素
• boolean previous()：判断有没有上一个元素

ListIterator可以逆向遍历list，但是前提是先正向遍历，然后才能逆向遍历。一般情况下不使用

public static void main(String[] args) {
    ArrayList<String> arrayList = new ArrayList<>();
    arrayList.add("王昭君");
    arrayList.add("诸葛亮");
    arrayList.add("貂蝉");
    ListIterator<String> listIterator = arrayList.listIterator();
    System.out.println(listIterator.next());
    System.out.println(listIterator.next());
    System.out.println(listIterator.next());
    while (listIterator.hasPrevious()){
        System.out.println(listIterator.previous());//get(--count)
    }
}

三种不同方式遍历学生对象集合

public class Test08 {
    public static void main(String[] args) {
        ArrayList<Student> students = new ArrayList<>();
        Student student1 = new Student("张三", 22, "男", "1253");
        Student student2 = new Student("李四", 25, "女", "2223");
        Student student3 = new Student("王五", 23, "女", "1255");
        Student student4 = new Student("刘六", 27, "男", "7534");
        Student student5 = new Student("齐七", 24, "男", "3435");

        students.add(student1);
        students.add(student2);
        students.add(student3);
        students.add(student4);
        students.add(student5);

        for (int i = 0; i < students.size(); i++) {
            System.out.println(students.get(i));
        }

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

        Iterator<Student> iterator = students.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }

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

        for (Student s : students) {
            System.out.println(s);
        }
    }
}

为什么使用泛型？

在1.5之前Java还没有泛型，我们在声明一个集合时，编译器默认集合中的数据为Object类型。

在没有指定泛型的集合中添加三个String类型的数据：

public class Test01 {
    public static void main(String[] args) {
        ArrayList arrayList = new ArrayList();
        arrayList.add("诸葛亮");
        arrayList.add("王昭君");
        arrayList.add("嫦娥");
        Iterator iterator = arrayList.iterator();
        while (iterator.hasNext()) {
            //Object next = iterator.next();
            //强制类型转换
            String next = (String) iterator.next();
            System.out.println(next);
        }
    }
}

通过迭代器取出集合中元素，可以发现类型为Object。但是我们明明存放的是String类型啊。这时就可以使用到强制类型转换，将Object转换成String类型。

这样向上转型是没有问题的，但是如果向这个集合中存放一个int类型的数据，这时遍历集合，就会报错。因为不能将Integer类型转换为String类型：java.lang.ClassCastException: class java.lang.Integer cannot be cast to class java.lang.String

因此在jdk1.5之前使用集合是很麻烦的，获取元素时需要判断该元素的类型。

ArrayList arrayList = new ArrayList<>();
arrayList.add("诸葛亮");
arrayList.add("王昭君");
arrayList.add("嫦娥");
arrayList.add(12);
Iterator iterator = arrayList.iterator();
while (iterator.hasNext()) {
    Object next = iterator.next();
    if (next instanceof String) {
        String str = (String) next;
        System.out.println(str);
    }
    if (next instanceof Integer) {
        Integer i = (Integer) next;
        System.out.println(i);
    }
}

那如何解决这个麻烦呢？这时就需要到泛型，在JDK1.5之后提供了泛型，为集合指定存放的类型，这个集合就不能存放非指定类型的数据。而且在获取这个数据时，不必再强转为目标数据类型。也保证了数据的安全性。

ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("诸葛亮");
arrayList.add("王昭君");
arrayList.add("嫦娥");
arrayList.add(12); //❌
Iterator iterator = arrayList.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

在指定泛型为String后向集合中添加int类型数据，一定会报错：java: 不兼容的类型: int无法转换为java.lang.String

泛型：是一种把类型的明确工作推迟到创建对象或者调用方法的时候再去明确的特殊类型

泛型可以使用在方法、接口、类，分别称作泛型类、泛型方法、泛型接口。

泛型类

泛型类定义格式：修饰符 class 类名<类型>{}

范例：public class Mark<T>{}

此处T可以随便写为任意标识符，T、E、K、V等形式的参数常用于表示泛型

首先定义一个学生类，学生类有学号属性。

public class Student {
    private String stuNumber;

    public String getStuNumber() {
        return stuNumber;
    }

    public void setStuNumber(String stuNumber) {
        this.stuNumber = stuNumber;
    }
}

我们可以创建一个学生对象，为其学号设置一个String类型的值

public static void main(String[] args) {
    Student s1 = new Student();
    s1.setStuNumber("10001");
    System.out.println(s1.getStuNumber());
}

当我们想要将学号赋值为int或其他类型时，肯定是不行的。想要赋值为其他类型就要修改学生类属性的声明。因此可以使用泛型类。

使用泛型类：

public class Mark<T> {
    /**
     * 成员属性类型和类定义的泛型类型是相同的
     */
    private T t;

    public T getT() {
        return t;
    }

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

public class Test02 {
    public static void main(String[] args) {
        Mark<String> stringMark = new Mark<>();
        stringMark.setT("诸葛亮");
        System.out.println(stringMark.getT());
        Mark<Integer> integerMark = new Mark<>();
        integerMark.setT(1001);
        System.out.println(integerMark.getT());
    }
}

使用泛型类可以规定类成员属性的类型

泛型方法

格式：修饰符<类型> 返回值类型 方法名(类型 变量名){...}

范例：public<T> void show(T t){...}

创建一个Love类，其中有四个方法：

public class Love {
    public String show(String str) {
        return str;
    }

    public Integer show(Integer integer) {
        return integer;
    }

    public Boolean show(Boolean bool) {
        return bool;
    }

    public Double show(Double dou) {
        return dou;
    }
}

四个方法是重载的，即方法名相同，参数列表与返回值不同

调用四个方法：

public class Test03 {
    public static void main(String[] args) {
        Love love = new Love();
        String zgl = love.show("诸葛亮");
        System.out.println(zgl);
        Boolean result = love.show(true);
        System.out.println(result);
        Double dou = love.show(25.5);
        System.out.println(dou);
        Integer i = love.show(25);
        System.out.println(i);
    }
}

当show方法中传入不同类型参数时，会自动返回什么类型的参数。但是会发现上面的代码会有很多重复性的代码，有冗余。一个类的方法想要传递多种不同类型的参数，传统模式只能定义四个方法重载，很不合理。因此可使用到泛型类来优化代码。

public class Love<T> {
    public T show(T t){
        return t;
    }
}

public static void main(String[] args) {
        Love<String> love1 = new Love();
        String mark = love1.show("哈哈");
        System.out.println(mark);
        Love<Boolean> love2 = new Love();
        Boolean result = love2.show(true);
        System.out.println(result);
        Love<Double> love3 = new Love();
        Double d = love3.show(255.5);
        System.out.println(d);
        Love<Integer> love4 = new Love();
        Integer i = love4.show(25);
        System.out.println(i);
    }

但是感觉show方法的调用还是有点重复，而且创建了很多love对象，每个love对象只能传递指定的泛型。

可以使用泛型方法优化代码

public class Love{
    public <T> T show(T t){
        return t;
    }
}

public static void main(String[] args) {
    Love love = new Love();
    String str = love.show("mark");
    System.out.println(str);
    Boolean result = love.show(true);
    System.out.println(result);
    Double d = love.show(255.5);
    System.out.println(d);
    Integer i = love.show(25);
    System.out.println(i);
}

泛型接口

格式：修饰符 interface 接口名<类型>{...}

范例：public interface MarkInterface<T>{...}

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

实现该接口：

public class MarkInterfaceImpl<T> implements MarkInterface<T>{
    @Override
    public T show(T t) {
        return t;
    }
}

调用实现类的方法：

public class Test04 {
    public static void main(String[] args) {
        MarkInterfaceImpl<String> stringMarkInterface = new MarkInterfaceImpl<>();
        String str = stringMarkInterface.show("36");
        System.out.println(str);
    }
}

泛型接口和泛型类的区别

在泛型接口中声明泛型方法，会涉及到两个泛型：接口的泛型和方法的泛型，两个泛型并不是同一个泛型

public interface MyInterface<T> {
    <M> T show(M m, T t);
}

实现类重写方法：

public class MyInterfaceImpl<T> implements MyInterface<T> {
    @Override
    public <M> T show(M m, T t) {
        System.out.println("M:" + m);
        return t;
    }
}

public class Test04 {
    public static void main(String[] args) {
        MarkInterfaceImpl<String> stringMarkInterface = new MarkInterfaceImpl<>();
        String str = stringMarkInterface.show("36");
        System.out.println(str);

        MyInterfaceImpl<String> stringMyInterface = new MyInterfaceImpl<>();
        String my = stringMyInterface.show(55, "hello");
        System.out.println("T:" + my);
    }
}

list接口中的泛型设计思路

ArrayList实现了List接口，List接口实际思路如下

public interface MarkList<E> {
    void add(E e);
    E get(int index);
}

ArrayList实现List接口：

public class MarkArrayList<E> implements MarkList<E> {
    @Override
    public void add(E e) {
        System.out.println("新增成功");
    }

    @Override
    public E get(int index) {
        System.out.println("查询成功");
        E e = null;
        return e;
    }
}

类型通配符

当我们定义一个方法的时候，参数列表中如果传一个List集合，但是List集合的泛型不能确定，，那我们应该如何做？我们就可以这样写：List<?>。

• 类型通配符<?> 一般用于接受使用，不能够做添加
• List<?>：表示元素类型未知的list，它的元素可以匹配任何类型
• 带通配符的List仅带表示它是各种泛型List的父类，并不能把元素添加到其中

• 类型通配符上限：<? extends 类型> 例如： List<? extends MarkParent>：它表示的类型是MarkParent或者其子类型
• 类型通配符下限：<? super 类型> 例如：List<? super MarkSon>：它表示的类型是MarkSon或者其父类型

可变参数

public static int sum(int a, int b) {
    return a + b;
}

public static int sum(int a, int b, int c) {
    return a + b + c;
}

public static int sum(int a, int b, int c, int d) {
    return a + b + c + d;
}

上述sum参数在做参数重载，即方法名相同，参数列表和返回值不同。当我们以后调用方法时，有需要新增一个参数，就要再做一次方法重载，代码非常不灵活。因此可以用到可变参数。

• 可变参数，又称参数个数可变，用作方法的形参出现，那么方法参个数就是可变的了
• 书写格式：
  • 格式：修饰符 返回值类型 方法名(数据类型...变量名){}
  • 范例：public static int sum(int...a){}
• 可变参数注意事项：
  • 这里的可变参数变量其实是一个数组
  • 如果一个方法有多个参数，包含可变参数，可变参数要放在最后

public static int[] sum(int... a) {
    for (int a1 : a) {
        System.out.println(a1);
    }
    return a;
}

Arrays类有一个方法叫asList(),可以将数组array转换为List。通过查看源码发现asList方法就是传入的可变参数。

public static void main(String[] args) {
    List<String> list = Arrays.asList("哈哈", "呵呵", "嘻嘻");
    System.out.println(list);
    list.add("啦啦");//错误
}

但是转换的List集合不能添加和删除。执行上述代码发现会报错：java.lang.UnsupportedOperationException

因为数组定义好的元素个数是不能发生变化的，那么转换成的List也不能改变。

泛型原理：擦除机制

之前我们强调，泛型是在编译阶段限制传递的类型

比如：

public static void main(String[] args) {
    //创建一个ArrayList，指定泛型为String
    ArrayList<String> strs = new ArrayList<>();
    strs.add("mark");
    //将ArrayList集合赋值给没有使用到泛型的List集合
    List list = strs;
    //可以发现，获取到的list中的元素为Object类型
    Object o = list.get(0);
    System.out.println(o);
}

在运行阶段会被擦除，底层的class文件在运行中是没有泛型的。如何证明？反编译：class文件 ->java源代码

可以使用XJad软件将.class文件反编译为java文件。

ArrayList底层是如何实现的？

经典面试题：ArrayList底层是如何实现的？

下面我们查看ArrayList源码：

阅读源码方式：

1.查看无参构造函数

​ 可以发现底层默认初始化了一个空数组

2.分析方法实现

可以发现ArrayList确实是基于数组实现的。根据index下标查询效率是非常高的。为什么呢？

此时就需要谈到数据结构中的时间复杂度了。

• 时间复杂度：

  • O(1)：只需要查询一次
  • O(n)：需要查询n次

  当我们根据index下标去查询修改时，我们可以直接通过index定位到这个位置的值，只需要查询一次。

  当我们根据元素查询修改时，只能将数组遍历，取出各个位置的值，如果取出的值等于所查元素值，就返回index的值或修改该值。

  public static void main(String[] args) {
      Object[] objects = new Object[10];
      objects[0] = "哈哈";
      objects[1] = "呵呵";
      objects[2] = "嘻嘻";
      //查询index为2的值 仅需查询一次 时间复杂度为O(1)
      System.out.println(objects[2]);
      System.out.println("--------------");
      //若想要查询嘻嘻的index
      int sum = 0;
      for (int i = 0; i < objects.length; i++) {
          sum++;
          if ("嘻嘻".equals(objects[i])) {
              System.out.println(i);
              break;
          }
      }
      //时间复杂度为O(n) n可以看作循环的次数
      System.out.println("查找 嘻嘻 需要循环" + sum + "次");
  }
  
  /**
   * 嘻嘻
   * --------------
   * 2
   * 查找 嘻嘻 需要循环3次
  */
  

原生的数组是没有扩容机制的，而ArrayList最开始默认初始化数组的容量为10。

add底层方法实现：

1. 判断是否需要扩容：使用当前最大集合容量减去集合当前容量，若大于0则需要扩容
2. 如果不需要扩容直接通过index赋值
3. 如果需要扩容则调用grow方法扩容到原来的1.5倍，再将原来数组的值拷贝到新的数组中

当第一次调用add方法添加元素时候，底层调用grow方法从而创建一个数组长度为10的数组替换老的数组。以后2到10次调用add方法（数组长度未超过10）均不会扩容。第11次调用add方法时候，会触发扩容机制，将调用grow方法进行扩容，创建一个新数组，容量为原数组容量的1.5倍（oldCapacity >> 1 == 10 / 2），并将就数组的值复制到新数组。

remove底层方法实现：

（1）判断索引index是否越界
（2）将 index + 1 及之后的元素向前移动一位
（3）最后一个值变为null
（4）长度size – 1

错误答案：底层基于数组实现，查询修改效率非常高，增删效率非常低

正确答案：底层基于数组实现，根据index下标查询、修改效率非常高，时间复杂度为O(1)，但是如果根据元素值查询、修改效率非常低，时间复杂度为O(n)（误区：不是查询效率比较高）；由于底层基于数组实现，新增需要触发扩容机制，效率非常低，而删除操作会把删除元素后面的元素向前移动一位，所以效率也是非常低的。

简单手写ArrayList集合

public class MarkArrayList<E> {
    /**
     * 集合需要存放的元素
     */
    private Object[] elementData;
    /**
     * 集合大小
     */
    private int size;

    /**
     * 无参构造函数
     */
    public MarkArrayList() {
        //默认数组初始化容量大小为10
        elementData = new Object[10];
    }

    /**
     * 添加元素方法
     *
     * @param e 所添加的元素
     */
    public void add(E e) {
        //在数组中添加元素，添加后集合大小加一
        elementData[size++] = e;
    }

}

ArrayList与Vector的区别

Vector可能比较陌生，Vector的底层实现和ArrayList很相似，可以说基本上完全一样。

Vector<String> strings = new Vector<>();
strings.add("mark");

首先初始化数组

在添加元素时，调用add方法，需要扩容时，默认扩容为原数组的2倍，还可在构造方法中指定扩容的大小

• 相同点：
  • ArrayList和Vector默认初始化容量等于10
  • 底层都是基于数组实现
  • 都是List接口下的子类
• 不同点：
  • ArrayList线程不安全，Vector线程安全
  • ArrayList每次扩容是原来容量的1.5倍，Vector每次扩容是原来容量的2倍且可以设置每次扩容的容量
  • ArrayList是通过懒加载的形式初始化容量，Vector直接通过构造函数初始化数组

数据结构—链表

数组数据结构：根据下标查询效率非常高，但是增加删除的效率非常低

而链表弥补了数组的缺点，增加、删除的效率非常高，但是查询的效率非常低

node1.next = node2

node2.next = node3

以此类推

当我们需要添加或者删除时，仅仅需要改变指针指向即可。

链表分为单向链表、双向链表、环形链表。

• 单向链表

  public class Node<E> {
      /**
       * node节点元素值
       */
      private E value;
      /**
       * 当前节点指向下一个节点
       */
      Node<E> next;
  
      public static void main(String[] args) {
          Node<String> node3 = new Node<>();
          node3.value = "3";
          Node<String> node2 = new Node<>();
          node2.value = "2";
          node2.next = node3;
          Node<String> node1 = new Node<>();
          node1.value = "1";
          node1.next = node2;
          System.out.println(node1.next.value);
      }
  }
  

  遍历单向链表：

  /**
   * 根据传入的头节点 从头遍历到尾部
   *
   * @param node 初始节点
   */
  public static void showNode(Node<?> node) {
      //当前node节点 从头节点开始
      Node<?> cuNode = node;
      while (cuNode != null) {
          System.out.println(cuNode.value);
          //当前node节点的下个节点赋值给cuNode
          cuNode = cuNode.next;
      }
  }
  

  新增节点

  只需要找到链表的最后一个节点 .next == 新增节点，不需要考虑扩容问题

  /**
   * 新增节点
   *
   * @param tailNode 尾节点
   * @param node     新增节点
   */
  public static void addNode(Node<String> tailNode, Node<String> node) {
      tailNode.next = node;
  }
  

  删除节点仅需要改变指针指向即可

  node1.next = node3; //删除node2节点
  showNode(node1);
  

• 双向链表

  public class NodeS<E> {
      /**
       * node节点元素值
       */
      private E value;
      /**
       * 当前节点指向下一个节点
       */
      NodeS<E> next;
  
      /**
       * 当前节点指向上一个节点
       */
      NodeS<E> pred;
  
      public static void main(String[] args) {
          NodeS<String> node3 = new NodeS<>();
          node3.value = "3";
          NodeS<String> node2 = new NodeS<>();
          node2.value = "2";
          NodeS<String> node1 = new NodeS<>();
          node1.value = "1";
          node1.next = node2;
          node2.next = node3;
          node3.pred = node2;
          node2.pred = node1;
          showNode(node1);
      }
  
      /**
       * 根据传入的头节点 从头遍历到尾部
       *
       * @param node 头节点
       */
      public static void showNode(NodeS<?> node) {
          //当前node节点 从头节点开始
          NodeS<?> cuNode = node;
          while (cuNode != null) {
              System.out.println(cuNode.value);
              //当前node节点的下个节点赋值给cuNode
              cuNode = cuNode.next;
          }
      }
  
      /**
       * 新增节点
       *
       * @param tailNode 尾节点
       * @param node     新增节点
       */
      public static void addNode(NodeS<String> tailNode, NodeS<String> node) {
          tailNode.next = node;
          node.pred = tailNode;
      }
  }
  

LinkedList基本使用

public static void main(String[] args) {
    List<String> linkedList = new LinkedList<>();
    linkedList.add("mark0");
    linkedList.add("mark1");
    linkedList.add("mark2");
    linkedList.add("mark3");
    System.out.println(linkedList.get(0));
    System.out.println(linkedList.size());
    Iterator<String> iterator = linkedList.iterator();
    while (iterator.hasNext()){
      System.out.println(iterator.next());
    }

    linkedList.set(1,"666");
    System.out.println("--------------");
    Iterator<String> iterator1 = linkedList.iterator();
    while (iterator1.hasNext()){
      System.out.println(iterator1.next());
    }

    linkedList.remove("mark3");
    System.out.println("--------------");
    Iterator<String> iterator2 = linkedList.iterator();
    while (iterator2.hasNext()){
      System.out.println(iterator2.next());
    }

    linkedList.remove(2);
    System.out.println("--------------");
    Iterator<String> iterator3 = linkedList.iterator();
    while (iterator3.hasNext()){
      System.out.println(iterator3.next());
    }
}

/*
mark0
4
mark0
mark1
mark2
mark3
--------------
mark0
666
mark2
mark3
--------------
mark0
666
mark2
--------------
mark0
666
*/

LinkedList底层基于双向链表实现，增删效率非常高，查询效率非常低。

那么，LinkedList的方法底层是如何实现的呢？

LinkedList源码解读分析

1. LinkedList是双向链表实现的list
2. LinkedList是非线程安全的
3. LinkedList元素允许为null，允许重复元素
4. LinkedList是基于链表实现的，因此插入删除效率高，查找效率低
5. LinkedList是基于链表实现的，因此不存在容量不足的问题，所以没有扩容方法
6. LinkedList还实现了栈和队列的操作方法，因此也可以作为栈、队列和双端队列来使用

add添加方法：

手写：

public class MarkLinkedList<E> {
    /**
     * 第一个节点
     */
    private Node<E> first;
    /**
     * 尾节点
     */
    private Node<E> last;

    /**
     * 链表大小
     */
    private int size = 0;

    private static class Node<E> {
        /**
         * 当前节点的值
         */
        private E item;
        /**
         * 上一个节点
         */
        private Node<E> prev;
        /**
         * 下一个节点
         */
        private Node<E> next;

        /**
         * 有参构造方法
         *
         * @param prev 当前节点的上一个节点
         * @param item 当前节点的值
         * @param next 当前节点的下一个节点
         */
        public Node(Node<E> prev, E item, Node<E> next) {
            this.item = item;
            this.prev = prev;
            this.next = next;
        }
    }

    public void add(E e) {
        //获取最后一个节点
        Node l = last;
        //创建一个新的节点
        Node<E> newNode = new Node<>(null, e, null);
        //设置最后一个节点为新节点
        last = newNode;
        //如果链表没有最后一个节点，列表为空
        if (l == null) {
            first = newNode;
        } else {
            //调用add方法创建一个新的node节点时，l的下一个节点为新节点，新节点的上一个节点为l
            l.next = newNode;
            newNode.prev = l;
        }
        //链表大小 +1
        size++;
    }

    public static void main(String[] args) {
        MarkLinkedList<String> linkedList = new MarkLinkedList<>();
        linkedList.add("Mark1");
        linkedList.add("Mark2");
        linkedList.add("Mark3");
    }
}

get查询方法

采用折半查询

/**
 * 根据index查询链表中对应的node节点
 *
 * @param index 所要查询节点的下标
 * @return 查询节点
 */
Node<E> node(int index) {
    //折半查询
    if (index < size >> 1) {
        //查询链表中间值的左边
        Node<E> f = first;
        for (int i = 0; i < index; i++) {
            f = f.next;
        }
        return f;
    } else {
        //查询链表中间值的右边
        Node<E> l = last;
        for (int i = size - 1; i > index; i--) {
            l = l.prev;
        }
        return l;
    }
}

public E get(int index){
    //下标越界需要报错
    return node(index).item;
}

remove删除方法

如果根据index下标删除，需要先查询到对应的node节点，时间复杂度是O(n)

删除链表节点效率确实很高，比ArrayList高，因为ArrayList删除元素需要移动数组

public E remove(int index) {
    //异常处理：下标越界需要报错
    return unlink(node(index));
}

public E unlink(Node<E> node) {
    //获取删除的node节点及其上一个和下一个节点
    final E element = node.item;
    Node<E> prev = node.prev;
    Node<E> next = node.next;
    //如果删除的节点上一个节点为空，则删除的是头节点
    if (prev == null) {
        first = next;
        first.prev = null;
    } else {
        //删除的不是头节点
        //删除节点的上一个节点.next = 删除节点的下一个节点
        prev.next = next;
        //删除节点的下一个节点.prev = 删除节点的上一个节点
        next.prev = prev;
    }
    //如果删除的节点下一个节点为空，则删除的是尾节点
    if (next == null) {
        last = prev;
        last.next = null;
    } else {
        //删除的不是尾节点
        //删除节点的下一个节点.prev = 删除节点的上一个节点
        next.prev = prev;
        //删除节点的上一个节点.next = 删除节点的下一个节点
        prev.next = next;
    }
    size--;
  	// GC回收
    node.item = null;
    return element;
}

Map集合基本特点

Map是一个接口：Interface Map<k,v>

Map集合特点：

• 键值对映射关系

• 一个键对应一个值

• 键不允许重复，值可以重复

• 散列存放数据，所以会存在散列问题，遍历数据与存储顺序不一致

  例如：HashMap元素存取无序，而LinkedHashMap存取有序

public static void main(String[] args) {
    Map<String,String> hashMap = new HashMap<>();
    hashMap.put("mark001","嫦娥");
    hashMap.put("mark002","王昭君");
    hashMap.put("mark003","扁鹊");
    System.out.println(hashMap);
    //如果key存在，则修改对应的value值
    hashMap.put("mark003","CC");
    System.out.println(hashMap);
}
/*
{mark002=王昭君, mark001=嫦娥, mark003=扁鹊}
{mark002=王昭君, mark001=嫦娥, mark003=CC}
*/

Map集合的常用方法

HashSet集合用法

• HashSet集合实现了Set接口

  

• HashSet基于HashMap实现，是一个不允许有重复元素的集合，因为add方法底层采用HashMap集合的key来存放，而HashMap的Key值不允许重复

• HashSet允许有null值，因为HashMap允许key为null

• HashSet是不保证有序的，即不会记录插入的顺序，因为HashMap是散列存放的

• HashSet没有get方法，所以不能用普通for循环遍历，但是可以用foreach遍历

public static void main(String[] args) {
    HashSet<String> strings = new HashSet<>();
    strings.add("mark01");
    strings.add("mark02");
    strings.add("589562");
    strings.add("mark04");
    strings.add("475458");
    strings.add("m85guu");
    Iterator<String> iterator = strings.iterator();
    while (iterator.hasNext()) {
      System.out.println(iterator.next());
    }
}
/*
mark01
m85guu
mark02
589562
mark04
475458
*/

手写HashSet集合

HashSet底层基于HashMap实现，元素的值就是HashMap的key

private HashMap<E, Object> map;
private static final Object PRESENT = new Object();

public MarkHashSet() {
    map = new HashMap<>();
}

public void add(E e) {
    map.put(e, PRESENT);
}

@Override
public String toString() {
    return "MarkHashSet{" +
            "map=" + map +
            '}';
}

public static void main(String[] args) {
    MarkHashSet<String> markHashSet = new MarkHashSet<>();
    markHashSet.add("哈哈哈");
    markHashSet.add( "呵呵呵");
    System.out.println(markHashSet);
}
//MarkHashSet{map={哈哈哈=java.lang.Object@506e1b77, 呵呵呵=java.lang.Object@506e1b77}}

Map集合的获取方法

public static void main(String[] args) {
   Map<String, String> hashMap = new HashMap<>();
   hashMap.put("英雄1", "诸葛亮");
   hashMap.put("英雄2", "王昭君");
   hashMap.put("英雄3", "嫦娥");
   //1.根据键获取值
   System.out.println("根据键获取值");
   System.out.println(hashMap.get("英雄1"));

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

   //2.获取所有键的集合（返回Set集合）
   System.out.println("获取所有键的集合（返回Set集合）");
   Set<String> keys = hashMap.keySet();
   for (String key : keys) {
     System.out.println(key);
   }

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

   //3.获取所有值的集合（返回Collection集合）
   System.out.println("获取所有值的集合（返回Collection集合）");
   Collection<String> values = hashMap.values();
   for (String value : values) {
     System.out.println(value);
   }

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

   //4.获取所有键值对象的集合
   System.out.println("获取所有键值对象的集合");
   Set<Map.Entry<String, String>> entries = hashMap.entrySet();
   //HashMap底层键值对通过Map接口中的Entry对象进行封装
   for (Map.Entry<String, String> entry : entries) {
     System.out.println(entry);
   }

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

   //5.如果存在相应的key则返回其对应的value，否则返回给定的默认值defaultValue
   String getordefault = hashMap.getOrDefault("英雄5", "默认英雄");
   System.out.println(getordefault);
}

Map集合的遍历

• 方式一

  先获取HashMap的所有键值，就可以调用get方法根据键值获取对应的value值

  Set<String> keys = hashMap.keySet();
  for (String key : keys) {
      System.out.println(key+":"+hashMap.get(key));
  }
  

• 方式二

  entrySet()方法：将键值对封装为entry对象

  Set<Map.Entry<String, String>> entries = hashMap.entrySet();
  for (Map.Entry<String, String> entry : entries) {
      //System.out.println(entry.getKey()+":"+entry.getValue());
      System.out.println(entry);
  }
  

• 方式三（了解即可）

  Set<Map.Entry<String, String>> entries1 = hashMap.entrySet();
  Iterator<Map.Entry<String, String>> iterator = entries1.iterator();
  while (iterator.hasNext()) {
      Map.Entry<String, String> entry = iterator.next();
      //System.out.println(entry.getKey()+":"+entry.getValue());
      System.out.println(entry);
  }
  

hashCode方法

• hashCode方法是Object父类提供的方法，hashcode方法返回该对象的哈希码值。支持该方法是为哈希表提供一些优点，例如，java.util.Hashtable 提供的哈希表。
• hashCode的常规协定是:在Java应用程序执行期间，在同一对象上多次调用hashCode方法时，必须一致地返回相同的整数。
• hashCode的存在主要是用于查找的快捷性，如Hashtable，HashMap等 ，hashCode是用来在散列存储结构中确定对象的存储地址的。
• 如果equals方法比较相等，则HashCode值也一定相等 ，但是HashCode值相等不代表equals比较也相等。
• 如果类中重写了equals方法，必须要重写hashCode方法

在之前我们学习过equals方法，很多人认为equals就是在比较两个对象的值是否相等，这是错误的。

public static void main(String[] args) {
    String str1 = "mark";
    String str2 = "mark";
    System.out.println(str1.equals(str2));
    MarkEntiry mark1 = new MarkEntiry("mark", 22);
    MarkEntiry mark2 = new MarkEntiry("mark", 22);
    System.out.println(mark1.equals(mark2));
}

可以发现，对象mark1和mark2的值是完全一样的，但是使用equals比较返回的值却为false。

equals属于Object父类中，默认情况下比较两个对象的内存地址是否相同。因为new了两个mark对象，所以两个对象的内存地址不相同，equals的结果也就为false。那为什么str1和str2的equals为true呢。因为String类重写了父类Object中的equlas，用来比较两个字符串是否相同。如果想能够实现两个对象的成员属性是否相等，需要重写。而重写equlas方法是需要重写hashCode方法的。IDEA工具可以帮助我们自动重写equals和hashcode方法。

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

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

手写equals和hashCode的重写

/**
 * 重写父类中的equals方法，比较两个对象的成员属性值是否相同
 *
 * @param o 比较的对象
 * @return 属性值是否相同
 */
@Override
public boolean equals(Object o) {
    //先判断两个对象的内存地址是否相等
    if (this == o) {
        return true;
    }
    MarkEntiry mark = (MarkEntiry) o;
    //比较两个对象的成员属性值是否相等
    if (this.name.equals(mark.name) && this.age.equals(mark.age)) {
        return true;
    }
    return false;
}

@Override
public int hashCode() {
    return this.name.hashCode()+this.age.hashCode();
}

此时再用equals比较两个对象返回的就是true了，两个对象的hashCode值也相等，但是如果不重写hashCode方法，两个对象的hashCode值是不相等的，违背了equals方法比较两个对象相等，则hashCode值也一定相等这条规则，因此在重写equals方法时一定要重写hashCode方法

那到底什么是hashCode？

• hashCode属于Object父类，java虚拟机给每个对象生成一个整数int类型的hashCode值。

• 如果equals方法比较两个对象相等，则hashCode值也一定相等

• 但是两个对象hashCode值相等不代表equals相等

• 如果两个对象的hashCode值相等，但是值不相等，称为hash冲突问题

  String strA = "a";
  Integer int97 = 97;
  System.out.println(strA.hashCode());
  System.out.println(int97.hashCode());
  System.out.println(strA.equals(int97));
  /*
  97
  97
  false
  */
  

基于ArrayList实现HashMap底层

public class MarkArrayListHashMap<K, V> {
    /**
     * 创建一个容器存放键值对
     */
    private ArrayList<Entry<K, V>> arrayListEntry = new ArrayList<>();

    /**
     * Entry对象存放键值对
     */
    class Entry<K, V> {
        K key;
        V value;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    public void put(K k, V v) {
        arrayListEntry.add(new Entry<>(k, v));
    }

    public V get(K k) {
        for (Entry<K, V> entry :
                arrayListEntry) {
            if (entry.key.equals(k)) {
                return entry.value;
            }
        }
        return null;
    }
}

并不推荐使用ArrayList实现HashMap，这样的效率是非常低的。

缺点：

1. 查找的效率太低了，get方法使用遍历，从头查询到尾部

优点：

1. 可以保证存放的键值对是有序存放，不是散列

HashMap集合常见面试题

1. HashMap的key是否可以为自定义对象？

   可以。

2. HashMap存储数据是有序还是无序？

   无序。在HashMap集合中，计算key对应的index值是散列的

3. HashMap是否可以存放null值？如果可以，存放在数组的那个位置？

   可以（HashTable不可以），存放在数组的index = 0 的位置

4. HashMap键值对如何封装的

   通过Map接口封装的Entry对象来封装

基于哈希表实现HashMap集合

HashMap集合1.7版本是基于数组+链表实现的

HashMap集合1.8版本是基于数组+链表+红黑树实现的

public class MarkHashMap<K, V> {
    /**
     * 假设数组的容量为10000（实际上没有10000，会有扩容机制）
     */
    private Entry[] entries = new Entry[10000];

    /**
     * Entry对象存放键值对
     */
    class Entry<K, V> {
        /**
         * 键
         */
        K key;
        /**
         * 值
         */
        V value;
        /**
         * key的hash值
         */
        int hash;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    public void put(K k, V v) {
        //根据key的hashCode 取余entries.length  余数就是key存放在数组中对应的index的位置
        int index = k.hashCode() % entries.length;
        entries[index] = new Entry<>(k, v);
    }

    public V get(K k) {
        //根据key查询
        int index = k.hashCode() % entries.length;
        return (V) entries[index].value;
    }
}

hashMap集合底层更具hash算法进行查询和存放的效率很高，时间复杂度为O(1)

hash冲突问题

hashCode值相同，但是值不同，例如key = ‘a’和key = 97，最终计算的index是相同的，都是97。

在jdk1.7中，使用链表解决hash冲突问题。在key = ‘a’之后添加key = 97。在index = 97处形成一个链表，key不同，但是hashCode都相同。

public void put(K k, V v) {
    //先判断该index位置是否有存放链表
    int hash = k.hashCode();
    int index = hash % entries.length;
    Entry oldEntry = entries[index];
    if (oldEntry == null) {
      //如果取不出该Entry对象，则该index位置为空，可以直接将其存放
      entries[index] = new Entry<>(k, v, hash);
    } else {
      //如果能够取出该Entry对象，则追加在后面形成链表
      oldEntry.next = new Entry<>(k, v, hash);
    }
  }

  public V get(K k) {
    //根据key查询
    int hash = k.hashCode();
    int index = k.hashCode() % entries.length;
    for (Entry<K, V> entry = entries[index]; entry != null; entry = entry.next) {
      if (entry.hash == hash && (entry.key == k || entry.key.equals(k))) {
        return entry.value;
      }
    }
    return null;
}

HashMap统计字符串中每个字符出现的次数

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    String str = scanner.nextLine();

    Map<Character, Integer> hashMap = new HashMap<>();
  	//将字符串中的每一个字符视为key，出现的次数视为value
    for (int i = 0; i < str.length(); i++) {
        //遍历字符串，拆分每一个字符
        Character key = str.charAt(i);
        //根据key获取值，即获取出现的次数
        Integer value = hashMap.get(key);
        if (value == null){
		   //如果value为空，即还未出现过该字符，设置value为1，即出现次数为1
            value = 1;
        }else{
          	//如果查询到了该字符，则出现次数value++
            value ++;
        }
      	//保存或修改字符对应出现次数value的值
        hashMap.put(key,value);
    }

    Set<Map.Entry<Character, Integer>> entries = hashMap.entrySet();
    for (Map.Entry<Character, Integer> entry : entries) {
        System.out.println(entry.getKey()+"出现次数为"+entry.getValue());
    }
}

Collentions单列集合操作工具类

Collections是集合操作的工具类，操作Collection单列集合

Collection类的常用方法

public static void main(String[] args) {
    ArrayList<Integer> arrayList = new ArrayList<>();
    arrayList.add(88);
    arrayList.add(82);
    arrayList.add(12);
    arrayList.add(35);
    arrayList.add(75);
    arrayList.add(76);
    //升序排序
    Collections.sort(arrayList);
    for (Integer integer : arrayList) {
        System.out.println(integer);
    }

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

    //顺序反转
    Collections.reverse(arrayList);
    for (Integer integer : arrayList) {
        System.out.println(integer);
    }

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

    //随机顺序
    Collections.shuffle(arrayList);
    for (Integer integer : arrayList) {
        System.out.println(integer);
    }
}

LinkedHashMap

LinkedHashMap与HashMap集合的用法都是相同的，LinkedHashMap有序。

LinkedHashMap继承自HashMap，它的多种操作都是建立在HashMap操作的基础上的，同HashMap不同的是，LinkedHashMap维护了一个Entry的双向链表，保证了插入的Entry的顺序

LinkedHashSet

LinkedHashSet 是Set集合的一个实现，具有set集合不重复的特点，与HashSet不同的是，可以保证元素的顺序，也就是遍历顺序和插入顺序是一致的。

LinkedHashSet底层基于LinkedHashMap实现

• 手写LinkedHashSet集合

  private LinkedHashMap<E, Object> linkedHashMap;
  private static final Object PRESENT = new Object();
  
  public MarkLinkedHashSet() {
      linkedHashMap = new LinkedHashMap<>();
  }
  
  public void add(E e) {
      linkedHashMap.put(e, PRESENT);
  }
  
  @Override
  public String toString() {
      return "MarkLinkedHashSet{" +
              "linkedHashMap=" + linkedHashMap +
              '}';
  }
  

原文地址：http://www.cnblogs.com/hackertyper/p/16850664.html