day18 java 集合Collection的List和Set

Collection分成List和Set
    |------Collection
        |-------List : 存储的元素是有序的并且可以重复
            |--------ArrayList
            |--------LinkedList
            |--------Vector
        |-------Set :  存储的元素是无序的并且不可以重复
            |--------HashSet
                    |--------LinkedHashSet
            |--------TreeSet

List接口

List常用的实现类有 ： ArrayList LinkedList Vector

1.List是单列集合

2.List继承了Collection接口

3.List中存放的元素是有序可重复的

ArrayList

[面试题]ArrayList的底实现？
    当我们通过ArrayList的空参构造器创建对象时底层会创建一个长度为0的Object[]。
    当我们第一次向该对象中添加元素时底层会扩容 扩容的长度为10(原来的长度是0).
    当我们向该对象中添加第11个元素时底层会再次扩容扩容为原来的1.5倍。并且将原来的数组中的元素
copy到当前数组中。

Collection c = new ArrayList();

List list = new ArrayList();

ArrayList list = new ArrayList(100);//可以指定初始化时的数组的长度。

方法API看上一章day17

LinkedList

说明：LinkedList底层是一个双向链表

ArrayList和LinkedList如何选择?

如果对集合中的数据只是查询或修改比较多那么可以选择ArrayList 如果对集合中的数据增，删的操作比较多那么可以使用LinkedList

[面试题] ArrayList和LinkedList的区别？

ArrayList底层是数组，LinkedList底层是双向链表

@Test
    public void test2(){
        LinkedList list = new LinkedList();
        list.add("a");
        list.add("b");
        list.add("c");

        //在链表的第一个位置添加元素
        list.addFirst("e");
        System.out.println(list);

        //在链表的最后一个位置添加元素
        list.addLast("f");
        System.out.println(list);

        //删除链表中的最后一个元素
        list.removeLast();
        System.out.println(list);

        //删除链表中的第一个元素
        list.removeFirst();
        System.out.println(list);
    }

队列：Queue queue = new LinkedList();

双端队列：Deque d = new LinkedList();

Vector

    1.Vector是List接口的实现类
    2.Vector的底层是数组（Object[]）

[面试题] ArrayList和Vector的区别？
    1.ArrayList和Vector底层都是Object[]
    2.ArrayList是线程不安全的，Vector是线程安全的。
    3.ArrayList空参构造器创建的是一个长度为0的数组，Vector空参构造器创建的是一个长度为10的数组
        ArrayList扩容为原来的1.5倍。Vector默认扩容为原来的2倍（也可以指定扩容大小）

/*
    第1个参数 ：数组初始化长度
    第2个参数 : 指定数组扩容的大小
 */
Vector vector = new Vector(10,20);

Stack存储的数据的特点： 先进后出

说明 ：Stack是Vector的子类

Stack s = new Stack();

Set

1.Set继承了Collection接口
2.Set是单列集合
3.Set存储的元素无序并且不可以重复
    无序性 ：是因为存放的元素的位置是根据hash值计算出的-计算出的值（0 到 数组的长度-1）没有序
    不可重复 ：是通过equals方法进行比较的结果。如果为true说明重复如果为false说明不重复。
4.Set的元素的遍历Iterator和增强for循环
5.Set中并没有再增加其它方法
5.Set的主要实现类 ：HashSet LinkedHashSet TreeSet

HashSet

HashSet的底层是Hash表（数组 + 链表 + 红黑树）

注意：HashSet中如果存放的是自定义类的对象那么该对象所属的类必须重写equals和hashCode方法。

思考？ 如何要数据不重复得怎么做 - HashSet？（类散列表）
    当我们向集合中存放数据a时会先调用a的hashCode方法得出一个在数组中存放的位置
 如果该位置没有其它元素则直接放入到该位置。如果该位置已经存在了其它元素b时。那么会调用
 a的equals方法和b进行比较，如果返回的结果为false说明a和b不一样则以链表的形式存式。
 如果返回的结果为true则说明a和b是一样的则不能放入。

当我们向Set中放数据  第1步是找位置  第2步是比较内容

LinkedHashSet

LinkedHashSet :
    LinkedHashSet是HashSet的子类。LinkedHashSet和HashSet的底层实现是一样的。
 只不过LinkedHashSet的底层维护了一张链表（双向链表） 通过该链表就可以按照添加的元素顺序进行遍历

TreeSet

TreeSet :
    1.TreeSet底层是红黑树
    2.TreeSet的作用是用来对元素进行排序
    3.TreeSet中存放的元素的类型必须是同一类型
    4.TreeSet的排序-自然排序 vs 定制排序

public class SetTest3 {

    @Test
    public void test(){
        TreeSet<String> set = new TreeSet<>();
        set.add("c");
        set.add("a");
        set.add("b");
        set.add("d");

        System.out.println(set);
    }

    @Test
    public void test2(){
        TreeSet set = new TreeSet();
        set.add("c");
        set.add(1);
        set.add(2);
        set.add("d");

        System.out.println(set);
    }

    /*
        自然排序 - 自定义的类实现Comparable接口
     */
    @Test
    public void test3(){
        TreeSet<Student> set = new TreeSet<>();
        set.add(new Student("c",1));
        set.add(new Student("d",5));
        set.add(new Student("a",3));
        set.add(new Student("b",2));
        set.add(new Student("k",2));
        set.add(new Student("f",2));

        System.out.println(set);
    }

    /*
        定制排序 - 将Comparator接口的实现类的对象传到TreeSet的构造器即可
     */
    @Test
    public void test4(){
        //如果使用定制排序那么自定义类就不需要实现Comparable接口
        //如果两种都有 --- 定制排序生效
        TreeSet<Student> set = new TreeSet<>(new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                return o1.name.compareTo(o2.name);
            }
        });
        set.add(new Student("c",1));
        set.add(new Student("d",5));
        set.add(new Student("a",3));
        set.add(new Student("b",2));
        set.add(new Student("k",2));
        set.add(new Student("f",2));

        System.out.println(set);
    }
}

class Student implements Comparable<Student>{
    String name;
    int id;

    public Student(String name, int id) {
        this.name = name;
        this.id = id;
    }

    @Override
    public String toString() {
        return id + " " + name;
    }

    /*
        按照id排序 如果id相同再按照name排序。

    @Override
    public int compareTo(Student o) {
        int cid = this.id - o.id;
        if (cid == 0){
            return this.name.compareTo(o.name);
        }
        return cid;
    }

     */

    @Override
    public int compareTo(Student o) {
        return this.id - o.id;
    }
}