【java 13天进阶Day05】数据结构,List,Set ,TreeSet集合,Collections工具类

常见的数据结构种类

1. 集合是基于数据结构做出来的，不同的集合底层会采用不同的数据结构。
2. 不同的数据结构，功能和作用是不一样的。
3. 数据结构：
   • 数据结构指的是数据以什么方式组织在一起。
   • 不同的数据结构，增删查的性能是不一样的。
   • 不同的集合底层会采用不同的数据结构，我们要知道集合的底层是基于哪种数据结构存储和操作数据的。这样才能知道具体场景用哪种集合。
4. Java常见的数据结构即数据存储的常用结构：栈、队列、数组、链表和红黑树。
5. a.队列（queue）
   • –先进先出，后进后出。
   • –场景：各种排队。叫号系统。
   • –有很多集合可以实现队列。
6. b.栈（stack）
   • –后进先出，先进后出
   • – 压栈==入栈
   • – 弹栈 == 出栈
   • –场景：手枪的弹夹。
7. c.数组
   • –数组是内存中的连续存储区域。
   • –分成若干等分的小区域（每个区域大小是一样的）
   • –元素存在索引
   • –特点：查询元素快（根据索引快速计算出元素的地址，然后立即去定位）
   • 增删元素慢（创建新数组，迁移元素）
8. d.链表
   • –元素不是内存中的连续区域存储。
   • –元素是游离存储的。每个元素会记录下个元素的地址。
   • –特点：查询元素慢。
   • 增删元素快（针对于首尾元素，速度极快，一般是双链表）。
9. e.红黑树（待看）
   1.
   2. 二叉树：binary tree永远只有一个根节点**,是每个结点不超过2个节点的树（tree） 。
   3. 查找二叉树,排序二叉树：小的左边，大的右边，但是可能树很高，性能变差。
   4. 为了做排序和搜索会进行左旋和右旋实现平衡查找二叉树，让树的高度差不大于1**。
   5. 红黑树（就是基于红黑规则实现了自平衡的排序二叉树）：树尽量的保证到了很矮小，但是又排好序了，性能最高的树。
   6. 红黑树的增删查改性能都好。

---

ArrayList集合

• List集合继承了Collection集合的全部功能，因为List集合多了索引，所以多了很多按照索引操作元素的功能。
• ArrayList实现List集合底层基于数组存储数据的，查询快，增删慢！
• public void add(int index, E element):将指定的元素，添加到该集合中的指定位置上。
• public E get(int index):返回集合中指定位置的元素。
• public E remove(int index):移除列表中指定位置的元素,返回的是被移除的元素。
• public E set(int index, E element):用指定元素替换集合中指定位置的元素，返回更新前的元素值。
• 四种遍历：多了for遍历，因为有索引。
• 使用多态List<String> lists = new ArrayList<>();

---

LinkedList集合

• LinkedList也是List的实现类：底层是基于链表的，增删比较快，查询慢！！
• LinkedList是支持双链表，定位前后的元素是非常快的，增删首尾的元素也是最快的。
• 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():从此列表所表示的堆栈处弹出一个元素。
• public void push(E e):将元素推入此列表所表示的堆栈。
• 放弃多态，使用多态无法调用子类新功能LinkedList<String> linkList = new LinkedList<>();

---

Set系列集合

• Set系列集合是基于哈希表存储数据的，它的增删改查的性能都很好。
• 只有HashSet同父类Set一致都是无序，不重复，无索引的。
• 使用多态Set<String> sets = new HashSet<>();
• 两个问题：
  • Set集合添加的元素是不重复的，是如何去重复的？
    • 对于有值特性的，Set集合可以直接判断进行去重复。
    • 对于引用数据类型的类对象，Set集合是按照如下流程进行是否重复的判断。
      1. Set集合会让两两对象，先调用自己的hashCode()方法得到彼此的哈希值（所谓的内存地址）a1.hashCode());
      2. 然后比较两个对象的哈希值是否相同，如果不相同则直接认为两个对象不重复。
      3. 如果哈希值相同，会继续让两个对象进行equals比较内容是否相同，如果相同认为真的重复了
         如果不相同认为不重复。
      4. 如果希望Set集合认为两个对象只要内容一样就重复了，必须重写对象的hashCode和equals方法。这会使得相同内容的对象哈希值一致且equals比较内容相同。（直接生产即可）
  • Set集合元素无序的原因是什么？
    • 根本原因是因为底层采用了哈希表存储元素。63%6=3
    • JDK 1.8之前：哈希表 = 数组 + 链表 + （哈希算法）
    • JDK 1.8之后：哈希表 = 数组 + 链表 + 红黑树 + （哈希算法）
    • 当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。

---

LinkedHashSet

• 是HashSet的子类，元素是**“有序”** 不重复，无索引。
• LinkedHashSet底层依然是使用哈希表存储元素的，但是每个元素都额外带一个链来维护添加顺序！！不光增删查快，还有序。
• 缺点是多了一个存储顺序的链会占内存空间!!而且不允许重复，无索引。
• 总结：
  • 如果希望元素可以重复，又有索引，查询要快用ArrayList集合。（用的最多）
  • 如果希望元素可以重复，又有索引，增删要快要用LinkedList集合。（适合查询元素比较少的情况，经常要首尾操作元素的情况）
  • 如果希望增删改查都很快，但是元素不重复以及无序无索引，那么用HashSet集合。
  • 如果希望增删改查都很快且有序，但是元素不重复以及无索引，那么用LinkedHashSet集合。

---

TreeSet集合

• 不重复，无索引，按照大小默认升序排序!!
• TreeSet集合称为排序不重复集合，可以对元素进行默认的升序排序。
• 使用多态，在Set基础上基本无新增功能 Set<Double> scores = new TreeSet<>();
• TreeSet集合自自排序的方式：
  • 1.有值特性的元素直接可以升序排序。（浮点型，整型）
  • 2.字符串类型的元素会按照首字符的编号排序。
  • 3.对于自定义的引用数据类型，TreeSet默认无法排序，执行的时候直接报错，因为人家不知道排序规则。
• 自定义的引用数据类型的排序实现：定制排序的大小规则

  • a.直接为对象的类实现比较器规则接口Comparable，重写比较方法（拓展方式）。

    • 如果程序员认为比较者大于被比较者 返回正数。
    • 如果程序员认为比较者小于被比较者 返回负数。
    • 如果程序员认为比较者等于被比较者 返回0。

    • @Data
      public class Employee implements Comparable<Employee> {private String name;private double salary;private int age;// 重写了比较方法。// e1.compareTo(o)// 比较者：this// 被比较者：o// 需求：按照年龄比较@Overridepublic int compareTo(Employee o) {// 规则：Java规则// 如果程序员认为比较者大于被比较者 返回正数！// 如果程序员认为比较者小于被比较者 返回负数！// 如果程序员认为比较者等于被比较者 返回0！
      //        if(this.age > o.age){
      //            return 1;
      //        }else if(this.age < o.age){
      //            return -1;
      //        }
      //        return 0;return this.age - o.age;}} 
      

  • b.直接为集合设置比较器Comparator对象,重写比较方法。

    • 如果程序员认为比较者大于被比较者 返回正数。
    • 如果程序员认为比较者小于被比较者 返回负数。
    • 如果程序员认为比较者等于被比较者 返回0。
    • 使用匿名内部类 public TreeSet(Comparator<? super E> comparator)

    • Set<Employee> employees1 = new TreeSet<>(new Comparator<Employee>() {@Overridepublic int compare(Employee o1, Employee o2) {// o1比较者   o2被比较者// 如果程序员认为比较者大于被比较者 返回正数！// 如果程序员认为比较者小于被比较者 返回负数！// 如果程序员认为比较者等于被比较者 返回0！return o1.getAge() - o2.getAge();}});
      

• 注意：如果类和集合都带有比较规则，优先使用集合自带的比较规则。

–

Collections工具类的使用

• java.utils.Collections:是集合工具类
• Collections并不属于集合，是用来操作集合的工具类。
• Collections有几个常用的API:
  • -public static boolean addAll(Collection<? super T> c, T… elements)：给集合对象批量添加元素！
    • List<String> names = new ArrayList<>();
    • Collections.addAll(names, "曹操", "小亮", "小王");
  • - public static void shuffle(List<?> list) ：打乱集合顺序，只能打乱有序的List集合。
  • - public static void sort(List list)：将集合中元素按照默认规则排序，默认升序。
  • - public static void sort(List list，Comparator<? super T> )：将集合中元素按照指定规则排序。
• Set是哈希算法存储的，无法为其排序和升序。
• 引用数据类型的排序
  • 字符串按照首字符的编号升序排序！
  • 自定义类型的比较方法API
    • - public static void sort(List list):
      • 将集合中元素按照默认规则排序。对于自定义的引用类型的排序人家根本不知道怎么排，直接报错！
      • 如果希望自定义的引用类型排序不报错，可以给类提供比较规则:Comparable。
    • - public static void sort(List list，Comparator<? super T>
      • 将集合中元素按照指定规则排序,自带比较器

      • //方式1 自定义比较器
        Collections.sort(oranges1, new Comparator<Orange>() {@Overridepublic int compare(Orange o1, Orange o2) {if (o1.getWeight() > o2.getWeight()) return -1;if (o1.getWeight() < o2.getWeight()) return 1;return 0;}});
        

      • //方式2 类实现Comparable接口
        @Data
        public class Orange implements Comparable {private String name;private double weight;private String price;@Overridepublic int compareTo(Object o) {Orange o2 = (Orange) o;if (this.weight > o2.weight) return 1;if (this.weight < o2.weight) return -1;return 0;}
        }
        

      • 注意：如果类有比较规则，而sort有比较器，优先使用比较器。

---

可变参数

• 可变参数用在形参中可以接收多个数据。
• 可变参数的格式：数据类型… 参数名称 public static void sum(int... nums)
• 可变参数的作用：
  • 传输参数非常灵活，方便。
  • 可以不传输参数。
  • 可以传输一个参数。
  • 可以传输多个参数。
  • 可以传输一个数组。
  • 可变参数在方法内部本质上就是一个数组。
• 可变参数的注意事项：
  • 1.一个形参列表中可变参数只能有一个。
  • 2.可变参数必须放在形参列表的最后面。

---

ps:b站课程《黑马程序员Java13天进阶》根据官方笔记结合自身情况整理的笔记
视频链接