1、集合概述

  • 什么是集合？集合有什么用？

    • 数组其实就是一个集合，集合实际上是一个容器，它可以容纳其他类型的数据，集合为什么在开发中使用最多？
      • 集合是一个容器，是一个载体，可以容纳多个对象，在实际开发中，假设连接数据库，数据库种有10条记录，那么假设把10条记录查询出来，在java程序中会将10条数据封装成10个java对象，然后将10个对象放在一个集合中，将集合传到前端，然后遍历集合，将一个数据一个数据展现出来
    • 集合不能存储基本数据类型，也不能存储java对象，集合当中存储的都是java对象的内存地址，（或者说集合中存储的是引用），集合在java中本身是一个对象，集合中任何时候存储的都是引用
    • java中每一个不同的集合，底层会对应的不同的数据结构，往不同的集合中存储元素，等于将数据放到了不同的数据结构中去，什么是数据结构？数据存储的结构就是数据结构，不同的数据结构，数据存储方式不同，例如：
      • 数组
      • 链表
      • 哈希表
      • 使用不同的集合就是使用不同的数据结构

        2、集合在java jdk哪个包下？

  • java.util.*

    • 所有的集合类和集合接口都在java.util下

      3、背会集合的继承结构图

      4、集合分类

      4.1单个方式存储元素，这一类集合超级父接口：java.util.Collection

      image.png
      image.png

      4.2 键值对的方式，超级父接口，java.util.

      image.png

4.3 总结

  • ArrayList: 底层是数组
  • LinkedList: 底层双向列表
  • Vector: 底层是数组，线程安全的，效率低，使用较少
  • HashSet: 底层是HashMap,放到HashSet集合中的元素等同于放到HashMap集合key部分了
  • TreeSet: 底层是TreeMap,放到TreeSet集合中的元素等同于放到TreeMap集合key部分了
  • HashMap: 底层是哈希表
  • Hashtable:底层也是哈希表，只不过线程安全的，效率较低，使用较少
  • Properties: 线程安全，key和value只能存储字符串String
  • TreeMap: 底层是二叉树，TreeMap中的key可以按照自动大小排序

    4.4 特点

    image.png

    5、collection

    5.1 集合中通用方法

    ```python package com.collection;

import com.oop.Student;

import java.util.ArrayList; import java.util.Collection;

/ java.util.collection 中常用的方法 1、Collection 中能存放什么元素 没有使用泛型之前，Collection中可以存储object所有子类型 使用了泛型之后，Collection只能存储某个具体类型 Collection中什么都能存，只能是object的子类就行 集合中不能直接存储基本数据类型，不能存储java对象，只是存储java对象的内存地址 / public class Demo01 { public static void main(String[] args) { // 1、创建一个对象 // Collection collection = new Collection(); 接口是抽象的，无法实例化 Collection c = new ArrayList(); c.add(100);// 实际放进去一个对象的内存地址，Integer x = new Integer() c.add(new Student1());// 自动装箱

  1.     //2、获取集合中元素个数
  2.     System.out.println("集合中的元素个数："+c.size());
  4.     // 3、判断集合中是否包含元素
  5.     System.out.println("集合中是否包含元素100："+c.contains(100));
  6.     // 4、移除元素
  7.     c.remove(100);
  8.     System.out.println("集合中是否包含元素100："+c.contains(100));
  9.     // 5、isEmpty()
  10.     System.out.println("集合中元素是否为空：" + c.isEmpty());
  11.     // 6、元素清空 clear
  12.     // 7、将集合转为数组
  13.     Object[] objs = c.toArray();
  14.     for(int i = 0; i < objs.length; i++){
  15.         Object o = objs[i];
  16.         System.out.println(o);
  17.     }
  19. }

}

class Student1{

}

  1. <a name="RN0gk"></a>
  2. #### 5.2 关于集合中遍历|迭代专题（重点 *****）
  3. ```python
  4. package com.collection;
  6. import java.util.Collection;
  7. import java.util.HashSet;
  8. import java.util.Iterator;
  10. /*
  11. 关于集合中遍历|迭代专题（重点 *****）
  12.  */
  13. public class Demo02 {
  14.     public static void main(String[] args) {
  15. //        以下讲解的是通用的迭代、遍历方式
  16. //        Map中不能用，在所有的collection以及子类中使用
  17.         //创建集合对象
  18.         Collection c = new HashSet();
  19.         c.add("abc");
  20.         c.add(100);
  21.         c.add(true);
  22.         c.add(3.14);
  23.         Iterator iterator = c.iterator();
  24.         while(iterator.hasNext()){
  25.             Object obj = iterator.next();
  26.             System.out.println("迭代元素: " + obj);
  27.         }
  28. //        迭代元素: abc
  29. //        迭代元素: 100
  30. //        迭代元素: 3.14
  31. //        迭代元素: true
  32.     }
  33. }

5.3 Collection集合的contains方法

image.png

  1. package com.collection;
  3. import java.util.ArrayList;
  4. import java.util.Collection;
  6. /*
  7. Collection集合的 contains方法
  8.     contains方法是判断集合中是否包含某个元素的方法
  9.     调用了equals方法进行比对
  10.     equals方法返回true则包含
  11.  */
  12. public class Demo03 {
  13.     public static void main(String[] args) {
  14.         Collection c = new ArrayList();
  16.         String s1 = new String("abc");
  17.         c.add(s1);
  18.         String s2 = new String("def");
  19.         c.add(s2);
  20.         System.out.println(c.size());//2
  22.         String x = new String("abc");
  23.         System.out.println(c.contains(x));//true String类的equals方法重写了比较内容
  25.     }
  26. }

5.5 存放在集合中的类型要重写equals方法

  1. package com.collection;
  3. import java.util.ArrayList;
  4. import java.util.Collection;
  6. public class Demo04 {
  7.     public static void main(String[] args) {
  8.         Collection c = new ArrayList();
  10.         User u1 = new User("jack");
  11.         User u2 = new User("jack");
  12.         c.add(u1);
  13.         System.out.println(c.contains(u2)); // 为重写equals方法 返回false
  14.     }
  15. }
  16. class User{
  17.     private String name;
  19.     public User() {}
  21.     public User(String name) {
  22.         this.name = name;
  23.     }
  25.     @Override
  26.     public boolean equals(Object obj) {
  27.         if (obj == null || !(obj instanceof User)) return false;
  28.         if (obj == this) return true;
  29.         User u = (User)obj;
  30.         return u.name.equals(this.name);
  31.     }
  32. }

5.6 remove方法

  1. package com.collection;
  3. import java.util.ArrayList;
  4. import java.util.Collection;
  6. public class Demo05 {
  7.     public static void main(String[] args) {
  8.         Collection c = new ArrayList();
  10.         String s1 = new String("abc");
  11.         c.add(s1);
  12.         String s2 = new String("abc");
  13.         c.remove(s2);
  14.         System.out.println(c.contains(s1));//false, remove重写了equals方法，删除了内容abc
  15.     }
  16. }

5.7 集合结构发生改变，迭代器需要重新获取

  1. package com.collection;
  3. import java.util.ArrayList;
  4. import java.util.Collection;
  5. import java.util.Iterator;
  7. /*
  8. 集合结构发生改变时，迭代器必须重新获取，否则发生异常，Java.util.ConcurrentModifycationException
  9. 编写代码时，next()方法返回值类型必须时Object
  10. iterator.remove();// 0 迭代器删除的一定是当前元素
  11.  */
  12. public class Demo06 {
  13.     public static void main(String[] args) {
  14.         Collection c = new ArrayList();
  16.         c.add("abc");
  17.         c.add("def");
  18.         Iterator iterator = c.iterator();
  19.         while (iterator.hasNext()){
  20.             Object o = iterator.next();
  21. //            c.remove(o);
  22.             System.out.println(o);
  23.             System.out.println(iterator.hasNext());
  24.             iterator.remove();// 0 迭代器删除的一定是当前元素
  25.         }
  27.         System.out.println(c.size());
  28.     }
  29. }

6、List特有方法

  1. package com.collection;
  3. import java.util.ArrayList;
  4. import java.util.Iterator;
  5. import java.util.List;
  7. /*
  8. 1、List集合存储元素特点
  9.     有序：List集合中的元素有下标
  10.     从0开始，以1递增
  11.     可重复，存储1一个1，还可存储1
  12. 2、List既可以是Collection接口的子接口，那么List肯定有自己的特色方法
  13. 以下是List方法特有的方法
  14.     void add(int index, E element) 将指定的元素插入此列表中的指定位置（可选操作）。
  15.     E get(int index) 返回此列表中指定位置的元素。
  16.     int indexOf(Object o) 返回此列表中指定元素的第一次出现的索引，如果此列表不包含元素，则返回-1。
  17.     E remove(int index) 删除该列表中指定位置的元素（可选操作）。
  18.     int lastIndexOf(Object o) 返回此列表中指定元素的最后一次出现的索引，如果此列表不包含元素，则返回-1。
  19.     E remove(int index) 删除该列表中指定位置的元素（可选操作）。
  20.     E set(int index, E element) 用指定的元素（可选操作）替换此列表中指定位置的元素。
  22.  */
  23. public class Demo07 {
  24.     public static void main(String[] args) {
  25.         List myList = new ArrayList();
  27.         //添加元素，默认向元素末尾添加元素
  28.         myList.add("abc");
  29.         myList.add("def");
  30.         myList.add(1,100);
  31.         System.out.println(myList.lastIndexOf(100));
  32.         // 通过下表获取元素
  33.         Object obj1 = myList.get(1);
  34.         System.out.println(obj1);
  36.         Iterator c = myList.iterator();
  37.         while(c.hasNext()){
  38.             Object obj = c.next();
  39.             System.out.println(obj);
  40.         }
  41.     }
  42. }

6.1 ArrayList

  • ArrayList集合初始化容量是10
  • 集合底层是object[] 数组
  • 使用的哪个集合最多？ ```python package com.collection;

/ ArrayList 集合 1、默认初始化容量是10 2、集合底层是object数组 3、构造方法 new ArrayList() new ArrayList(20) 4、ArrayList集合内容 增长到原来的1.5倍 ArrayList集合底层是数组，怎么优化？ 尽可能少的内容，因为数组扩容效率比较低，建议使用ArrayList集合 的时候预估元素的个数，给定一个初始化容量 5、数组优点 检索效率比较高，每个元素占用空间大小相同，内存地址连续，知道首元素内存地址，然后知道下标， 通过数据表达式就能计算元素的内存地址，所以检索效率高。 缺点 随机增删元素的效率比较低 6、向数组末尾添加元素 随机增删元素效率比较低 7、向数组末尾添加元素，效率很高，不受影响 8、面试官经常问的问题？ 这么多的集合中，你用的哪个集合最多？ ArrayList 因为往数组末尾添加元素，效率不受影响 另外，我们检索或查找某个元素的操作比较多 / public class Demo08 { public static void main(String[] args) { / ArrayList(Collection<? extends E> c) 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。 / Collection c = new ArrayList();

  1.     c.add(100);
  2.     c.add("abc");
  4.     List c1 = new ArrayList(c);
  6.     for(int i = 0; i < c1.size(); i ++){
  7.         Object o = c1.get(i);
  8.         System.out.println(o);
  9.     }
  10. }

}

  1. <a name="ZsVF4"></a>
  2. ### 7、链表的数据结构
  3. <a name="UlQZW"></a>
  4. #### 7.1 概念
  6. - 基本单元-节点
  7. - 有两个属性，data(存储的数据),next(下一节点的内存地址)
  8. - 优点
  9.    - 增删效率高，不涉及大量元素位移问题
  10. - 缺点
  11.    - 查询效率低，每一次查询某个元素的时候需要从头节点开始往下遍历
  13. ![image.png](https://cdn.nlark.com/yuque/0/2021/png/12881754/1625403632521-0f6b68ac-27e8-4287-874e-812d677c954a.png#clientId=u8c153e9d-933d-4&from=paste&height=354&id=u399cd7e6&margin=%5Bobject%20Object%5D&name=image.png&originHeight=707&originWidth=1405&originalType=binary&ratio=1&size=467000&status=done&style=none&taskId=u677da7cb-6710-423e-8d7d-be334397e9b&width=702.5)
  14. <a name="K5Nhv"></a>
  15. #### 7.2 单链表实现
  16. ```python
  17. // client
  18. package com.danlink;
  20. public class Link {
  21.     // 定义头节点
  22.     Node header = null;
  23.     int size = 0;
  24.     /*
  25.     查找集合最后一个元素
  26.      */
  27.     public Node findLastNode(Node node){
  28.         if (node.next == null){
  29.             return node;
  30.         }
  31.         return findLastNode(node.next);
  32.     }
  33.     /*
  34.     查找某个元素
  35.      */
  37.     // 返回元素个数
  38.     public int size(){
  39.         return size;
  40.     }
  41.     // 添加链表中某个数据
  42.     public void add(Object data){
  43.         if (header == null){
  44.             header = new Node(data,null);
  45.         }else{
  46.             Node lasNnode = findLastNode(header);
  47.             lasNnode.next = new Node(data,null);
  48.         }
  49.         size += 1;
  50.     }
  51.     // 删除
  52.     public void remove(Object obj){
  54.     }
  55.     // 修改
  56.     public void modify(Object obj){
  58.     }
  59.     // 查询
  60.     public void find(Object obj){
  62.     }
  63. }
  64. // Node
  65. package com.danlink;
  66. /*
  67. 单链表中的节点
  68. 节点是单链表的基本单元
  69. 每一个节点Node都有两个属性
  70.     一个属性：是存储的数据
  71.     另一个属性：是下一个节点的内存地址
  72.  */
  73. public class Node {
  74.     // 存储的数据
  75.     Object data;
  76.     // 下一个节点的地址
  77.     Node next;
  79.     public Node() {}
  81.     public Node(Object data, Node next) {
  82.         this.data = data;
  83.         this.next = next;
  84.     }
  85. }
  86. // link
  87. package com.danlink;
  89. public class Link {
  90.     // 定义头节点
  91.     Node header = null;
  92.     int size = 0;
  93.     /*
  94.     查找集合最后一个元素
  95.      */
  96.     public Node findLastNode(Node node){
  97.         if (node.next == null){
  98.             return node;
  99.         }
  100.         return findLastNode(node.next);
  101.     }
  102.     /*
  103.     查找某个元素
  104.      */
  106.     // 返回元素个数
  107.     public int size(){
  108.         return size;
  109.     }
  110.     // 添加链表中某个数据
  111.     public void add(Object data){
  112.         if (header == null){
  113.             header = new Node(data,null);
  114.         }else{
  115.             Node lasNnode = findLastNode(header);
  116.             lasNnode.next = new Node(data,null);
  117.         }
  118.         size += 1;
  119.     }
  120.     // 删除
  121.     public void remove(Object obj){
  123.     }
  124.     // 修改
  125.     public void modify(Object obj){
  127.     }
  128.     // 查询
  129.     public void find(Object obj){
  131.     }
  132. }

7.3 链表的优点和缺点

  • 链表的优点
    • 链表的元素在空间存储上内存地址不连续
    • 随机增删元素的时候不会有大量元素位移，因此随机增删效率高，建议在随机增删的业务场景较多时使用LinkedList
  • 链表的缺点
    • 不能通过数学表达式计算查找元素的内存地址，每一次查找都是从头节点开始遍历，直到找到为止，所以linkedList集合索引/查找的效率较低
  • ArrayList:把检索发挥到极致，末尾添加元素效率很高，索引效率高不是因为下标的原因，是因为底层数组发挥的作用，linkedList同样有下标，只能从头节点一个一个遍历
  • LinkedList:把随机增删发挥到极致，

  • 加元素都是到末尾添加，

    7.4 末尾添加元素效率为什么高？

    image.png

  • 找位置通过可计算的内存地址找到，不需要从头开始一个一个遍历

    7.5 LinkedList 源码分析（双向链表）

    image.png

7.6 分析

  1. package kyrie.bao.com.collection;
  3. import java.util.LinkedList;
  4. import java.util.List;
  6. public class Demo01 {
  7.     public static void main(String[] args) {
  8.         List list = new LinkedList();
  9.         list.add("a");
  10.         list.add("b");
  11.         list.add("c");
  13.         for (int i = 0; i < list.size(); i++) {
  14.             Object obj = list.get(i);
  15.             System.out.println(obj);
  16.         }
  17.     }
  18. }

image.png

7.7 Vextor

  1. 非线程安全变成线程安全的
  2. List mylist = new ArrayList();
  3. Collection.syschronizedList(mylist);
  4. mylist.add("a");
  5. mylist.add("b")