Java通识基础24——集合类1

Collection综述

集合类的概念——容器类

集合类的对象——容器本身

集合类对象的基本功能——

  • 装对象——add(对象)
  • 取出对象——get
  • 删除对象
  • 容器大小
  • 查看容器是否为空——empty
  • 清空容器——clear()
  • 遍历容器

集合的根接口collection

collection的三个子接口

Set子类

  • 基本等同于collection，但是集合元素不允许重复（不能装两个相同的对象）
  • 集合元素是无序的
    • 实现类HashSet（真正无序）
      • 子类LinkedHashSet
    • 接口SortedSet（字面意思，有序的Set集合）
      • 子类TreeSet

List子类（Set的反例）

  • 集合元素可以重复
  • 元素时有序的，元素都有索引
    • 基于数组的实现类ArrayList
    • 基于链表的实现类LinkedList（既是队列，也是栈）

Queue子类

  • 队列——先入先出（后面将解释）
    • 提供子接口Deque
      • 该接口的实现类ArrayDeque
      • 继承实现类LinkedList（既是队列，也是栈）

三个基础的数据结构

image.png

数据结构介绍

数据结构——栈(Stack)

形象的将栈理解为一个弹夹——后压进去的子弹先被打出来

push（压栈）——将对象压入栈中

pop（弹栈）——让对象从栈中弹出

综上所述，栈遵循先入后出的特征（只有一个出入口）

数据结构——队列（Queue）

可以形象理解为单项轨道，特征是遵循这一个方向

对象先入先出（一个入口一个出口）、

数据结构双端队列（Deque）

既可以作为栈，也可作为队列

有两个口既可以出也可以入

Collection根接口的基本用法和基本方法

  1. import java.util.Collection;
  2. import java.util.HashSet;
  3. import java.util.Iterator;
  5. public class CollectionTest {
  6.     public static void main(String[] args) {
  7.         Collection<String> c=new HashSet<String>();//尖括号内叫泛型，限制该集合只能装指定类型的对象
  8.         Collection<String> c1=new HashSet<>();//菱形语法，功能与上一句相同
  9.         //该语句实现了向上转型，从HashSet向上转型为Collection
  11.         //装对象——add(对象)
  12.         c.add("Date");//上面泛型已经声明只能装String
  13.         c.add("wyd");
  14.         c.add("lsl");
  15.         c.add("ggg");
  16.         System.out.println(c);
  18.         //取出对象——get
  20.         //删除对象
  21.         c.remove("wyd");
  22.         System.out.println(c);
  24.         //容器大小
  25.         System.out.println(c.size());
  27.         //查看容器是否为空——empty
  28.         System.out.println(c.isEmpty());
  30.         //遍历容器(集合)
  31.         for (String g:c){
  32.             System.out.println(g);
  33.         }//用foreach循环进行遍历
  35.         for(Iterator<String> a=c.iterator();a.hasNext();){
  36.             String st=a.next();
  37.             System.out.println(st);
  38.         }//用Iterator遍历器进行遍历
  40.         Iterator<String> b=c.iterator();
  41.         while (b.hasNext()){
  42.             String st=b.next();
  43.             System.out.println(st);
  44.         }//用Iterator遍历器进行遍历
  46.         c.forEach(t-> System.out.println(c));//Lambda表达式遍历
  48.         //判断是否包含某一个对象
  49.         System.out.println(c.contains("wyd"));
  50.         System.out.println(c.contains("lsl"));
  52.         //清空容器——clear()
  53.         c.clear();
  54.         System.out.println(c);
  55.     }
  56. }

Set子接口

HashSet实现类的特征与功能

特征

基本等同于collection，所拥有的方法相同

但增加了两个要求

  • 元素不可重复
  • 元素无序
  • 快速存读数据

最大的特征是速度快——Set最常用的实现类是HashSet

  1. import java.util.*;
  2. public class Set {
  3.     public static void main(String[] args) {
  4.         HashSet<Integer> sets=new HashSet<>();
  5.         sets.add(2);
  6.         sets.add(3);
  7.         sets.add(6);
  8.         sets.add(0);
  9.         sets.add(2);//元素不能重复
  10.         sets.add(122);
  11.         System.out.println(sets);
  12.     }
  13. }
  14. /*
  15.     [0, 2, 3, 6, 122]顺序打乱并且不显示重复元素
  16. */

HashSet判断两个元素是否相等

  • 两个对象通过equals比较是否相等
  • 两个对象的HashCode()返回值是否相等
    该方法是给HashSet、HashMap等需要Hash算法的程序调用的，作为该对象的标识

hashCode方法

重写原则

  • 所有参与equals比较的field都需要参与HashCode计算
  • 计算出每一个HashCode的值。并且将其累加（乘质数，质数个数取决于变量数量）

重写目的——让equals和hashCode方法一致

  1. import java.util.HashSet;
  3. public class SetTest2 {
  4.     public static void main(String[] args) {
  5.         HashSet<Cat> m1=new HashSet<>();
  6.         m1.add(new Cat("black",2.2));
  7.         m1.add(new Cat("black",2.2));
  8.         System.out.println(m1);
  9.     }
  10. }
  11. class Cat {
  12.     private String color;
  13.     private Double weight;
  14.     public Cat(String color,double weight){
  15.         this.color=color;
  16.         this.weight=weight;
  17.     }
  19.     public void setColor(String color) {
  20.         this.color = color;
  21.     }
  23.     public void setWeight(double weight) {
  24.         this.weight = weight;
  25.     }
  27.     public double getWeight() {
  28.         return weight;
  29.     }
  31.     public String getColor() {
  32.         return color;
  33.     }
  35.     @Override
  36.     public String toString(){
  37.         return "Cat"+this.color+" "+this.weight;
  38.     }
  40.     @Override
  41.     public boolean equals(Object obj){
  42.         if(this==obj){
  43.             return true;
  44.         }
  45.         if (obj!=null&&obj.getClass()==Cat.class){
  46.             Cat target=(Cat)obj;
  47.             return this.color.equals(target.color)&&(this.weight-target.weight)<1e-6;
  48.         }
  49.         return false;
  50.     }
  51.     @Override
  52.     public int hashCode(){
  53.         int prime=31;//定义一个质数
  54.         return this.color.hashCode()*prime+this.weight.hashCode();
  55.         //计算出每一个Field的hashCode值并乘质数
  56.         //这里有两个变量，第一个乘一个质数（一般31）
  57.     }
  58. }
  59. /*
  60. [Catblack 2.2]此时就保留了一个元素
  61. */

Java系统提供的类只要重写了equals方法，一般也要重写hashCode方法

HashSet的底层实现机制详解

  • HashSet的底层是基于Hash表（本质是数组）实现的
  • HashSet的方法是基于HashMap实现的

数组，在所有的数据结构中是最迅捷的——

数组变量保存了数组对象的首地址，这样查找很迅速

数组的第i个元素的地址=首地址+i*元素大小注意，此处的i从0开始，避免从1开始有减法参与运算（在计算机中，加法运算永远都比减法运算块），当程序需要取第i个元素的时候，直接根据上式计算出来的地址取值

  • HashSet存元素的步骤：
    1. HashSet会先调用该元素的HashCode()，该方法返回一个int值
    2. HashSet会根据元素的HashCode()方法的返回值计算该元素应该保存在HashSet底层数组的什么位置
      具体而言就是拿此元素的HashCode方法的返回值对于数组长度取余
      比如HashCode值为100，数组长度为8，其余即为4。这个元素将被放在底层数组的第5位
    3. HashSet会到底层数组的该位置去检查该位置是否有已有元素
      • 如果这个位置没有元素，就把新元素存到数组的该位置
      • 如果这个位置有元素，就会形成链（旧元素会被新元素从原有的位置挤出去，新元素会给旧元素抛出橄榄枝手牵手形成链条的逻辑模型）
  • HashSet取元素的步骤：
    1. HashSet会先调用该元素的HashCode()，该方法返回一个int值
    2. HashSet会根据元素的HashCode()方法的返回值计算该元素应该保存在HashSet底层数组的什么位置
    3. HashSet会到底层数组的该位置去检查该位置是否有需要的元素
      • 如果这个位置确实保存着我们需要找的元素，直接取出该元素即可
      • 如果该位置的元素不是我们需要找的元素，需要遍历该位置形成的链逐个去找

链越长，查找的性能越差，而底层数组越大，形成链的概率越小

HashSet的两个性能选项

HashSet(int initialCapacity, float loadFactor)

  • initialCapacity——初始大小，也就是底层数组的大小，其默认值是16
  • loadFactor——负载因子——当元素个数除以数组长度大于等于负载因子的时候，此时HashSet会将数组长度扩大一倍。比如负载因子是0.5，数组用了一半的时候就会扩展。所以当负载因子越大，数组的利用率越高，形成链的概率越大。反之，数组的利用率越低，形成链的概率越小
    默认的负载因子大小为0.75

List接口和ArrayList实现类

特征

  • 元素可以重复
  • 元素有序，按照添加顺序排列，第一个元素的元素索引为0，第二个元素的元素索引为1…..

由于List的集合元素是有索引（下标）的，因此程序可以根据下标来就行添加。获取，删除

形象的看，List相当于一个竹子容器，每一节只能装一个对象

Set集合支持的方法，List集合也完全支持

  1. import java.util.ArrayList;
  2. import java.util.List;
  4. public class ListTest {
  5.     public static void main(String[] args) {
  6.         List<String> a=new ArrayList<>();
  7.         a.add("233");
  8.         a.add("wyd");
  9.         a.add("wyd");
  10.         System.out.println(a);
  11.         //根据索引来添加
  12.         a.add(1,"gtn");
  13.         a.add(1,"lsl");
  14.         //根据索引替换
  15.         a.set(3,"wt");
  16.         System.out.println(a);
  17.         //根据索引获取
  18.         System.out.println(a.get(3));
  19.         //根据索引删除
  20.         a.remove(4);
  21.         System.out.println(a);
  22.         //获取元素位置
  23.         System.out.println(a.indexOf("gtn"));
  24.         System.out.println(a.indexOf("kkk"));//不存在将返回-1
  25.         //取出子集
  26.         List<String> b=a.subList(1,3);//前包后不包
  27.         System.out.println(b);
  28.     }
  29. }
  30. /*
  31. [233, wyd, wyd]
  32. [233, lsl, gtn, wt, wyd]
  33. wt
  34. [233, lsl, gtn, wt]
  35. 2
  36. -1
  37. [lsl, gtn]
  39. */

可以通过下标来遍历集合，原有的三种遍历方式也是可行的

  1.    for (int i=0;i<a.size();i++){
  2.             System.out.println(a.get(i));
  3.         }

List集合类同样可以在初始化的时候指定底层数组的长度，默认长度为10

Deque接口

代表双端队列——既是栈也是队列

ArrayDeque基于数组实现，性能较好（块！已经代替了stack）

使用场景

栈——

  • push(元素)
  • pop()
  • peek()获取最顶端的元素但并不弹出
  1. import java.util.ArrayDeque;
  2. import java.util.Deque;
  4. public class ArrayDequeTest {
  5.     public static void main(String[] args) {
  6.         Deque<String> stack=new ArrayDeque<>();
  7.         stack.push("wyd");
  8.         stack.push("sff");
  9.         stack.push("zsj");
  10.         //压入元素
  11.         System.out.println(stack);
  12.         System.out.println(stack.pop());
  13.         //先压的在下面，先弹最后压进去的“子弹”
  14.         System.out.println(stack.peek());
  15.         //显示最上面的元素
  16.     }
  17. }
  18. /*
  19. [zsj, sff, wyd]
  20. zsj
  21. sff
  22. */

队列——

  • offer(元素)：入队
  • poll()：出队
  • peek()：回去队头元素，但不出队
  1. import java.util.ArrayDeque;
  2. import java.util.Deque;
  4. public class ArrayDequeTest {
  5.     public static void main(String[] args) {
  6.         Deque<String> stack=new ArrayDeque<>();
  7.         stack.offer("wyd");
  8.         stack.offer("sff");
  9.         stack.offer("zsj");
  10.         //压入元素
  11.         System.out.println(stack);
  12.         System.out.println(stack.poll());
  13.         //先压的在下面，先弹最后压进去的“子弹”
  14.         System.out.println(stack.peek());
  15.         //显示最上面的元素
  16.     }
  17. }
  18. /*
  19. [wyd, sff, zsj]
  20. wyd
  21. sff
  22. */

List有的方法Deque同样也有

回顾

根接口——collection

Set子接口——元素内容不可以重复；元素无序

List子接口——元素内容可以重复；元素有序

  • ArrayList实现类：基于数组实现——性能好
  • LinkedList实现类：功能强大性能差

Queue子接口：队列；特征——FIFO先入先出

Set子接口的子接口——SortedSet

  • 实现类HashSet——基于hash表，快速存取
    • LinkedHashSet子类——额外维护一条链的记住元素的添加顺序

Queue子接口的子接口——Deque，双端队列——既是栈，也是队列

Interator接口——遍历器