一、集合与数组的比较

二、集合结构继承图

集合分为两大类：
一类是单个方式存储元素，超级父接口是java.util.Collection;
一类是以键值对的方式存储元素，超级父接口是java.util.Map。
Collection和Map，是集合框架的根接口。

集合结构的继承需要熟练掌握。注意分清哪些是接口，哪些是实现类。

有序：指的是存进去的元素是这个顺序，取出来还是这个顺序；
无序：表示存进去是这个顺序，取出来就不一定是这个顺序。并且没有下标。
可重复：允许存放重复的元素；
不可重复：不允许存放重复的元素。即存进去1，就不能再存储1。

三、Collection接口

Collection接口是List接口和Set接口的父接口。Collection接口中定义了对集合进行增、删、改、查的方法，List接口和Set接口继承了这些方法。

四、List接口及其实现类

List是有序可重复的Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素。实现List接口的常用类有LinkedList，ArrayList，Vector。

List中特有的方法：

1.ArrayList类

底层是Object数组，所以ArrayList集合查询效率高，增删效率低。
（问：为什么数组检索效率高，增删效率低？
答：检索效率高是因为第一：Java的数组中存储的每个元素类型一致，也就是说每个元素占用的空间大小相同；第二：Java的数组中存储的每个元素的内存地址是连续状态的；第三：首元素的内存地址作为整个数组对象的内存地址，可见我们是知道首元素内存地址的；第四：数组中的元素是有下标的，有下标就可以计算出被查找的元素和首元素的偏移量。
增删效率低是因为往数组里某个下标位置增加元素需要把这个下标往后的元素后移一位，删除也同理。）
ArrayList自动扩容机制：初始容量为10，扩容后为原容量的1.5倍。

ArrayList类有三个构造方法：

Arraylist集合测试：

public static void main(String[] args) {
        // 创建ArrayList实例
        ArrayList<String> list = new ArrayList<>();
        // 给list添加元素
        for (int i=97; i<105; i++) {
            list.add(String.valueOf((char)i));
        }
        System.out.println("list数组的内容是" + list);
        System.out.println("list数组中元素个数为： " + list.size());
        list.set(0,"haha");
        System.out.println("list数组修改后的内容是： " + list);
        System.out.println("list数组中是否包含“a”： " + list.contains("a"));
        System.out.println("list数组下标为2的元素是： " + list.get(2));
        list.remove("c");
        System.out.println("list数组移除“c”后的内容是： " + list);

        // 遍历list集合
        for (String s : list) {
            System.out.printf("%s\t",s);
        }
 }

结果：

list数组的内容是[a, b, c, d, e, f, g, h]
list数组中元素个数为： 8
list数组修改后的内容是： [haha, b, c, d, e, f, g, h]
list数组中是否包含“a”： false
list数组下标为2的元素是： c
list数组移除“c”后的内容是： [haha, b, d, e, f, g, h]
haha	b	d	e	f	g	h	

2、LinkedList类

底层采用双向链表结构，优势在于高效地插入和删除其中的元素，但随机访问元素的速度较慢，特性与ArrayList刚好相反。如果程序需要反复对集合做插入和删除操作，应选择LinkedList类。

LinkedList类有两个构造方法：

LinkedList类还实现了Deque和Queue接口，实现了这两个接口中的指定的方法，用于处理首部和尾部的元素。可以利用LinkedList实现栈(stack)、队列(queue)、双向队列(double-ended queue )。 它具有方法addFirst()、addLast()、getFirst()、getLast()、removeFirst()、removeLast()等。

LinkedList集合测试：

public static void main(String[] args) {
        // 创建ArrayList实例
        ArrayList<String> list = new ArrayList<>();
        // 给list添加元素
        for (int i=97; i<105; i++) {
            list.add(String.valueOf((char)i));
        }
        System.out.println("list数组的内容是" + list);

        // 创建LinkedList实例
        LinkedList<String> link = new LinkedList<>(list);

        System.out.println("link的内容是" + link);
        link.addFirst("first");
        link.addLast("last");
        System.out.println("link的内容是" + link);
        System.out.println("link的第一个元素内容是： " + link.getFirst());
}

结果：

list数组的内容是[a, b, c, d, e, f, g, h]
link的内容是[a, b, c, d, e, f, g, h]
link的内容是[first, a, b, c, d, e, f, g, h, last]
link的第一个元素内容是： first

3、Vector类

:底层数据结构是数组，查询快，增删慢，线程安全，效率低，可以存储重复元素，不建议使用。

五、Iterator接口（迭代器）

Iterator接口是对Collection进行迭代的迭代器。利用这个接口，可以对Collection中的元素进行访问，实现对集合元素的遍历。
Iterator接口有三个方法：

迭代器一开始指向第一个对象，使用Next()后指向下一个对象。在迭代集合元素过程中，如果使用了出remove()方法之外的方式改变了集合结构，迭代器必须重新获取。且remove()只有在调用Next()方法后才可以使用，每次执行Next()之后最多调用一次。

迭代器测试：

public static void main(String[] args) {
        // 创建ArrayList实例
        ArrayList<Integer> list = new ArrayList<>();
        // 给list添加元素
        for (int i=1; i<9; i++) {
            list.add(i);
        }
        // 返回Iterator迭代器
        Iterator<Integer> it = list.iterator();
        //迭代器遍历集合
        while (it.hasNext()) {  // 判断是否有元素
            int x = it.next();  // 获取元素
            System.out.println(x);
            if (x == 5)  // 元素为5时移除元素
                it.remove();
        }

        // 转换为对象数组
        Object[] a = list.toArray();
        System.out.printf("删除之后的内容是： ");
        for (int i=0; i<a.length; i++) {
            System.out.printf("%s\t",a[i]);
        }
}

结果：

1
2
3
4
5
6
7
8
删除之后的内容是： 1	2	3	4	6	7	8	

六、Set接口及其实现类

无序集合，不允许存放重复的元素；允许使用null元素。对 add()、equals() 和 hashCode() 方法进行更为严格的限制。

（因为HashSet和TreeSet集合底层都是Map，HashSet底层是HashMap，TreeSet底层是TreeMap。所以把Map学会，Set集合就很好理解了，所以这里先简单介绍一下Set接口及其实现类，可以先去学习第七节Map接口。）

1、HashSet类

HashSet底层数据结构采用哈希表实现，元素无序且唯一，线程不安全，效率高，可以存储null元素，元素的唯一性是靠所存储元素类型是否重写hashCode()和equals()方法来保证的，如果没有重写这两个方法，则无法保证元素的唯一性。

具体实现唯一性的比较过程：存储元素首先会使用hash()算法函数生成一个int类型hashCode散列值，然后已经的所存储的元素的hashCode值比较，如果hashCode不相等，则所存储的两个对象一定不相等，此时存储当前的新的hashCode值处的元素对象；如果hashCode相等，存储元素的对象还是不一定相等，此时会调用equals()方法判断两个对象的内容是否相等，如果内容相等，那么就是同一个对象，无需存储；如果比较的内容不相等，那么就是不同的对象，就该存储了，此时就要采用哈希的解决地址冲突算法，在当前hashCode值处类似一个新的链表， 在同一个hashCode值的后面存储存储不同的对象，这样就保证了元素的唯一性。

HashSet类测试：

public static void main(String[] args) {
        Set<String> strs = new HashSet<>();
        strs.add("aa");
        strs.add("bb");
        strs.add("cc");
        strs.add("dd");
        strs.add("aa");
        Iterator<String> it = strs.iterator();
        while (it.hasNext()) {
            String s = it.next();
            System.out.println(s);
        }
    }

结果：

aa
bb
cc
dd

2、TreeSet类

集合底层是TreeMAp，TreeMap底层是二叉树结构。与HashSet类不同，TreeSet类不是散列的，而是有序的。

元素唯一且已经排好序；唯一性同样需要重写hashCode和equals()方法，二叉树结构保证了元素的有序性。根据构造方法不同，分为自然排序（无参构造）和比较器排序（有参构造），自然排序要求元素必须实现Compareable接口，并重写里面的compareTo()方法，元素通过比较返回的int值来判断排序序列，返回0说明两个对象相同，不需要存储；比较器排需要在TreeSet初始化是时候传入一个实现Comparator接口的比较器对象，或者采用匿名内部类的方式new一个Comparator对象，重写里面的compare()方法。

七、Map接口

1、Map集合和Colltection集合没有继承关系。
2、Map集合以Key和Value的键值对方式存储元素。
3、Key和Value都是存储java对象的内存地址。Key起到主导地位，Value是Key的附属品。
4、无序不可重复。

Map中常用方法：

Map常用方法测试：

public static void main(String[] args) {
        // 创建Map集合对象
        Map<Integer,String> map = new HashMap<>();
        // 向集合添加键值对
        map.put(1,"中国");
        map.put(2,"美国");
        map.put(3,"俄罗斯");
        map.put(4,"英国");
        // 通过key获取value
        System.out.println(map.get(1));
        // 判断是否包含某个key
        System.out.println("是否包含key “4”： " + map.containsKey(4));
        // 判断是否包含某个key
        System.out.println("是否包含value “中国”： " + map.containsValue("中国"));
        // map集合是否为空
        System.out.println("集合是否为空： " + map.isEmpty());
        // 通过key删除键值对
        map.remove(2);
        // 集合元素个数
        System.out.println("集合元素个数： " + map.size());
        // 将map集合转换为Set集合
        Set<Map.Entry<Integer,String>> set = map.entrySet();

        System.out.println("======================================================");
        // 遍历集合
        for (Map.Entry<Integer,String>entry : set) {
            System.out.println("key: " + entry.getKey() + "  value: " + entry.getValue());
        }
}

结果：

中国
是否包含key “4”： true
是否包含value “中国”： true
集合是否为空： false
集合元素个数： 3
======================================================
key: 1  value: 中国
key: 3  value: 俄罗斯
key: 4  value: 英国

1、遍历Map集合的四种方法

public static void main(String[] args) {
        Map<String, String> map= new HashMap<>();
        map.put("关羽", "云长");
        map.put("张飞", "益德");
        map.put("赵云", "子龙");
        map.put("马超", "孟起");
        map.put("黄忠", "汉升");

        //第一种遍历map的方法，通过加强for循环map.keySet()，然后通过键key获取到value值
        for(String s:map.keySet()){
            System.out.println("key : "+s+" value : "+map.get(s));
        }
        System.out.println("====================================");

        //第二种只遍历键或者值，通过加强for循环
        for(String s1:map.keySet()){//遍历map的键
            System.out.println("键key ："+s1);
        }
        for(String s2:map.values()){//遍历map的值
            System.out.println("值value ："+s2);
        }
        System.out.println("====================================");

        //第三种方式Map.Entry<String, String>的加强for循环遍历输出键key和值value
        Set<Map.Entry<String,String>> set = map.entrySet();
        for(Map.Entry<String, String> entry : set){
            System.out.println("键 key ："+entry.getKey()+" 值value ："+entry.getValue());
        }
        System.out.println("====================================");

        //第四种Iterator遍历获取，然后获取到Map.Entry<String, String>，再得到getKey()和getValue()
        Iterator<Map.Entry<String, String>> it=map.entrySet().iterator();
        while(it.hasNext()){
            Map.Entry<String, String> entry=it.next();
            System.out.println("键key ："+entry.getKey()+" value ："+entry.getValue());
        }
        System.out.println("====================================");
    }

2、HashMap 哈希表(散列表)数据结构

要掌握HashMap集合，就要熟悉哈希表的数据结构。因为HashMap集合底层是哈希表/散列表的数据结构。

哈希表是一个数组与单向链表的结合体。 所以哈希表在查询和增删数据方面效率都很高。

HashMap底层实际上是一个一维数组，数组里面存的是一个Node（HashMap.Node节点，这个节点里面存储了哈希值，键值对，下一个节点的内存地址）。哈希值是key的hashCode()方法的结果，hash值再通过哈希函数，可以转换为数组的下标。

map.put(k,v)实现原理：
①先将键值对k，v封装到Node对象中；
②底层会调用k的hashCode()方法得出hash值；
③通过哈希函数，将hash值转换为数组的下标。
④进行比较：下标位置如果没有任何元素，就把Node添加到这个位置上；如果下标位置上有链表，此时会拿着k和链表上的每一个节点的k用equals()方法进行比较（因为Map是不可重复的），如果没有重复的新节点就会加到链表末尾，否则则会覆盖有相同k值的节点。

map.get(k)实现原理：
①调用k的hashCode()方法得出hash值；
②进行比较：下标位置如果没有任何元素，返回null，如果下标位置上有链表，此时会拿着k和链表上的每一个节点的k用equals()方法进行比较，如果结果都是false，则返回null；如果有一个节点用了equals方法后结果为true，则返回这个节点的value值。

问：为什么哈希表随机增删、查询效率都高？
答：增删是在链表上完成的，查询也不需要都扫描，只需要部分扫描。

这里重点来了，上述调用了的hashCode()和equals()方法，都需要重写！
equals()重写原因：equals默认比较的是两个对象的内存地址，但我们需要比较的是k中的内容。
hashCode
结论：放在HashMap()集合key部分的元素，，以及放在HashSet集合中的元素，需要同时重写hashCode和equals方法。

重写equals()和hashCode()方法测试：
在重写前和重写后代码运行的结果是不同的，各位可以用这段代码测试一下，把之前的和注释部分取消注释后对比一下。

public class HashMapTest01 {
    public static void main(String[] args) {
        Student s1 = new Student("Jake");
        Student s2 = new Student("Jake");
        System.out.println(s1.equals(s2));
        System.out.println(s1.hashCode() == s2.hashCode());
        Set<Student> students = new HashSet<>();
        students.add(s1);
        students.add(s2);
        System.out.println(students.size());
    }
}

class Student {
    //@Override
    //public boolean equals(Object o) {
    //    if (this == o) return true;
    //    if (o == null || getClass() != o.getClass()) return false;
    //    Student student = (Student) o;
    //    return Objects.equals(name, student.name);
    //}
    //
    //@Override
    //public int hashCode() {
    //    return Objects.hash(name);
    //}

    private String name; 

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

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}

3、TreeMap类

TreeMap类是Map接口的具体实现，底层是二叉树数据结构，支持元素的有序存储，可以按照元素的大小顺序自动排序。TreeMap类中所有元素都必须实现Comparable接口，与TreeSet类相似（TreeSet类底层是TreeMap,放在TreeSet集合中的元素，等同于放在TreeMap集合中的key部分）。

TreeSet类自动排序测试：

public static void main(String[] args) {
        TreeSet<String> ts = new TreeSet<>();
        ts.add("ss");
        ts.add("abf");
        ts.add("g");
        ts.add("f");
        ts.add("abcd");
        ts.add("abc");

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

结果（按照字典顺序升序）：

abc
abcd
abf
f
h
ss

对于自定义的类型，TreeMap是无法自动排序的。需要指定自定义对象之间的比较规则。如果没有指定（谁大谁小没有说明），TreeMap类不知如何给元素排序，就会报错，比如以下这段代码：

public class TreeSetTest02 {
    public static void main(String[] args) {
        Student s1 = new Student("Ana",18);
        Student s2 = new Student("Bob",25);
        Student s3 = new Student("Stark",21);
        Student s4 = new Student("Lip",18);

        TreeSet<Student> students = new TreeSet<>();
        students.add(s1);
        students.add(s2);
        students.add(s3);
        students.add(s4);

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

class Student {
    private String name;
    private int age;

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

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

结果会报以下异常：

 java.lang.ClassCastException: class test.Student cannot be cast to class java.lang.Comparable

这时我们就需要对自定义类型实现Comparable接口，并重写compareTo()方法，需要在这个方法中编写比较的逻辑（比较规则）。
compareTo方法返回的是int值：
返回0表示相同，value会覆盖；
返回>0，会在右子树上找；
返回<0，会在左子树上找。（此处不了解请去学习二叉树数据结构）

比较规则是自己设定的，首先比较年龄的大小，如果年龄一样，则比较字符串的大小。

public class TreeSetTest02 {
    public static void main(String[] args) {
        Student s1 = new Student("Ana",18);
        Student s2 = new Student("Bob",25);
        Student s3 = new Student("Stark",21);
        Student s4 = new Student("Lip",18);

        TreeSet<Student> students = new TreeSet<>();
        students.add(s1);
        students.add(s2);
        students.add(s3);
        students.add(s4);

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

class Student implements Comparable<Student>{
    private String name;
    private int age;

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

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
    // compareTO方法返回的是int值；
    // 比较规则是自己设定的，首先比较年龄的大小，如果年龄一样，则比较字符串的大小；
    public int compareTo(Student o) {
        if (this.age != o.age)
            return this.age - o.age;
        else  //年龄一样
            return this.name.compareTo(o.name);  // 此处调用的不是这个类中的compareTo方法，而是调用了字符串的compareTo方法
    }
}

结果：

Student{name='Ana', age=18}
Student{name='Lip', age=18}
Student{name='Stark', age=21}
Student{name='Bob', age=25}

TreeSet集合中元素可排序的第二种方式：使用比较器方式。 单独写一个比较器，这个比较器实现java.util.Comparator接口。并在创建TreeSet集合时，传入这个比较器。

public class TreeSetTest02 {
    public static void main(String[] args) {
        Student s1 = new Student("Ana",18);
        Student s2 = new Student("Bob",25);
        Student s3 = new Student("Stark",21);
        Student s4 = new Student("Lip",18);

        //创建TreeSet集合时，需要传入这个比较器
        TreeSet<Student> students = new TreeSet<>(new StudentComparator());
        students.add(s1);
        students.add(s2);
        students.add(s3);
        students.add(s4);

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

class Student {
    public String name;
    public int age;

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

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

//单独写一个比较器
//比较器实现java.util.Comparator接口
class StudentComparator implements Comparator<Student> {

    @Override
    public int compare(Student o1, Student o2) {
        if (o1.age != o2.age)
            return o1.age - o2.age;
        else
            return o1.name.compareTo(o2.name);
    }
}

当然也可以使用匿名内部类的方式。

public class TreeSetTest02 {
    public static void main(String[] args) {
        Student s1 = new Student("Ana",18);
        Student s2 = new Student("Bob",25);
        Student s3 = new Student("Stark",21);
        Student s4 = new Student("Lip",18);

        //创建TreeSet集合时，需要传入比较器（使用匿名内部类）
        TreeSet<Student> students = new TreeSet<>(new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {
                if (o1.age != o2.age)
                    return o1.age - o2.age;
                else
                    return o1.name.compareTo(o2.name);
            }
        });
        students.add(s1);
        students.add(s2);
        students.add(s3);
        students.add(s4);

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

class Student {
    public String name;
    public int age;

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

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

结论： 放到TreeSet或者TreeMap集合key部分的元素要想做到排序，包括两种方式:
第一种:放在集合中的元素实现java. lang. Comparable接口。（比较规则固定的时候使用这种）
第二种:在构造TreeSet或者TreeMap集合的时候给它传一个比较器对象。（比较规则经常变化的时候使用这种）