复习

1.Collection根接口
    增: boolean add(E e)
    删: boolean remove(Object obj)
    改: 无
    查: 无
    其他: clear isEmpty size contains toArray
2.迭代器: 遍历集合(与索引无关)
    Iterator<集合的泛型> it = 集合对象.iterator();
    while(it.hasNext()){
        集合的泛型 变量名 = it.next();   
    }
    增强for循环,就是迭代器的语法糖(简便格式)
    for(数据类型 变量名 : 集合/数组){
        System.out.println(变量名);
    }
    =========================
    注意:使用迭代器的过程中,你不能直接通过代码对集合的元素进行增删操作.
    如果你想增删元素,a.使用普通的fori循环 b.使用迭代器提供remove方法    
    
3.泛型(理解)
     给一个泛型类,比如ArrayList<E>,怎么使用??
        ArrayList<String> arr = new ArrayList<String>();
        ArrayList<Integer> arr = new ArrayList<Integer>();
4.4+1种数据结构
    栈结构: 先进后出
    队列结构: 先进先出
    数组结构: 查询快,增删慢
    链表结构: 查询慢,增删快
    红黑树结构: 查询速度非常恐怖    

今日内容

• List接口
  List接口的实现类(ArrayList,LinkedList,Vector)
• Set接口
  Set接口的实现类(HashSet,LinkedHashSet,TreeSet)
• Collections 专门操作集合的工具类
  打乱顺序,排序(默认),自定义排序

List接口[重点]

List接口特点

• 继承了Collection接口
• List接口的特点:
  1.有序的(Java中的有序的是指存取顺序保持一致,如存入2,1,3 取出也是2,1,3)
  2.有索引的
  3.元素可重复的

List接口中常用方法

• 继承Collection接口, 所以有Collection中的8个(7个常见,1个获取迭代器)
• List接口自己的特有方法(跟索引相关)
  增: add(int index, E e)
  删:remove(int index)
  改:set(int index, E 新元素);
  查:get(int index)
• List接口的实现类
  1.ArrayList集合 [重点]
  2.LinkedList集合[重点]
  3.Vector[了解]

ArrayList的数据结构以及使用

特点: 查询快,增删慢!!

• ArrayList集合的方法(7个Collection中的+1个迭代器+4个List中的)
• 数据结构:ArrayList集合底层采用的是数组结构.因此查询快,增删慢

LinkedList集合的数据结构以及使用

特点:查询慢,增删快

• LinkedList的方法(7个Collection中的+1个迭代器+4个List接口中的) 特有方法有8个:

public void addFirst(E e) :将指定元素插入此列表的开头。
public void addLast(E e) :将指定元素添加到此列表的结尾。
public E getFirst() :返回此列表的第一个元素。
public E getLast() :返回此列表的最后一个元素。
public E removeFirst() :移除并返回此列表的第一个元素。
public E removeLast() :移除并返回此列表的最后一个元素。
public E pop() :将指定元素添加到此列表的结尾。从此列表所表示的堆栈处弹出一个元素。底层为removeFirst()和此方法一样
public void push(E e) :将指定元素插入此列表的开头。将元素推入此列表所表示的堆栈。底层为addFirst() 和此方法一样
public boolean isEmpty() ：如果列表不包含元素，则返回true。

• LinkedList集合数据存储的结构是链表结构方便元素添加、删除的集合。

• LinkedList的使用

LinkedList的源码分析(了解)

• LinkedList的底层采用链表结构(双向链表)
• LinkedList这个类有两个成员变量
  Node<E> first; 记录了开始节点
  Node<E> last; 记录了结束节点
• 节点类Node,是这样的
  它是LinkedList的内部类
  private static class Node<E>{
  E item; 该节点的数据域
  Node<E> prev; 指针域,指向上一个节点
  Node<E> next; 指针域,指向下一个节点
  }
• LinkedList的add方法
  a.将新增的节点,添加到last节点之后
  b.并且将size++,总的元素个数增加1
• LinkedList的get方法
  a.先查找指定索引的那个节点(从前往后找,从后往前找)
  b.找到节点之后,获取节点的数据域,然后返回

Collections类(重点)

Collections的介绍

是一个集合的工具类,该类中的很多静态方法用来操作集合

Collections的常用功能

- public static void shuffle(List<?> list) :打乱集合顺序。
- public static <T> void sort(List<T> list,Comparator<T> com); 带有比较器的排序方法
如果集合泛型是数值类型, 按照数值大小升序(比较器详细讲解在下边)
如果集合泛型是Chararcter类型,那按照字符的码值升序
如果集合泛型是String类型,那么按照首字母升序,如果首字母一样,按照次字母排序,以此类推
- public static <T> void sort(List<T> list，Comparator<? super T> ) :将集合中元素按照指定规则排序。

注意:
sort、max、min三个方法都需要指定排序的规则。即：如果集合中存的是自定义对象，那么该对象必须要实现Comparable接口或者给这三个方法传递一个Comparator的实现类作为比较器.

使用Collections类的sort方法

使用带有比较器的sort方法:

//使用比较器降序排序
public class TestCollections02 {
    public static void main(String[] args) {
        //1.创建一个集合
        ArrayList<Integer> arr = new ArrayList<Integer>();
        //2.添加点元素
        arr.add(2);
        arr.add(8);
        arr.add(3);
        arr.add(9);
        arr.add(4);
        arr.add(1);
        arr.add(6);
        arr.add(7);
        arr.add(5);
        System.out.println(arr);
        //3.使用带有比较器的sort方法
        Collections.sort(arr, new Comparator<Integer>() {
            /**
             * 该方法就是比较方法
             * @param o1 第一元素
             * @param o2 第二元素
             * @return 返回值代表谁大谁小,如果是正数代表o1大,如果适合负数代表o2大,如果是0代表一样大
             *
             * 口诀:
             *  升序 前-后
             */
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        System.out.println(arr);
    }
}
    
//使用比较器排序自定义类型
public class TestCollections03 {
    public static void main(String[] args) {
        //1.创建一个集合
        ArrayList<Dog> arr = new ArrayList<Dog>();
        //2.加狗
        arr.add(new Dog(1,"jack",4));
        arr.add(new Dog(4,"lilei",3));
        arr.add(new Dog(2,"ady",2));
        arr.add(new Dog(3,"hanmmeimei",5));
        //3.对狗集合继续排序
        Collections.sort(arr, new Comparator<Dog>() {
            @Override
            public int compare(Dog o1, Dog o2) {
                //升序 前-后
                //按照狗的年龄降序
//                return o2.age-o1.age;
                //按照狗的名字的长度升序
//                return o1.name.length()-o2.name.length();
                //按照狗的年龄和腿数的总和,升序
                return (o1.age+o1.legs)-(o2.age+o2.legs);

            }
        });
        //4.打印
        for (Dog dog : arr) {
            System.out.println(dog);
        }
    }
}

排序

自然排序和比较器排序

• 整数类型(int,short,byte,long) 可以用减法,
• 引用类型 使用 对象名.compareTo(对象名)方法

自然排序(只能实现一种排序规则)

根据数字的大小

Comparable接口

在定义类中实现Comparable接口,并且重写该接口内的比较规则的方法 然后在测试类中可以配合 Conllections.sort().使用,打印出来的集合就是按照了自定义的比较规则而打印
也可以配合TreeSet集合使用

自然排序缺点:

只能实现一种比较规则. 所以比较规则多的话使用比较器排序

图解代码

比较器排序

比较规则写在类的内部,每个比较器都可以实现一个自定义比较规则,想要用多种规则,就用多个比较器实现,一般使用匿名内部类填写规则.

Comparator接口(比较器)

Collections中有两个sort重载方法, 一个根据从小到大排序, 一个根据规则排序
public static <T> void sort(List<T> list，Comparator<? super T> ) :将集合中元素按照指定规则排序。参数列表中, 一个为集合, 一个为接口实现类对象.接口参数需要传入接口的实现类对象或者使用匿名内部类实现.
此匿名内部类中的返回值口诀为: 升序前-后

public static void main(String[] args) {
        // 创建四个学生对象 存储到集合中
        ArrayList<Student> list = new ArrayList<Student>();
 
        list.add(new Student("rose",18));
        list.add(new Student("jack",16));
        list.add(new Student("abc",20));
        Collections.sort(list, new Comparator<Student>() {
          @Override
            public int compare(Student o1, Student o2) {
            这里的返回值,升序 前-后
            return o1.getAge()-o2.getAge();//以学生的年龄升序
      或者使用 return o1.name.compareTo(o2.name) 字符串已经实现好了 compareTo方法
         }
        });
 
 
        for (Student student : list) {
            System.out.println(student);
        }
    }

可变参数

• 使用
  在JDK1.5之后，如果我们定义一个方法需要接受多个参数，并且多个参数类型一致，我们可以对其简化.
  格式：

修饰符 返回值类型 方法名(参数类型... 形参名){ }

注意：
1.一个方法只能有一个可变参数
2.如果方法中有多个参数，可变参数要放到最后。

• 应用场景
  Collections
  在Collections中也提供了添加一些元素方法：
  public static <T> boolean addAll(Collection<T> c, T... elements) :往集合中添加一些元素。

public class CollectionsDemo {
    public static void main(String[] args) {
      ArrayList<Integer> list = new ArrayList<Integer>();
      //原来写法
      //list.add(12);
      //list.add(14);
      //list.add(15);
      //list.add(1000);
      //采用工具类 完成 往集合中添加元素  
      Collections.addAll(list, 5, 222, 1，2);
      System.out.println(list);
}

Set接口[重点]

Set接口的特点

• 继承Collection接口
• 特点:
  1.无序.(实现类LinkedHashSet除外)(Java中无序指,存入2,1,3. 打印出来可能是1,2,3等)
  2.无索引
  3.元素不可重复
  注意: 除了Set接口的实现类LinkedHashSet是有序的

Set接口的常用方法以及常用子类

• Set接口中的方法(7个Collection继承的常见方法,1个迭代器)
• Set接口没有特有方法
• Set接口的实现类
  1.HashSet
  2.LinkedHashSet
  3.TreeSet

HashSet的数据结构以及使用

• HashSet没有特有方法
• HashSet底层采用的是哈希表结构(数组结构+链表结构+红黑树结构)无序,无索引,元素唯一
• HashSet的使用

public class TestHashSet {
    public static void main(String[] args) {
        //1.创建一个HashSet对象
        HashSet<String> set = new HashSet<String>();
        //2.添加,没有带索引的方法,证明无索引
        set.add("php");
        set.add("java");
        set.add("python");
        set.add("c++");
        set.add("c#");
        //3.直接的打印,证明无序
        System.out.println(set);//[c#, python, c++, java, php]
        //4.再加一个一样元素,证明唯一
        set.add("php");
        set.add("php");
        set.add("php");
        set.add("php");
        set.add("php");
        set.add("php");
        System.out.println(set);
    }
}    

哈希表结构的介绍

• Java中的每个对象的哈希值(对象的"数字指纹")
  1.对象的哈希值,相当于对象的"指纹"(哈希值是十进制, 对象的地址值是十六进制 , 换算之后值一样)
  2.获取对象的哈希值
  调用对象.hashCode方法就可以获取 返回值为int

public class TestHashDemo01 {
    public static void main(String[] args) {
        //1.获取一个对象的哈希码值
        Student s1 = new Student(10,"前妻");
        int hashCode = s1.hashCode();
        System.out.println(hashCode);//1163157884
    }
}  
   

3.Java中的地址值真实面目是哈希值的十六进制表示
4.Java中的地址值存在,但是看不见
Dog d = new Dog(); 变量d中存储的是Dog()对象的真正地址值. 打印d 是Object类中的toString方法此方法是打印出哈希值. 因此隐藏了对象的地址值.
5.不同的两个对象,可能会有哈希值相同的情况, 因为获取的哈希值方法返回值为int类型, 对象可以有无数个, 哈希值只有int范围个.(特别是String类会有可能出现地址值相同如 "abc"和"acD")

• 哈希表结构特点(无序,无索引,无重复)
  1.哈希表结构会先比较两个对象的哈希值,再调用equals比较两个对象.只有哈希值相同,并且equals返回值为true.才判定这两个元素为重复的,后进来的元素不再进行添加操作(具体底层操作如下图)
  2.哈希表结构 = 数组结构 + 链表结构 +红黑树结构

  
  

• 哈希值(上图解释)
  因为哈希表结构底层使用了数组结构, 所以哈希值决定了元素放入数组的哪个位置
  HashSet中使用了HashMap

如 键:a,hash:97 计算方法为: hash%数组长度=需要放置的数组下标 97%16 = 6 所以将元素a放在数组下标为6的位置. 如果哈希值一样, 计算出来的下标一样的话, 就用链表形式,当多于8个链表的时候,采用了红黑树结构

哈希表结构保存自定义类型[重要]

因为哈希表判断两个元素重复与否, 先判断的是哈希值,再使用equals方法判断.
所以为了保证元素的唯一性, 如果元素是自定义类型, 必须重写hashCode和equals方法 (alt+insert)快捷键

/**
 * 使用哈希表保存自定义类型的练习
 */
public class TestHashSetDemo {
    public static void main(String[] args) {
        //1.创建一个哈希表结构的集合
        HashSet<Dog> dogHashSet = new HashSet<Dog>();
        //2.保存对象
        dogHashSet.add(new Dog(10,"旺小财",3));
        dogHashSet.add(new Dog(20,"旺中财",4));
        dogHashSet.add(new Dog(30,"旺大财",5));
        dogHashSet.add(new Dog(40,"旺老财",6));

        //再添加一只狗
        dogHashSet.add(new Dog(30,"旺大财",5));
        //哈希表判断两个元素重复or不重复的依据是什么??
        //  哈希表和equals
        //为了保证元素的唯一性,我们要重写hashCode和equals,根据内容来计算哈希值,equals也改成比较内容
        //3.打印
        for (Dog dog : dogHashSet) {
            System.out.println(dog);
        }
    }
}

public class Dog {
    int age;
    String name;
    int legs;
    public Dog() {
    }
    public Dog(int age, String name, int legs) {
        this.age = age;
        this.name = name;
        this.legs = legs;
    }
    @Override
    public String toString() {
        return "Dog{" +
                "age=" + age +
                ", name='" + name + '\'' +
                ", legs=" + legs +
                '}';
    }
    //为了保证哈希表中元素的唯一性,我们需要重写hashCode和equals方法
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Dog dog = (Dog) o;
        return age == dog.age &&
                legs == dog.legs &&
                Objects.equals(name, dog.name);
    }
    @Override
    public int hashCode() {
        return Objects.hash(age, name, legs);
    }
}

HashSet源码分析

• 构造方法

HashSet<String> set = new HashSet<String>();
    public HashSet() {
        map = new HashMap<>(); 
    }

HashSet底层实际是依赖一个HashMap

• HashSet的add方法

public boolean add(E e) { 
        return map.put(e, PRESENT)==null;
    }     

实际上是调用HashMap的put方法

• HashMap的put方法
  HashMap保存键时,是根据键的哈希值确定保存位置.

LinkedHashSet的数据结构以及使用

• LinkedHashSet特点:有序,无索引,元素不重复
• LinkedHashSet无特有方法
• LinkedHashSet底层采用链表+哈希表结构
• LinkedHashSet的使用)

TreeSet的数据结构以及使用

• TreeSet的特点
  1.无序的但是有自然顺序(存取顺序不一样, 但是无序中一种特殊存在,有自然顺序, 打印出的值是按自然数值从小到大打印出来, 如 输入 321, 打印出来为123)
  2.无索引的
  3.元素唯一
  按照元素大小进行排序,要求元素实现Comparable接口(自然排序)或者加比较器
• TreeSet特有方法: 没有
• TreeSet底层采用红黑树结构
• TreeSet的使用

public static void main(String[] args) {
    //无参构造,默认使用元素的自然顺序进行排序
    TreeSet<Integer> set = new TreeSet<Integer>();
    set.add(20);
    set.add(18);
    set.add(23);
    set.add(22);
    set.add(17);
    set.add(24);
    set.add(19);
    System.out.println(set);
}
 
控制台的输出结果为:
[17, 18, 19, 20, 22, 23, 24]

• TreeSet也可以使用比较器自定义排序规则
  因为TreeSet的构造方法有两个

public TreeSet()：                               根据其元素的自然排序进行排序
public TreeSet(Comparator<E> comparator):    根据指定的比较器进行排序