image.png

Collection

  • 包含了
    • List
    • Set
    • hashCode约定
    • Map
  • Collection接口：
    • 是Collection继承体系的根接口

Collection体系简介

1. Collection的体系

  • Collection的体系结构
  • List/Set约定

2. Collection体系提供的常用方法

  • new: new ArrayList(Collection), new ArrayList()
  • R: size()/isEmpty()/contains()/for()/stream()
  • C/U: add()/addAll()/retainAll()
  • D: clear()/remove()/removeAll()

List

  • 最常用的ArrayList
    • 本质就是一个数组
  • list的capacity，动态扩容
    • 创建一个更大的空间，然后把原先的元素拷贝进去
  • add()方法

Set

  • 无序，不包含重复元素
    • 判断重复：equals方法
  • 如何实现一个Set
    • Object是不是重复的
    • Hash桶，计算对象的hashCode，去Hash桶里找
      image.png

  • Java世界里第二重要的约定（第一重要是equals）：hashCode

    • 同一个对象必须返回相同的hashCode
    • 两个equals为true的对象，必须返回相同的hashCode
    • 两个对象不等，也可能返回相同的hashCode

      哈希算法

  • 哈希就是一个单向的映射

    • 张三 -> 张，李四 -> 李 （单向映射，不能返回来张 -> 张三）
    • 为何单向：因为对象是有无数种可能的，而如果对应int之类的都是有限的
  • 例子：从姓名到姓到哈希运算
  • 从任意对象到一个整数的hashCode

HashSet

  • 最常用，最高效的Set实现

  • HashSet的高效性

    • 对比ArrayList的查找速度

      1. public static void main(String[] args) {
      2.    Set<Integer> set = new HashSet<>();
      3.    List<Integer> list = new ArrayList<>();
      5.    // 1000_000等同于1000000，易于阅读
      6.    for (int i = 0; i < 1000_000; i++) {
      7.        set.add(i);
      8.        list.add(i);
      9.    }
      11.    long t0 = System.nanoTime();
      12.    set.contains(9999_9999);
      13.    long t1 = System.nanoTime();
      15.    list.contains(9999_9999);
      16.    long t2 = System.nanoTime();
      18.    System.out.println("set: " + (t1 - t0) / 1000.0 / 1000); // set: 0.010884
      19.    System.out.println("list: " + (t2 - t1) / 1000.0 / 1000); // list: 15.394606
      20. }

  • 使用HashSet对ArrayList去重

  • HashSet是无序的！如果有需要可以使用LinkedHashSet
    • HashSet不保证迭代的顺序
    • HashSet不保证顺序是不变的
    • LinkedHashSet可保证顺序和插入顺序一致
  • 原理：与ArrayList不同，HashSet是一个个Hash桶，桶编号是对象的hashCode
    • 桶中的数据接口JDK7及之前是链表，之后在链表长度大于8时会转化为红黑树

image.png

Map

  • C/U:
    • put()/putAll()
  • R:
    • get()/size()
    • containsKey()/containsValue()
    • keySet()/values()/entrySet()
  • D:
    • remove()/clear()

HashMap

  • 最常用，最高效的Map实现
  • 常见问题：
    • HashMap扩容
    • HashMap的线程不安全性
    • HashMap在Java7+后的改变：链表 -> 红黑树
      • 用桶存储hashCode相同的东西，桶里是一个链表
      • 通过一组精心设计的值，可以让哈希桶个数为1个(或极少)，桶查找优势不复存在，变为链表查找，性能恶化，服务器负载升高
        image.png
      • 所以JDK7之后，桶里不再是链表，而是红黑树
  • HashMap和HashSet本质上是一种东西：HashSet里面用了HashMap

有序集合TreeSet/TreeMap

  • 二叉树/红黑树简介
  • 使用Comparable约定，认为排序相等的元素相等
  • 二叉树查找，插入
  • TreeSet数据结构用了红黑树（一种二叉树）

Collections工具方法集合

  • emptySet()/emptyMap(): 返回一个方便的新集合
  • synchronizedCollection：将一个集合变为线程安全的
  • unmodifiableCollection：将一个集合变为不可变的(也可以用Guava的Immutable)

Collection的其他实现

  • Queue/Deque(双端队列)
  • Vector/Stack 已废弃
  • LinkedList
  • ConcurrentHashMap
  • PriorityQueue

Guava（Google，用于补充）

  • 不要重复发明轮⼦！尽量使⽤经过实战检验 的类库
  • Lists/Sets/Maps
  • ImmutableMap/ImmutableSet
  • Multiset/Multimap
  • BiMap