容器和数据结构

1、泛型 Generics

容器的概述

---

开发和学习中需要时刻和数据打交道，如何组织这些数据是我们编程中重要的内容。 我们一般通过"容器"来容纳和管理数据。那什么是"容器"呢? 生活中的容器不难理解，是用来容纳物体的，如锅碗瓢盆、箱子和包等。程序中的 "容器" 也有类似的功能，就是用来容纳和管理数据的。

数组就是一种容器，可以在其中放置对象或基本类型数据。

数组的优势：是一种简单的线性序列，可以快速地访问数组元素，效率高。如果从效率和类型检查的角度讲，数组是最好的。

数组的劣势：不灵活。容量需要事先定义好，不能随着需求的变化而扩容。比如：我们在一个用户管理系统中，要把今天注册的所有用户取出来，那么这样的用户有多少个?我们在写程序时是无法确定的。因此，在这里就不能使用数组。

基于数组并不能满足我们对于 "管理和组织数据的需求"，所以我们需要一种更强大、更灵活、容量随时可扩的容器来装载我们的对象。 这就是我们今天要学习的容器，也叫集合(Collection)。

以下是容器的接口层次结构图：

泛型

---

泛型是JDK1.5以后增加的，它可以帮助我们建立类型安全的集合。提高了代码可读性和安全性。

泛型的本质就是 "数据类型的参数化"。 我们可以把 "泛型" 理解为数据类型的一个占位符(形式参数)，即告诉编译器，在调用泛型时必须传入实际类型。这样，在存储数据、读取数据时都避免了大量的类型判断，非常便捷。

自定义泛型

---

我们可以在类的声明处增加泛型列表，如：<T,E,V>。

【示例 1-1】泛型的声明

class MyCollection<E> {  //E:表示泛型
    Object[] objs = new Object[5];

    public void set(E obj, int index) { //E:表示泛型
        objs[index] = obj;
    }

    public E get(int index) { //E:表示泛型
        return (E) objs[index];
    }
}

泛型E像一个占位符一样表示"未知的某个数据类型"，需要我们在真正调用的时候传入这个"数据类型"。

【示例 1-2】泛型的应用

public class TestGenerics {
    public static void main(String[] args) {
        //这里的"String"就是实际传入的数据类型
        MyCollection<String> mc = new MyCollection<String>();
        mc.set("张三", 0);
        mc.set("李四", 1);
        
        //加了泛型,直接返回String类型数据,不需要强制转换啦
        String str = mc.get(0);
        System.out.println(str);
    }
}

容器中的泛型

---

容器相关类都定义了泛型，我们在开发和工作中，在使用容器类时都要使用泛型。这样，在容器的存储数据、读取数据时都避免了大量的类型判断，非常便捷。

【示例 1-3】泛型类的在集合中的使用

//以下代码中List、Set、Map、Iterator都是与容器相关的接口
List list = new ArrayList();
Map map = new HashMap();
Set set = new HashSet();
Iterator iterator = set.iterator();

通过阅读源码，我们发现Collection、List、Set、Map、Iterator接口都定义了泛型。

2、Collection 接口

Collection 表示一组对象，它是集中、收集的意思。Collection接口的两个子接口是List、Set接口。

由于List、Set是Collection的子接口，意味着所有List、Set的实现类都有上面的方法。

3、List 特点和常用方法

List是有序、可重复的容器。

有序：List中每个元素都有索引标记。可以根据元素的索引标记(在List中的位置)访问元素，从而精确控制这些元素。

可重复：List允许加入重复的元素。

除了Collection接口中的方法，List多了一些跟顺序(索引)有关的方法，参见下表：

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

【示例 3-1】List的常用方法

public class TestList {
    //测试add/remove/size/isEmpty/contains/clear/toArrays等方法
    public static void main(String[] args) {
        List<String> c = new ArrayList<>();
        /*
           返回集合中元素的个数
         */
        int size = c.size();
        System.out.println("list的大小:"+size); //0

        /*
            如果集合中没有元素则返回 true
         */
        boolean empty = c.isEmpty();
        System.out.println("list集合是否为空:"+empty); //true

        /*
            向集合中添加元素
         */
        c.add("因为你的出现,我的世界变得如此精彩");
        c.add("helloworld");
        System.out.println(c); // [因为你的出现,我的世界变得如此精彩, helloworld]
        System.out.println("list的大小:"+size); //2

        /*
            判断集合中是否包含 “helloworld”这个元素
         */
        boolean contains = c.contains("helloworld");
        System.out.println("是否包含指定元素:"+contains);

        /*
            将集合中转换成 object 数组
         */
        Object[] objects = c.toArray();
        System.out.println("转化成Object数组:"+objects);

        /*
            移除集合中的 "helloworld" 这个元素
         */
        c.remove("helloworld");
        System.out.println(c); //[因为你的出现,我的世界变得如此精彩]
        System.out.println("list的大小:"+size); //1

        /*
            清除集合中所有元素
         */
        c.clear();
        System.out.println(c); //[]
        System.out.println("list的大小:"+size); //0
    }
}

执行结果如下：

【示例 3-2】两个List之间的元素处理

public class TestList2 {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("白豆五");
        list.add("张三");
        list.add("李四");

        List<String> list2 = new ArrayList<>();
        list2.add("王五");
        list2.add("赵六");
        list2.add("白豆五");

        /*
            判断 list 是否包含 list2 所用元素
         */
        System.out.println(list.containsAll(list2)); // false
        System.out.println("list集合:" + list); //list集合:[白豆五, 张三, 李四]

        /*
            将 list2 中所有元素都添加到 list 中
         */
        list.addAll(list2);
        System.out.println("list集合:" + list); //list集合:[白豆五, 张三, 李四, 王五, 赵六, 白豆五]

        /*
            从list中删除 同时在list和list2中存在的元素
         */
        list.removeAll(list2);
        System.out.println("list集合:" + list); //list集合:[ 张三, 李四]

        /*
            取list和list2的交集
         */
        list.retainAll(list2);
        System.out.println("list集合:" + list); //list集合:[]
    }
}

执行结果如下：

【示例 3-3】List中操作索引的常用方法

public class TestList3 {
    public static void main(String[] args) {
        test();
    }

    public static void test() {
        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");
        System.out.println("list集合：" + list); //list集合：[A, B, C, D]

        /*
           向指定位置插入“hello”这个元素,然后之前在该位置的元素会向右移
         */
        list.add(2, "hello");
        System.out.println("list集合：" + list); //list集合：[A, B, hello, C, D]

        /*
            移除list中指定位置的元素,然后它后面的元素会左移（索引-1）
         */
        list.remove(2);
        System.out.println("list集合：" + list); //list集合：[A, B, C, D]
        /*
           用指定的元素 “c” 替换此列表中指定位置的元素 “C”
         */
        list.set(2,"c");
        System.out.println("list集合：" + list); //list集合：[A, B, c, D]

        /*
            获取指定位置的元素
         */
        System.out.println(list.get(1)); //B

        /*
            list.indexOf("B") 从头开始获取元素 “B” 的位置
            list.lastIndexOf("B) 从末尾开始获取元素 “B” 的位置
         */
        list.add("B");
        System.out.println(list.indexOf("B")); // 1
        System.out.println(list.lastIndexOf("B")); //4
    }
}

执行结果如下：

4、ArrayList 特点和底层实现

ArrayList底层是用数组实现的。

特点：查询效率高，增删效率低，线程不安全。

接下来我们查看ArrayList的源码：

我们可以看出ArrayList底层使用Object数组来存储元素数据的。所有的方法，都围绕这个核心的Object数组来展开。

我们知道，数组长度是有限的，而ArrayList是可以存放任意数量的对象，长度不受限制，那么它是怎么实现的呢？

本质上就是通过定义新的更大的数组，将旧数组中的内容拷贝到新数组，来实现扩容。 ArrayList的Object数组初始化长度为10 ，如果我们存储满了这个数组，需要存储第11个对象，就会定义新的长度更大的数组，并将原数组内容和新的元素一起加入到新数组中，源码如下：

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

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

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

// 扩容机制
private void grow(int minCapacity) {
    // 老容量长度
    int oldCapacity = elementData.length;
    // 新容量长度 = 老容量长度 + (老容量长度/2)。 如:新容量长度=15
    int newCapacity = oldCapacity + (oldCapacity >> 1); // >>1表示 右移1位,相当于除以2
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 将elementData数组的元素拷贝新数组中,然后替换这个elementData
    elementData = Arrays.copyOf(elementData, newCapacity);
}

自定义实现 ArrayList

---

【示例 4-1】实现ArrayList容量的初始化，以及add()和toString()方法

/**
 * @ClassName: MyArrayList
 * @Description: 自定义实现ArrayList
 * @Author: 白豆五
 * Version: 1.0
 */
public class MyArrayList {
    // 核心数组
    private Object[] elementData;
    // 元素大小
    private int size;
    // 默认容量
    private static final int DEFAULT_CAPACITY = 10;

    public MyArrayList() {
        elementData = new Object[DEFAULT_CAPACITY];
    }

    public MyArrayList(int capacity) {
        elementData = new Object[capacity];
    }

    public void add(Object obj) {
        elementData[size++] = obj;

    }

    @Override
    public String toString() {
        // 可变的字符序列
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(elementData[i] + ",");
        }
        sb.setCharAt(sb.length() - 1, ']');
        return sb.toString();
    }

    public static void main(String[] args) {
        MyArrayList list = new MyArrayList();
        list.add("hello");
        list.add("world");

        System.out.println(list);
    }
}

执行结果如下：

【示例 4-2】增加了泛型, 增加数组扩容功能

package com.baidou.mycollection;

/**
 * @ClassName: MyArrayList2
 * @Description: 自定义实现ArrayList, 增加了泛型, 增加数组扩容功能
 * @Author: 白豆五
 * @Date: 2021/8/9 17:52
 * Version: 1.0
 */
public class MyArrayList2<E> {
    // 核心数组
    private Object[] elementData;
    // 元素大小
    private int size;
    // 默认容量
    private static final int DEFAULT_CAPACITY = 10;

    public MyArrayList2() {
        elementData = new Object[DEFAULT_CAPACITY];
    }

    public MyArrayList2(int capacity) {
        elementData = new Object[capacity];
    }

    public void add(E element) {
        //判断什么时候需要扩容
        if (size == elementData.length) {
            //扩容操作
            Object[] newArray = new Object[elementData.length + (elementData.length >> 1)];
            //数组拷贝
            System.arraycopy(elementData, 0, newArray, 0, elementData.length);
            elementData = newArray;
        }
        elementData[size++] = element;

    }

    @Override
    public String toString() {
        // 可变的字符序列
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(elementData[i] + ",");
        }
        sb.setCharAt(sb.length() - 1, ']');
        return sb.toString();
    }

    public static void main(String[] args) {
        MyArrayList2 list = new MyArrayList2();
        for (int i = 0; i < 20; i++) {
            list.add(i);
        }
        System.out.println(list);
        System.out.println("elementData.length:"+list.elementData.length);
    }
}

执行结果如下：

【示例 4-3】增加了set和get方法，增加了数组边界判断

public class MyArrayList3<E> {
    // 核心数组
    private Object[] elementData;
    // 元素大小
    private int size;
    // 默认容量
    private static final int DEFAULT_CAPACITY = 10;

    public MyArrayList3() {
        elementData = new Object[DEFAULT_CAPACITY];
    }

    public MyArrayList3(int capacity) {
        if (capacity < 0) {
            throw new RuntimeException("容器的容量不能为负数!");
        } else if (capacity == 0) {
            elementData = new Object[DEFAULT_CAPACITY];
        } else {
            elementData = new Object[capacity];
        }
    }

    public void add(E element) {
        // 判断什么时候需要扩容
        if (size == elementData.length) {
            //扩容操作
            Object[] newArray = new Object[elementData.length + (elementData.length >> 1)];
            //数组拷贝
            System.arraycopy(elementData, 0, newArray, 0, elementData.length);
            elementData = newArray;
        }
        elementData[size++] = element;
    }

    public E get(int index) {
        checkRange(index);
        return (E) elementData[index];
    }

    public void set(int index, E element) {
        //索引合法判断
        checkRange(index);
        elementData[index] = element;
    }

    private void checkRange(int index) {
        //索引合法判断
        if (index < 0 || index > size - 1) {
            //不合法
            throw new RuntimeException("索引不合法:" + index);
        }
    }

    @Override
    public String toString() {
        // 可变的字符序列
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(elementData[i] + ",");
        }
        sb.setCharAt(sb.length() - 1, ']');
        return sb.toString();
    }

    public static void main(String[] args) {
        MyArrayList3 list = new MyArrayList3();
        for (int i = 0; i < 40; i++) {
            list.add("hello" + i);
        }
        System.out.println(list);
        //list.set(40, "sfdsf");
        System.out.println(list.get(39));
    }
}

执行结果如下：

【示例 4-4】增加remove方法，增加了初始化容的判断，增加了size和isEmpty方法

public class MyArrayList4<E> {
    // 核心数组
    private Object[] elementData;
    // 元素大小
    private int size;
    // 默认容量
    private static final int DEFAULT_CAPACITY = 10;

    public MyArrayList4() {
        elementData = new Object[DEFAULT_CAPACITY];
    }

    public MyArrayList4(int capacity) {
        if (capacity < 0) {
            throw new RuntimeException("容器的容量不能为负数!");
        } else if (capacity == 0) {
            elementData = new Object[DEFAULT_CAPACITY];
        } else {
            elementData = new Object[capacity];
        }

    }

    public void add(E element) {
         //判断什么时候需要扩容
        if (size == elementData.length) {
            //扩容操作
            Object[] newArray = new Object[elementData.length + (elementData.length >> 1)];
            //数组拷贝
            System.arraycopy(elementData, 0, newArray, 0, elementData.length);
            elementData = newArray;
        }
        elementData[size++] = element;
    }

    public E get(int index) {
        checkRange(index);
        return (E) elementData[index];
    }

    public void set(int index, E element) {
        //索引合法判断
        checkRange(index);
        elementData[index] = element;
    }

    private void checkRange(int index) {
        //索引合法判断
        if (index < 0 || index > size - 1) {
            //不合法
            throw new RuntimeException("索引不合法:" + index);
        }
    }

    public void remove(E element) {
        // element,将它和容器中所有元素比较,获得第一个为true的,返回。
        for (int i = 0; i < size; i++) {
            if (element.equals(get(i))) { //容器中所有的比较操作,都是用的 equals 而不是 ==
                //将该元素从此处移除
                remove(i);
            }
        }
    }

    public void remove(int index) {
        /*
              a,b,c,d,e  比如删除 b,要从c开始拷贝
              abde
         */
        int numMoved = size - index - 1;
        if (numMoved > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        }
        elementData[--size] = null;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0 ? true : false;
    }

    @Override
    public String toString() {
        // 可变的字符序列
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(elementData[i] + ",");
        }
        sb.setCharAt(sb.length() - 1, ']');
        return sb.toString();
    }

    public static void main(String[] args) {
        MyArrayList4 list = new MyArrayList4();
        for (int i = 0; i < 20; i++) {
            list.add("hello" + i);
        }
        System.out.println("初始集合:" + list);
        System.out.println("元素个数为:" + list.size());
        System.out.println();
        list.set(15, "sfdsf");
        System.out.println("插入元素后的集合:" + list);
        System.out.println("元素个数为:" + list.size());
        System.out.println();
        list.remove("sfdsf");
        list.remove(0);
        System.out.println("移除元素后的集合:" + list);
        System.out.println("元素个数为:" + list.size());

        System.out.println("list是否为空:"+list.isEmpty());
    }
}

执行结果如下：