概述

需求1：20个学员。用Student描述，创建Student对象。
既然对象很多先进行存储---数组。

Student[] stus = new Student[20];

需求2：又来来了一个新学员。
原来的容器用不了。数组的长度是固定的。

解决：
创建一个新数组，将原来数组中的元素复制到新数组中。
麻烦。Java中提供解决问题的对象---->集合。

当数据多了需要存储，需要容器，而数据的个数不确定，无法使用数组，这时可以使用Java中另一个容器--集合。

集合和数组的区别？
数组的长度是固定的。
集合的长度是可变的。

数组中存储的是同一类型的元素，可以存储基本数据类型值。
集合存储的都是对象。而且对象的类型可以不一致。

什么时候使用集合呢？
当对象多的时候，先进行存储。

JDK最早的1.0版本中。提供的集合容器很少。
到了1.2版，为了更多的需求，出现了集合框架。有了更多的容器。
完成不同的需求。
这些容器怎么区分？区分的方式：每一个容器的数据结构不一样。
数据存储到的一种方式。

不断的向上抽取过程中，出现体现，形成了集合框架。
最顶层：Collection接口。
学习体系：看顶层，用底层。

了解顶层Collection：
一个容器：添加，删除，获取等功能。

Collection:
        |--List:有序的，带索引的，通过索引就可以精确的操作集合中的元素，元素是可以重复的。
                List提供了增删改查动作   
                增加add(element) add(index,element)  ;
                删除remove(element) remove(index);
                修改set(index,element);
                查询get(index);
            |--Vector：可以增长的数组结构。同步的。效率非常低。已被ArrayList替代。
            |--ArrayList：是数组结构，长度是可变的（原理是创建新数组+复制数组），查询速度很快，增删较慢，不同步的。
            |--LinkedList：是链表结构，不同步的，增删速度很快，查询速度较慢。
                    可用于实现堆栈，队列。
                    堆栈：先进后出  First in Last Out  FILO 手枪弹夹。
                    队列：先进先出  First in First Out FIFO 排队买票。
            List可以存储重复元素的，如果需求中要求容器中的元素必须保证唯一性。
            
        |--Set:不包含重复元素的集合，不保证顺序。而且方法和Collection一致。Set集合取出元素的方式只有一种：迭代器。
            |--HashSet:哈希表结构，不同步，保证元素唯一性的方式依赖于：hashCode(),equals()方法。查询速度快。
            |--TreeSet:可以对Set集合中的元素进行排序。使用的是二叉树结构。如何保证元素唯一性的呢？
                        使用的对象比较方法的结果是否为0，是0，视为相同元素不存。
                        元素的排序比较有两种方式：
                        1，元素自身具备自然排序，其实就是实现了Comparable接口重写了compareTo方法。
                        如果元素自身不具备自然排序，或者具备的自然排序不是所需要的，这时只能用第二种方式。
                        2，比较器排序，其实就是在创建TreeSet集合时，在构造函数中指定具体的比较方式。
                            需要定义一个类实现Comparator接口，重写compare方法。
            到此为止：再往集合中存储对象时，通常该对象都需要覆盖hashCode，equals，
            同时实现Comparale接口，建立对象的自然排序。通常还有一个方法也会复写toString();
            
    看集合对象的小技巧：★★★★★★
    集合分体系。List  Set
    子类对象的后缀名是所属体系，前缀名是数据结构名称。
    List：新出的子类都是以List结尾的，通常都是非同步的。
        |--ArrayList ：看到array，就知道数组，查询速度快。
        |--LinkedList：看到link，就知道链表，增删速度快。
        
    Set:
        |--HashSet:看到hash，就知道哈希表，查询速度更快，并想到元素唯一，通过hashCode(),equals方法保证唯一性。
        |--TreeSet:看到tree，就知道二叉树，可以排序，排序想到Comparable-compareTo Comparator--compare方法。

Collection的基本方法了解

    public static void main(String[] args) {
        
//      Collection coll = new ArrayList();//目前演示Collection的方法，不关系子类对象的类型是什么。
//      collectionDemo(coll);
        
        Collection c1 = new ArrayList();
        Collection c2 = new ArrayList();
        collectionDemo2(c1, c2);

    }
    
//  演示Collection中带all方法 。
    public static void collectionDemo2(Collection c1,Collection c2){
        
        //1,给两个集合添加元素。
        c1.add("abc1");
        c1.add("abc2");
        c1.add("abc3");
        
        c2.add("abc1");
        c2.add("abc4");
        c2.add("abc5");
        
        //添加所有c2的元素到c1中。
//      c1.addAll(c2);
        
//      boolean b = c1.containsAll(c2);
//      System.out.println("b="+b);
        
        //删除c1中所有和c2相同的元素。
//      c1.removeAll(c2);
        
        //保留了c1中和c2相同的元素。
        c1.retainAll(c2);
        
        //打印。
        System.out.println("c1="+c1);
        
    }
    
//  演示Collection中常见的一般方法。
    public static void collectionDemo(Collection coll) {
        
        //1,往集合中添加对象元素。add(Object);
        coll.add("itcast1");
        coll.add("itcast2");
        coll.add("itcast3");
        
        
        //2,删除。
//      coll.remove("itcast2");
        
        //3,判断是否包含。
        System.out.println(coll.contains("itcast11"));
        
        //4,清除。
        coll.clear();
        //把集合打印一下。
        System.out.println(coll);//[itcast1, itcast2, itcast3]
        
    }

Iterator-迭代

集合取元素，无论是什么数据结构，最终共性的取出方式，一个一个取，取之前先判断。有，取一个。没有，结束。这种取出的共性方式：迭代。

    public static void main(String[] args) {
        
        Collection coll = new ArrayList();

        /*//2.获取容器的迭代器对象。通过iterator方法。
        Iterator it = coll.iterator();
        
        //3,使用具体的迭代器对象获取集合中的元素。参阅迭代器的方法
        while(it.hasNext()){
            System.out.println(it.next());
        }*/

//      System.out.println(it.next());//java.util.NoSuchElementException没有这个元素异常。
        
        /*
         * 细节。
         * 1，集合中存储其实都是对象的地址。
         * 2，集合中可以存储基本数值吗？不行，但是jdk1.5以后可以这么写，但是存储的还是对象(基本数据类型包装类对象)。
         * 3，存储时提升了Object。取出时要使用元素的特有内容，必须向下转型。
         */
        
        //coll存储元素。
//      coll.add("abc1");//存储的是对象的引用。
        
//      coll.add(3);//coll.add(Integer.valueOf(3));//自动装箱。
        

        coll.add("itcast1");//Object obj = "itcast1";提升为了Object。
        coll.add("hehe");//
        coll.add("nba");
        
        for (Iterator it = coll.iterator(); it.hasNext();) {
            
            Object object = it.next();//取出来的都是Object。需要使用元素的特有方法时需要向下转型。
            String str = (String)object;
            System.out.println(str.length());
            
        }
    }

往集合中存储自定义的对象。

    public static void main(String[] args) {
        /*
         * 往集合中存储自定义的对象。
         */
        
        //1,创建集合对象。
        Collection coll = new ArrayList();
        
        //2,添加具体的学生元素
        Student stu = new Student("lisi1",21);
        coll.add(stu);
        coll.add(stu);
        coll.add(new Student("lisi2",22));
        coll.add(new Student("lisi3",23));
        coll.add(new Student("lisi3",23));
        
        /*
         * 什么是重复呢?都是有判断依据的。
         * 依据都是通过方法来完成的。
         * 
         */
        for (Iterator it = coll.iterator(); it.hasNext();) {
            Student student = (Student) it.next();
            System.out.println(student.getName());
        }
        
    }

集合中的重复概念

什么是重复呢?都是有判断依据的。
依据都是通过方法来完成的。

public class Student {
    private String name;
    private int age;

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

    /**
     * 建立学生对象判断相同的依据。覆盖equals方法，只要同姓名同年龄就是同一人。视为重复元素。
     * @return
     */
    public String getName() {
        return name;
    }

    @Override
    public boolean equals(Object obj) {
        
        if(this== obj)
            return true;
        
        if(!(obj instanceof Student)){
            throw new ClassCastException("类型错误");
        }
        
        Student stu = (Student)obj;
        
        return this.name.equals(stu.name) && this.age == stu.age;
    }

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

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

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

List接口

    public static void main(String[] args) {
        /*
         * 使用List，解决，插入元素的问题。因为add方法追加。
         * List接口的特有方法，全都是围绕索引来定义的。
         * 
         * List获取元素的方式有两种：一种是迭代，一种 遍历+get
         * 
         * List接口是支持对元素进行curd增删改查动作的。
         * 
         */
        List list = new ArrayList();
        
        //1,添加元素。
        list.add(new Student("wangcai1",21));
        list.add(new Student("wangcai2",22));
        list.add(new Student("wangcai3",23));
        
        //2,插入元素。
//      list.add(1, new Student("xiaoqiang",25));
        
        //3,删除元素。
//      list.remove(2);//IndexOutOfBoundsException
        
        
        //3,修改元素。
        list.set(1, new Student("xiaoming",11));
        
//      Object obj = list.get(1);
//      System.out.println(obj);
        for (int i = 0; i < list.size(); i++) {
            System.out.println("get("+i+"):"+list.get(i));
        }
        
//      for (Iterator it = list.iterator(); it.hasNext();) {
//          Student stu = (Student) it.next();
//          System.out.println(stu);
//      }
    

    }

迭代期间修改List

    public static void main(String[] args) {
        
        
        List list = new ArrayList();
        
        list.add("itcast1");
        list.add("itcast2");
        list.add("itcast3");
        list.add("itcast4");
        
        /*
         *  获取集合中的元素。
         *  如果集合中有元素等于 itcast2.那么就插入一个新的元素，java。
         *  
         *  引发了java.util.ConcurrentModificationException
         *  在迭代过程中，使用了集合的方法对元素进行操作。导致迭代器并不知道集合中的变化，容易引发数据的不确定性。
         *  
         *  解决:在迭代时，不要使用集合的方法操作元素。
         *  那么想要在迭代时对元素操作咋办？可以使用迭代器的方法操作。
         *  可是很遗憾：迭代器的方式只有 hasNext() ,next(),remove();
         *  Iterator有一个子接口ListIterator可以完成该问题的解决。如何获取该子接口对象呢？
         *  通过List接口中的listIterator()就可以获取，
         *  记住：该列表迭代器只有List接口有。而且这个迭代器可以完成在迭代过程中的增删改查动作。
         *  
         *  
         */
//      Iterator it = list.iterator();
//      获取列表迭代其对象
        ListIterator it = list.listIterator();
        
        while(it.hasNext()){
            
            Object obj = it.next();
            if("itcast2".equals(obj)){
//              list.add("java");
//              it.add("java"); // itcast1 itcast2 java itcast3 itcast4
                it.set("java");// itcast1 java itcast3 itcast4
            }
        }
        
        System.out.println(list);

    }

用LinkedList模拟一个队列数据结构

public class LinkedListTest {

    /**
     * @param args
     */
    public static void main(String[] args) {
        /*
         * 面试题：用LinkedList模拟一个堆栈或者队列数据结构。
         * 创建一个堆栈或者队列数据结构对象，该对象中使用LinkedList来完成的。
         * 
         * 自定义堆栈结构。作业。
         */
        //创建一个队列对象。
        Queue queue = new Queue();
        //往队列中添加元素。
        queue.myAdd("itcast1");
        queue.myAdd("itcast2");
        queue.myAdd("itcast3");
        queue.myAdd("itcast4");
        
        while(!queue.isNull()){
            System.out.println(queue.myGet());
        }
    }
}
/**
 * 定义一个队列数据结构。Queue
 */
class Queue{
    //封装了一个链表数据结构。
    private LinkedList link;
    /*
     * 队列初始化时，对链表对象初始化。
     */
    Queue(){
        link = new LinkedList();
    }
    
    /**
     * 队列的添加元素功能。
     */
    public void myAdd(Object obj){
        //内部使用的就是链表的方法。
        link.addFirst(obj);
    }
    
    /**
     * 队列的获取方法。
     */
    public Object myGet(){
        return link.removeLast();
    }
    
    /**
     * 判断队列中元素是否空，没有元素就为true。
     */
    public boolean isNull(){
        return link.isEmpty();
    }
}

哈希存储结构原理图解

哈希存储结构原理图解

HashSet为什么自定义对象没有保证唯一性

    public static void main(String[] args) {
        
        Set set = new HashSet();
        
        /*
//      去除了字符串中的重复元素。
        set.add("nba");
        set.add("java");
        set.add("haha");
        set.add("itcast");
        set.add("haha");
        set.add("java");
        set.add("java");
        set.add("java");
        set.add("itcast");*/
        
        /*
         * 
         * 为什么学生对象没有保证唯一性呢？
         * 通过对哈希表的分析。
         * 存储元素时，先调用了元素对象的hashCode()方法，而每个学生对象都是新建立的对象，
         * 所以hashCode值都不相同，也就不需要判断equals了。
         * 想要按照需求同姓名同年龄来保证学生对象的唯一性咋办？
         * 不能使用Object中hashCode方法，需要重新定义hashCode的算法内容。
         * 简单说：重写hashCode方法。
         */
        set.add(new Student("lisi1",21));
        set.add(new Student("lisi2",22));
        set.add(new Student("lisi1",21));
        set.add(new Student("lisi2",22));
        set.add(new Student("lisi1",21));
        
        "abc1".hashCode();
        
        for (Iterator it = set.iterator(); it.hasNext();) {
            System.out.println(it.next());
        }

    }

HashSet保证自定义对象唯一性

重写自定义对象equals方法和hashCode方法

public class Student implements Comparable {

    private String name;
    private int age;

    public Student() {
        super();
    }

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

    /**
     * 重写hashCode方法，建立Student对象的hash值算法内容。 通过学生对象特有数据姓名和年龄值来算出hash值。
     */
    @Override
    public int hashCode() {

        final int NUMBER = 24;

        return name.hashCode() + age * NUMBER;// 乘以24(随意)为了尽量保证hash值不同
        // return 1;
    }

    /**
     * 重写了equals方法，建立Student对象判断相同的依据。
     */
    @Override
    public boolean equals(Object obj) {

        System.out.println("equals");
        if (this == obj)
            return true;

        if (!(obj instanceof Student)) {
            throw new ClassCastException();
        }

        Student stu = (Student) obj;
        return this.name.equals(stu.name) && this.age == stu.age;
    }

    public String getName() {
        return name;
    }

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

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

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

    /**
     * 重写compareTo方法，建立学生的自然排序(对象的默认排序方式)。
     * 按照学生年龄排序。
     */
    @Override
    public int compareTo(Object o) {
        
        
        if(!(o instanceof Student)){
            throw new ClassCastException();
        }
        Student stu = (Student)o;
        
//      if(this.age>stu.age)
//          return 1;
//      if(this.age<stu.age)
//          return -1;
        
        /*
         * 注意：在比较时，必须明确主次。主要条件相同，继续比较次要条件。
         */
        int temp = this.age - stu.age;
        
        return temp==0?this.name.compareTo(stu.name):temp;
    }

}

TreeSet自然排序存储自定义对象

TreeSet存储自定义对象使用元素的自然顺序对元素进行排序
必须实现Comparable接口。

public class Student implements Comparable {
    private String name;
    private int age;

    public Student() {
        super();
    }

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

    /**
     * 重写hashCode方法，建立Student对象的hash值算法内容。 通过学生对象特有数据姓名和年龄值来算出hash值。
     */
    @Override
    public int hashCode() {

        final int NUMBER = 24;

        return name.hashCode() + age * NUMBER;// 乘以24(随意)为了尽量保证hash值不同
        // return 1;
    }

    /**
     * 重写了equals方法，建立Student对象判断相同的依据。
     */
    @Override
    public boolean equals(Object obj) {

        System.out.println("equals");
        if (this == obj)
            return true;

        if (!(obj instanceof Student)) {
            throw new ClassCastException();
        }

        Student stu = (Student) obj;
        return this.name.equals(stu.name) && this.age == stu.age;
    }

    public String getName() {
        return name;
    }

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

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

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

    /**
     * 重写compareTo方法，建立学生的自然排序(对象的默认排序方式)。
     * 按照学生年龄排序。
     */
    @Override
    public int compareTo(Object o) {
        
        
        if(!(o instanceof Student)){
            throw new ClassCastException();
        }
        Student stu = (Student)o;
        
//      if(this.age>stu.age)
//          return 1;
//      if(this.age<stu.age)
//          return -1;
        
        /*
         * 注意：在比较时，必须明确主次。主要条件相同，继续比较次要条件。
         */
        int temp = this.age - stu.age;
        
        return temp==0?this.name.compareTo(stu.name):temp;
    }

}

    public static void main(String[] args) {
    
        //演示TreeSet,
        Set set = new TreeSet();
        /*
        set.add("nba");
        set.add("abc");
        set.add("java");
        set.add("aaa");
        */
        /*
         * TreeSet的add方法内部最终实现：
         * 需要将元素转成Comparable类型，为什么？因为这个类型具备排序的能力。
         * 这个类型中有一个专门为排序提供了一个compareTo方法。
         * 如果要让学生具备比较排序的功能，需要让学生扩展功能，实现Comparable接口。
         */
        set.add(new Student("lisi6",21));
        set.add(new Student("lisi8",22));
        set.add(new Student("lisi5",25));
        set.add(new Student("lisi3",23));
        set.add(new Student("lisi7",20));
        
        
        
        for (Iterator it = set.iterator(); it.hasNext();) {
            System.out.println(it.next());
        }
    }

TreeSet比较器排序存储自定义对象

其实就是在创建TreeSet集合时，在构造函数中指定具体的比较方式。
需要定义一个类实现Comparator接口，重写compare方法。

public class ComparatorByName implements Comparator {

    @Override
    public int compare(Object o1, Object o2) {
        //1,因为要比较的是学生对象的姓名。所以向下转型成Student对象。
        Student s1 = (Student)o1;
        Student s2 = (Student)o2;
        
        //先比较姓名。
        int temp = s1.getName().compareTo(s2.getName());
        //如果姓名相同，再比较年龄。
        return temp==0? s1.getAge()-s2.getAge():temp;
    }
}
    public static void main(String[] args) {
        //在创建TreeSet集合对象时明确比较器。
        Set set = new TreeSet(new ComparatorByName());
        /*
         * 想要按照学生的姓名排序，说明学生中的自然排序不是所需要的。
         * 这时只能使用比较器。ComparatorByName。
         */
        set.add(new Student("lisi6",21));
        set.add(new Student("lisi8",22));
        set.add(new Student("lisi5",25));
        set.add(new Student("lisi3",23));
        set.add(new Student("lisi7",20));
        
        for (Iterator it = set.iterator(); it.hasNext();) {
            System.out.println(it.next());
        }
    }

TreeSet的二叉树数据结构

如果需要排序就用TreeSet

TreeSet的二叉树数据结构