集合

可以将集合分为2个大类

集合 - 图1

Collection接口

API方法：

集合 - 图2

注意Collection是接口，需要子类才能实现，里面只能存储引用类型，所以会进行自动拆箱和装箱。

遍历：

增强for，还有迭代器遍历

  1. // 迭代器遍历
  2. Iterator it = col.iterator();
  3. while (it.hasNext()) {
  4.     System.out.println(it.next());
  5. }

实现类以及子接口

图示：

集合 - 图3

List接口

ArrayList实现类源码

JDK1.7

类中的成员变量

集合 - 图4

初始化，在JDK1.7中会默认初始化成员变量elementData数组的大小为10

集合 - 图5

  1. 对应的内存关系

集合 - 图6

add()方法

集合 - 图7

  • 如果数组的10个位置都满后，就开始进行数组的扩容，扩容长度为原数组的1.5倍
    集合 - 图8
  • 判断是否扩容

集合 - 图9

  • 扩容步骤

集合 - 图10

总结：底层数组，在调用构造器的时候，数组长度初始化10，扩容的时候扩展为原数组的1.5倍

JDK1.8

类中的成员变量，和1.7一致。

集合 - 图11

new 一个对象时的初始化，注意此时初始化数组的大小为一个常量，而常量值为0，则JDK1.8中初始化并没有申请一个长度为10的数组。

集合 - 图12

集合 - 图13

add方法

集合 - 图14

  • 调用初始化方法

集合 - 图15

  • 此时在参数中会调用初始化扩容大小的方法

集合 - 图16

集合 - 图17

  • 此时minCapacity已经被赋值为10，与原数组大小比较判断是否进行扩容

集合 - 图18

  • 此时才是grow的扩容实现

集合 - 图19

总结：底层数组实现，在调用构造器的时候，底层数组为f，在调用add方法以后底层数组才重新赋值为新数组，新数组的长度为10-》节省了内存，在add后才创建长度为10的数组。

Vector实现类

成员变量，也是数组实现

集合 - 图20

初始化值，为10

集合 - 图21

集合 - 图22

add方法

  • 注意add方法加了锁，所以是线程安全的
    集合 - 图23
  • 扩容中间步骤和ArrayList大致一样
    集合 - 图24
  • 扩容步骤，注意此时扩容的大小是原数组2倍，而不是1.5倍
    集合 - 图25

总结：都是数组进行实现，但和ArrayList的区别就是，线程安全，扩容的大小是2倍，因此造成了效率低，所以被弃用。

LinkedList实现类

LinkedList时有双向链表实现

  1. transient int size = 0;        // 节点个数
  3. /**
  4.  * Pointer to first node.
  5.  * Invariant: (first == null && last == null) ||
  6.  *            (first.prev == null && first.item != null)
  7.  */
  8. transient Node<E> first;    // 前节点
  10. /**
  11.  * Pointer to last node.
  12.  * Invariant: (first == null && last == null) ||
  13.  *            (last.next == null && last.item != null)
  14.  */
  15. transient Node<E> last;        // 后节点
  17. /**
  18.  * Constructs an empty list.
  19.  */
  20. public LinkedList() {        // 构造方法
  21. }
  23. public LinkedList(Collection<? extends E> c) {
  24.     this();
  25.     addAll(c);
  26. }

add方法：

  • 会返回boolean类型 
    1. public boolean add(E e) {
    2.  linkLast(e);
    3.  return true;
    4. }
  • 调用linkLast方法，方法实现 
    1. /**
    2. * Links e as last element.
    3. */
    4. void linkLast(E e) {
    5.  final Node<E> l = last;    // 创建一个节点，作为最后一个节点的临时值
    6.  final Node<E> newNode = new Node<>(l, e, null);    // 此时添加节点在最后的位置，l作为前节点，null作为后节点
    7.  last = newNode;    // 赋值给last，更新最后一个元素
    8.  if (l == null)    // 如果添加的时第一个元素
    9.      first = newNode; // 将第一个节点指向newNode节点
    10.  else
    11.      l.next = newNode;    // 如果不是，进行连接，l指向新生成的节点
    12.  size++;    // 大小加一
    13.  modCount++;
    14. }

get方法：

  • getLast()和getFirst()方法直接通过first和last节点取值即可，而get方法有些区别： 
    1. public E get(int index) {
    2.  checkElementIndex(index);    // 健壮性检查
    3.  return node(index).item;
    4. }

  • node方法的具体实现，注意优化步骤 

    1. Node<E> node(int index) {
    2.  // assert isElementIndex(index);
    4.  if (index < (size >> 1)) {    // 将链表分成两半，提高检索效率，如果此时查找的元素在前半部分，那么从first开始向后查找
    5.      Node<E> x = first;
    6.      for (int i = 0; i < index; i++)
    7.          x = x.next;
    8.      return x;
    9.  } else {    // 如果在后半部分，从last元素开始向前查找
    10.      Node<E> x = last;
    11.      for (int i = size - 1; i > index; i--)
    12.          x = x.prev;
    13.      return x;
    14.  }
    15. }

Iterator迭代器

  • 接口关系
    集合 - 图26
  • 可以知道Itr类是ArrayList的内部类
    集合 - 图27
  • Itr具体实现，Itr方法可以调用ArrayList的成员变量，也就是通过cursor表示代表指针来操作数组。
    集合 - 图28

ListIterator迭代器

用于允许程序员沿任一方向遍历列表的列表的迭代器，在迭代期间修改列表，并获取列表中迭代器的当前位置。

常用方法

集合 - 图29

测试遍历方法

  1. public class ListIteratorTest {
  2.     public static void main(String[] args) {
  3.         ArrayList<String> list = new ArrayList<>();
  4.         list.add("aa");
  5.         list.add("bb");
  6.         list.add("cc");
  7.         list.add("dd");
  8.         list.add("ee");
  10.         // 将ff插入cc的后面
  11. //        Iterator<String> it = list.iterator();
  12. //        while (it.hasNext()) {
  13. //            if ("cc".equals(it.next())) {
  14. //                list.add("ff"); // 报错ConcurrentModificationException，就是迭代器和list共同操作数组
  15. //            }
  16. //        }
  18.          // 此时可以使用LinkIterator操作数组
  19.         ListIterator<String> it1 = list.listIterator();
  20.         while (it1.hasNext()) {
  21.             if ("cc".equals(it1.next())) {
  22.                 it1.add("ff"); // 此时都是迭代器来操作
  23.             }
  24.         }
  26.         System.out.println(list);   // [aa, bb, cc, ff, dd, ee]
  28.         // 可以逆向遍历
  29.         while (it1.hasPrevious()) {
  30.             System.out.println(it1.previous());    // ee dd ff cc bb aa 
  31.         }
  32.     }
  33. }

后序遍历

Set接口

HashSet实现类

此类实现Set接口，由哈希表（实际为HashMap实例）支持。对集合的迭代次序不作任何保证;特别是，它不能保证订单在一段时间内保持不变。这个类允许null元素。

这个类提供了基本操作（add，remove，contains和size）固定的时间性能，假定哈希函数将分散的桶中正确的元素。 迭代此集合需要与HashSet实例的大小（元素数量）和后台HashMap实例（桶数）的“容量”的总和成比例的时间。 因此，如果迭代性能很重要，不要将初始容量设置得太高（或负载因子太低）是非常重要的。

请注意，此实现不同步。

常用方法

可以看出hashset没有关于索引的方法。

集合 - 图30

在add元素时，如果没有重写equals方法，那么set将不能判重。

原理图

集合 - 图31

比较器

比较int
  1. int a = 10;
  2.         int b = 20;
  3.         System.out.println(a-b); // =0  >0  <0

比较double
  1.  double a = 9.6;
  2.         double b = 9.3;
  3.        /* System.out.println((int)(a-b));*/
  4.         System.out.println(((Double) a).compareTo((Double) b));

比较String
  1. String a = "A";
  2.         String b = "B";
  3.         System.out.println(a.compareTo(b));

比较自定义类型

  • 内部比较器
    实现Comparable接口，重写compareTo方法 

    1. public class Student implements Comparable<Student> {
    2.  private int age;
    3.  private double height;
    4.  private String name;
    6.  public int getAge() {
    7.      return age;
    8.  }
    10.  public void setAge(int age) {
    11.      this.age = age;
    12.  }
    14.  public double getHeight() {
    15.      return height;
    16.  }
    18.  public void setHeight(double height) {
    19.      this.height = height;
    20.  }
    22.  public String getName() {
    23.      return name;
    24.  }
    26.  public void setName(String name) {
    27.      this.name = name;
    28.  }
    30.  public Student(int age, double height, String name) {
    31.      this.age = age;
    32.      this.height = height;
    33.      this.name = name;
    34.  }
    36.  @Override
    37.  public String toString() {
    38.      return "Student{" +
    39.              "age=" + age +
    40.              ", height=" + height +
    41.              ", name='" + name + '\'' +
    42.              '}';
    43.  }
    45.  @Override
    46.  public int compareTo(Student o) {
    47.      // 以年龄进行比较
    48. //        return this.age - o.getAge();
    49.      // 以name进行比较
    50.      return this.getName().compareTo(o.getName());
    51.  }
    52. }
  • 外部比较器
    可以自己写一个类，也可以使用匿名内部类 
    1. public class ComparatorTest {
    2.  public static void main(String[] args) {
    3.      // 比较两个自定义类型
    4.      Student s1 = new Student(14, 160.5, "alili");
    5.      Student s2 = new Student(14, 170.5, "bnana");
    6.      Comparator<Student> com = new Comparator<Student>() {
    7.          @Override
    8.          public int compare(Student o1, Student o2) {
    9.              // 按照年龄进行比较
    10.              return o1.getAge() - o2.getAge();
    11.          }
    12.      };
    13.      System.out.println(com.compare(s1, s2));
    14.  }
    15. }

TreeSet实现类

TreeSet和HashSet一样，保证了元素时唯一，但内部使其排列（可以自定义比较器来控制其升序还是降序）。但升序的比较是按照比较器来定义。

常用方法

查api

原理结构图

底层逻辑结构便是二叉搜索树，通过比较器进行比较来判断往哪放，输出的话逻辑上就是中序遍历，保证升序输出。

集合 - 图32

使用实例

如果在TreeSet中加入String和Integer等包装类类型的话TreeSet会自动排序，因为包装类中都实现了内部比较器。

例如Double：

集合 - 图33

而自定义类需要自己定义

  • 内部比较器需要类实现Comparable接口，重写compareTo方法
  • 外部比较器 
    1. public class TreeSetTest {
    2.  public static void main(String[] args) {
    3.      //创建一个TreeSet:
    4.      TreeSet<Student> ts = new TreeSet<>(new Comparator<Student>() {
    5.          @Override
    6.          public int compare(Student o1, Student o2) {
    7.              // 按照年龄进行升序
    8.              return o1.getAge() - o2.getAge();
    9.          }
    10.      });
    11.      ts.add(new Student(10, 180, "elili"));
    12.      ts.add(new Student(8, 184, "blili"));
    13.      ts.add(new Student(4, 165, "alili"));
    14.      ts.add(new Student(9, 155, "elili"));
    15.      ts.add(new Student(10, 143, "flili"));
    16.      ts.add(new Student(1, 175, "dlili"));
    17.      System.out.println(ts.size());
    18.      System.out.println(ts);
    19.  }
    20. }

    外部比较器利用堕胎，扩展性好

Map接口

实现类以及子接口

集合 - 图34

常用方法

  1. package com.msb.test11;
  2. import java.util.Collection;
  3. import java.util.HashMap;
  4. import java.util.Map;
  5. import java.util.Set;
  6. /**
  7.  * @author : msb-zhaoss
  8.  */
  9. public class Test01 {
  10.     //这是main方法，程序的入口
  11.     public static void main(String[] args) {
  12.         /*
  13.         增加：put(K key, V value)
  14.         删除：clear() remove(Object key)
  15.         修改：
  16.         查看：entrySet() get(Object key) keySet() size() values()
  17.         判断：containsKey(Object key) containsValue(Object value)
  18.             equals(Object o) isEmpty()
  19.          */
  20.         //创建一个Map集合：无序，唯一
  21.         Map<String,Integer> map = new HashMap<>();
  22.         System.out.println(map.put("lili", 10101010));
  23.         map.put("nana",12345234);
  24.         map.put("feifei",34563465);
  25.         System.out.println(map.put("lili", 34565677));
  26.         map.put("mingming",12323);
  27.         /*map.clear();清空*/
  28.         /*map.remove("feifei");移除*/
  29.         System.out.println(map.size());
  30.         System.out.println(map);
  31.         System.out.println(map.containsKey("lili"));
  32.         System.out.println(map.containsValue(12323));
  33.         Map<String,Integer> map2 = new HashMap<>();
  34.         System.out.println(map2.put("lili", 10101010));
  35.         map2.put("nana",12345234);
  36.         map2.put("feifei",34563465);
  37.         System.out.println(map2.put("lili", 34565677));
  38.         map2.put("mingming2",12323);
  39.         System.out.println(map==map2);
  40.         System.out.println(map.equals(map2));//equals进行了重写，比较的是集合中的值是否一致
  41.         System.out.println("判断是否为空："+map.isEmpty());
  42.         System.out.println(map.get("nana"));
  43.         System.out.println("-----------------------------------");
  44.         //keySet()对集合中的key进行遍历查看：
  45.         Set<String> set = map.keySet();
  46.         for(String s:set){
  47.             System.out.println(s);
  48.         }
  49.         System.out.println("-----------------------------------");
  50.         //values()对集合中的value进行遍历查看：
  51.         Collection<Integer> values = map.values();
  52.         for(Integer i:values){
  53.             System.out.println(i);
  54.         }
  55.         System.out.println("-----------------------------------");
  56.         //get(Object key) keySet()
  57.         Set<String> set2 = map.keySet();
  58.         for(String s:set2){
  59.             System.out.println(map.get(s));
  60.         }
  61.         System.out.println("-----------------------------------");
  62.         //entrySet()
  63.         Set<Map.Entry<String, Integer>> entries = map.entrySet();
  64.         for(Map.Entry<String, Integer> e:entries){
  65.             System.out.println(e.getKey()+"----"+e.getValue());
  66.         }
  67.     }
  68. }

TreeMap

和TreeSet使用一样，需要实现内部或者外部比较器

HashMap

HashMap底层代码细节参照🔗

红黑树介绍参照🔗