1 Java 集合框架接口

  • Collections
  • Map
  • Queue
  • Dequeue
  • SortedSet
  • SortedMap
  • Iterator

2 Collections 集合

  1. List
    • 特点：存储和取出的顺序一致，可存放重复元素，且可以由 Iterator 和 ListIterator 进行迭代；
    • 分类：
      • 读快写慢：
        • ArrayList:
          （1）初始数组容量为 0，在存储第一个元素后容量默认是 10；
          （2）每当容量满了之后再存储元素，会使用 Arrays.copyOf()，将容量扩大 1.5 倍；
          （3）内部维护一个 modCount 用于计算操作数组的次数。内部定义的 Iterator 中维护一个 expectedModCount，使用迭代器对该集合进行迭代时，记录写操作次数，并比较 modCount 与 excpectedModCount 是否一致，若不一致，说明在使用迭代器操作集合时有其他线程对集合进行写操作，抛出 ConcurrentModificationException；
        • Vector：
          （1）与 ArrayList 区别不大，用 synchronized 修饰方法；
      • 读慢写快：
        • LinkedList：
          （1）JDK 1.7 前为双向循环列表，之后取消了循环；
          （2）实现的 ListIterator 可双向遍历，若通过索引获取值，会根据索引在前半还是后半来决定使用顺序遍历还是逆序遍历；
  2. Set
    • 特点：存储和取出顺序不一定一致，不可存放重复元素，对重复的判断是 hashCode() 与 equals() 一致；
    • 分类：
      • HashSet：
        （1）内部维护 HashMap，许多性质与 HashMap 相同；
        （2）Set 的值是 Map 的键，Set 内部通过维护一个 Object 作为 Map 所有键值对的 value；
      • TreeSet：
        （1）内部维护 TreeMap，许多性质与 TreeMap 相同；

3 Map 集合

  1. 常见实现类
    • HashMap：
      图片说明 图片来源于网络
      （1）内部维护一个数组，数组存储链表节点 Node；
      （2）数组长度默认为 16，若长度由用户决定，则必定为 图片说明 ；
      （3）内部维护一个加载因子，若当前容量达到 图片说明 ，则会进行扩容，每次扩容为原来的 2 倍；
      （4）HashMap 通过计算哈希确定存储在数组的位置，计算公式是 图片说明 ，其中容量是 图片说明，即 图片说明 ，在二进制中 图片说明 结果为很多的 1，和 hashCode 进行与运算可以充分散列在数组的各个位置，减少哈希碰撞；
      （5）在 JDK 1.8 后，新增了红黑树。在链表长度到达 8 且 数组长度超过 64 时会开启红黑树；
      （6）put() 方***计算哈希，若计算出的哈希值一样，即存放在数组的位置一样，再使用 equals() 进行比较，如果一致，就替换旧的元素，如果不一样，就存放在链表或红黑树后；
      （7）resize 操作需要 rehash，非常耗时；
      （8）在 JDK 1.8 之前， 并发下的 resize 会导致死锁；
    • TreeMap：
      （1）内部是红黑树结构。根据内部维护的 Comparator 或元素实现的 Comparable 接口对元素进行比较并存放；
      （2）因为需要使用比较器比较元素，所以不能存储 null 的键。
  2. 同步并发实现类
    • HashTable：
      • 键和值都不能为 null；
      • 直接使用键的 hashCode 计算存储位置；
      • 使用 synchronized 修饰方法；
    • ConccurentHashMap：
      • JDK 1.8 前，使用分段式锁，将数组分为 16 份，每一份都有一个锁。之后将锁的粒度调整为 Node，即数组中每个元素都有一把锁；
      • 使用 CAS 存储元素，直到成功为止；
      • 当迭代器对数组进行操作时，其他线程通过 COW 操作数组，即安全失败。

拓展

  1. 快速失败与安全失败
    • 快速失败：即使用 modCount 与 expectedModCount 进行对比，若不一致则抛出 ConccurentModificationException 异常；
    • 安全失败：JUC 下的集合类，线程通过 COW 对数组进行修改，另一个线程的迭代器中无法感知被修改的值；
  2. Iterator 和 Enumeration
    • Iterator：在遍历时，其他线程无法修改集合；
    • Enumeration：占用内存更少；
  3. Iterator 和 ListIterator
    • Iterator：只能向后遍历；
    • ListIterator：可以双向遍历，只有 List 实现类才拥有。