容器

2020-08-15 阅读量

容器/集合的基本概念

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

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

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

泛型

泛型是JDK1.5以后增加的，他可以帮助我们建立类型安全的集合。

泛型的本质就是“数据类型的参数化”。我们可以吧“泛型”理解为数据类型的一个占位符（形式参数），即告诉编译器，在调用泛型时必须传入实际类型。

package cn.yishan.collection;

/**
* 测试泛型
* @author yishan
*/
public class TestGeneric {
    public static void main(String[] args) {
        MyCollection<String> mc = new MyCollection<String>();

        mc.set("杨亦山",0);

        String b = mc.get(0);
    }
}

class MyCollection<E>{
    Object[] objs = new Object[5];

    public void set(E e,int index){
        objs[index] = e;
    }
    public E get(int index){
        return (E) objs[index];
    }
}

容器中方法

package cn.yishan.collection;

import java.util.*;

/**
* 测试Collection接口中的方法
* @author yishan
*/
public class TestList {
    public static void main(String[] args) {           
        test01();
    }
    public static void test01(){
        Collection<String> c = new ArrayList<>();

        System.out.println(c.size());
        System.out.println(c.isEmpty());

        c.add("杨大侠");
        c.add("杨大帅");
        System.out.println(c);
        System.out.println(c.size());
        //判断是否包含字符串内容
        System.out.println(c.contains("杨大侠"));
        Object[] obj = c.toArray();
        System.out.println(obj);
        //移除容器里面的对象，并不是删除
        c.remove("杨大帅");
        System.out.println(c);
        //移除容器内所有的元素
        c.clear();
        System.out.println(c.size());
    }       
}

ArrayList_操作多个List_并集和交集

public static void test02(){
            List<String> list01 = new ArrayList<>();
            list01.add("aa");
            list01.add("bb");
            list01.add("cc");

            List<String> list02 = new ArrayList<>();
            list02.add("aa");
            list02.add("dd");
            list02.add("ee");

            System.out.println("list01:"+list01);
            //把另外一个集合的所有的元素都加进来
            //list01.addAll(list02);
            //移除两个集合相同的部分
            //list01.removeAll(list02);
            //取交集
            list01.retainAll(list02);

            System.out.println("list01:"+list01);
            //查看一个集合是否包含另外一个集合
            System.out.println(list01.containsAll(list02));

        }

ArrayList_索引和顺序相关方法

List是有序，可重复的容器

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

可重复：List允许加入重复的元素。更确切的讲，List通常允许满足e1.equals(e2)的元素重复加入容器。

List接口常用的实现类有3个：ArrayList(底层实现是数组)、LinkedList（底层是链表）和Vector（底层也是数组，线程安全）。

private static void test03() {
        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");
        System.out.println(list);
        //在指定的相应的索引处插入字符
        list.add(2,"我");
        System.out.println(list);
        //在指定的相应的索引处删除字符
        list.remove(2);
        System.out.println(list);
        //在指定的相应的索引处修改字符
        list.set(2,"杨大帅");
        System.out.println(list);
        //获取指定的相应索引处的字符
        System.out.println(list.get(2));

        list.add("C");
        list.add("B");
        list.add("A");
        System.out.println(list);
        //查找该字符，返回该字符第一次出现的索引位置，不存在返回-1
        System.out.println(list.indexOf("B"));
        //查找该字符，返回该字符最后一次出现的索引位置，不存在返回-1
        System.out.println(list.lastIndexOf("B"));
    }

ArrayList 源码解读

ArrayList底层是用数组实现的存储。特点：查询效率高，增删效率低，线程不安全。我们一般使用它。

数组长度是有限的，而ArrayList是可以存放任意数量的对象，长度不受限制，那么他是怎么实现的呢？ 数组扩容

扩容长度为原数组长度右移一位，相当于扩容原数组长度的一半

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        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);
    }

remove方法

数组拷贝数组下标控制位置，自我拷贝，覆盖需要删除的元素

public E remove(int index) {
    rangeCheck(index);

        modCount++;
    E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        elementData[--size] = null; // clear to let GC do its work
    return oldValue;
    }

clear方法

循环遍历，依次赋值为null,即清空所有元素

public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        	size = 0;
    }

扩展

ArrayList的增删未必就是比LinkedList要慢。

如果增删都是在末尾来操作【每次调用的都是remove()和add()】，此时ArrayList就不需要移动和复制数组来进行操作了。如果数据量有百万级的时，速度是会比LinkedList要快的。
如果删除操作的位置是在中间。由于LinkedList的消耗主要是在遍历上，ArrayList的消耗主要是在移动和复制上(底层调用的是arraycopy()方法，是native方法)。
- LinkedList的遍历速度是要慢于ArrayList的复制移动速度的
- 如果数据量有百万级的时，还是ArrayList要快。