学习笔记 - Java集合框架

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 实现类才拥有。