Collection

List — 有序可重复列表

ArrayList

1. 底层是用数组实现的，重要的成员有元素数组/数组中元素数 size/ modCount 修改次数。
2. 进行 add 添加时，若没有指定添加位置，就会根据 size 确定添加的新元素在数组中的下标进行添加，若 size >= 数组长度，则需要扩容。
3. 在进行扩容时，会将 modCount++，并且会将原数组中的元素，拷贝至新数组中，新数组的大小是原数组的 1.5 倍，默认的初始容量是 0，且在第一次添加元素时，设置数组大小为10。

• 若指定 i 为添加元素的位置，会调用 System.ArrayCopy 方法对 i 下标以后的元素进行拷贝，拷贝完成后再把添加的元素放在 i 位置。
• 调用 get 方法时，由于 ArrayList 底层基于数组，因此实现了一个 RandomAccess 标识接口，表示按下标读取数据速度很快，主要是由于数组在内存中是连续存储，可以通过第一个元素的存储地址和偏移量offset 直接计算得到访问的元素的存储地址。
• 若 contains 方法是通过元素的值进行查找，则需要遍历数组。

手写ArrayList

10个月前

0495

LinkedList

• LinkedList 是基于链表存储的，链表中节点 Node 重要包含存储的元素的引用 E，指向前驱节点指针prev 和指向后继节点的指针 next，LinkedList 中重要成员主要有 size/头节点 first/尾节点 last。
• LinkedList 由于 Node 在内存中是分散存储的，因此没有对 size 限制，在执行 add 方法时，默认添加在链表的尾部。
• 若指定添加元素在链表中的位置，LinkedList 需要调用 node 方法，传入参数 Index 找到对应的节点，在查找对应的节点时，若 Index < size / 2，从头节点向后遍历，若 Index > size / 2，从尾节点向前遍历，因此即使添加元素只需要改变节点的指针，但查找添加的位置的耗时仍然不小，开销不比 ArrayList 少。
• 调用 get 方法时，若按下标查找，也需要进行同样的遍历，性能比 ArrayList 差很多，按 contains 进行查找时，也需要进行遍历，与 ArrayList 相比半斤八两。
• 链表节点除了元素值，还需要维护两个指针，导致 LinkedList 存储的内存开销远大于 ArrayList。

手写LinkedList

10个月前

06411

Vector & Stack

• Vector 也是基于数组进行存储，其原理与 ArrayList 类似，区别在于，Vector 中会维护一个 CapacityIncrement变量，每一次进行扩容时，只增加一个 CapacityIncrement 变量的大小，若没有指定 CapacityIncrement，默认为 0，且在扩容时，若 CapacityIncrement为 0，则将数组大小翻倍。
• Vector 中的所有增删改查方法，包括 get 方法，都通过在方法上加 Sychronized 锁方式锁住 Vector 对象，实现线程安全，性能较差。

Set — 不可重复列表

1. HashSet：内部有一个成员变量的 HashMap，实际上就是使用的 HashMap 的方法。
2. TreeSet：内部有一个成员变量的 TreeMap，底层就是 TreeMap。
3. LinkedHashSet：底层调用的 HashSet 的方法，HashSet 中的 HashMap 也可以是 LinkedHashMap，因此实际是由LinkedHashMap 实现。

Queue / Deque

LinkedList 实现 Queue 和 Deque，LinkedList 中使用 first 和 last 两个节点的指针用来标记链表的头/尾节点，当进行 add 方法添加时，默认是在链表尾部添加，调用 poll 方法时，就会返回 first 节点，调用 pop 方法时，返回 last 节点。

ArrayDeque

数组的方式实现了双端队列，主要是使用 head 和 tail 两个指针来标记 队列头/栈底 和 队列尾/栈顶。

PriorityQueue

• 使用数组的方式实现了优先队列，内部其实是一个二叉堆结构（小顶堆），原理逻辑与堆排序一致重要属性有 size，用来标记数组中元素的个数，即新添加的元素的下标。
• 执行 offer 方法时，先确认 size 是否大于等于数组长度，若大于等于则进行扩容，执行 siftup 方法。siftup 方法中，若制定了 Comparator，按照 Comparator 的 compare 方法与父节点比较，也就是 (size - 1) >>> 1下标对应的元素进行堆的插入，若没有指定，按元素实现的 Comparable 接口的 compareTo 方法进行比较。
• 执行 poll() 方法时，若 size 为 0，返回空值，否则返回数组中下标为 0 的堆顶元素，将数组下标 0 位置替换为 size – 1位置的元素，并减小 size，调用 siftdown 方法整理堆。
• siftdown 方法同样也分为根据 Comparator 和 Comparable 两种比较，主要是对 0 位置新换上来的元素与子节点进行比较，将其与最大的并大于 0 位置的子节点进行交换，并循环直到将其放到合适的位置。

BlockQueue

• 阻塞队列（BlockingQueue）是一个线程安全的队列，它可以保证在队列满时，生产者线程会被阻塞，直到队列有空闲空间；在队列为空时，消费者线程会被阻塞，直到队列有元素可供消费。
• 阻塞队列常用于生产者消费者模型，在这种模型中，生产者线程负责往队列中添加元素，消费者线程负责从队列中取出元素。阻塞队列可以保证生产者线程和消费者线程之间不会发生数据竞争，从而提高并发效率。

Map

HashMap

重要成员变量

1. 负载因子：默认为 0.75，表示 HashMap 存储的元素数到达 HashMap 散列数组长度的 0.75 时就进行扩容，负载因子越大，散列数组的内存利用率越高，但哈希冲突概率也越高，查询效率相对降低；负载因子越小，散列数组的内存利用率越低，但哈希冲突概率越低，查询效率相对较高。
2. 散列数组：HashMap 通过分离链表法解决哈希冲突的问题，在散列数组中存储的就是链表中的一个个头节点。
3. K-V 键值对：以 Node 节点的方式进行存储，Node 继承自 Map.Entry，包含 Next 指针，Key，Value 和 hash。
4. threshold 门限：就是 负载因子 * 数组容量。
5. size：HashMap 中当前存储的节点数。

put 方法流程

1. 再哈希：首先对 Key 进行再哈希，将 Key 的 HashCode 按位有符号右移 16 位，再与原本的 HashCode 进行异或

   目的：在对散列数组长度取余时，高位通常不参与运算，再哈希让高位参与哈希运算，让低位尽量不同，使哈希分布更均匀

2. 检查散列数组是否为空，若为空，初始化散列数组。
3. 若 Key 的 HashCode 对应的散列数组位置上节点为空，则直接将新节点加入。
4. 若不为空，比较链表的头节点 Key 与 put Key 是否相等，先比较 hashcode，再比较（== || equals），若相等，进行更新，若不相等，顺着链表按同样的逻辑进行比较。
5. 若是 1.8 的HashMap，会先判断链表的头节点是否是 TreeNode，若是，则按照红黑树的逻辑进行插入。
6. 1.7 的 HashMap 中，若遍历完链表仍未找到 Key 相同的节点，则将新节点加入到链表头，会造成并发扩容的死链问题，1.8 中，将头插法改为了尾插法，解决了死链问题，但并发环境下的其他基本问题，如更新丢失等，仍然没有解决。

   1.8 以前一直采用头插法的是由于计算机的局部性原理，主要是时间局部性原理，即一个最近被访问过的对象，很有可能很快会被再访问到，基于该假设，在头节点插入，可以有效的提高查询的效率，在发生并发问题时，可以使用concurrent map来解决。

7. 若添加后 size >= threshold，就会进行扩容。

扩容流程

1. 首先 HashMap 的初始容量是 16，并且每次对原数组长度 * 2 进行扩容，当 size > threshold 时就会进行扩容。

   HashMap 每次 * 2 的原因：

   1、2 的幂次可以用 & 的方式进行取余运算，效率更高；

   2、在扩容移动链表节点时，节点在新数组中的位置只可能是原位置 i 或 i + oldCap 旧数组长度，扩容时效率更高。

2. 创建新的散列数组，并将旧的散列数组中的链表的头节点拷贝至新数组中，在移动时，节点的 hash 与 oldCap进行 & 运算，若结果为 0，表示在新数组中位置不变，若不为 0，表示在新数组中位置为 i + oldCap。
3. 在移动节点时，会使用一个 loHead/loTail 和 hiHead/hiTail 分别指向新数组中位置 i 和 i + oldCap 的链表的头尾节点，用一个 next 指针指向当前正在移动节点的下一个节点，在 1.8 中，由于使用尾插法，每一次移动节点都会添加至loTail/hiTail之后，不会发生死链问题，而在 1.7 中，由于使用头插法，每一次移动节点都会添加至 head 之前，会发生扩容死链问题。
4. 1.7 扩容死链问题：t1 线程正在移动 A 节点，next 节点指向 A 节点的下一个节点 B，即 A -> B，此时 t2 线程完成了 A 和 B 的移动，此时 B.next = A，在 t1 移动 A 到新数组中后，当前正在移动节点 e 指向 B，next 指向 B.next = A，此时就形成了链表中的环，最终导致程序崩溃。

以下是 1.7 版本 HashMap 扩容死链问题的示例代码：

public class HashMapTest {

    public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<>();
        map.put("a", "1");
        map.put("b", "2");
        map.put("c", "3");

        // 创建一个线程，负责扩容 HashMap
        new Thread(() -> {
            map.put("d", "4");
            map.put("e", "5");
            map.put("f", "6");
        }).start();

        // 创建另一个线程，负责遍历 HashMap
        new Thread(() -> {
            for (String key : map.keySet()) {
                System.out.println(key);
            }
        }).start();
    }
}

1.8 红黑树

与 AVL 树比较

1. 增删性能，红黑树较好AVL

   树通过节点的左右子树高度差是否大于 1 判断是否平衡，若不平衡，需要通过单/双旋转恢复平衡，而红黑树主要根据节点颜色和节点到子孙节点路径上黑节点数量判断平衡，可以通过改变节点颜色或者旋转恢复平衡，开销较小。

2. 查询性能，AVL 树较好

   AVL树的最大高度为 1.44 * log(N + 2)，一般情况只比 log(N) 稍大，红黑树由于平衡判断更加宽松，由着色法则得到的最大高度为 2 * log(N + 1)，因此性能会稍微差于 AVL 树。

3. 内存空间消耗，红黑树稍大。
4. 为什么不用跳表？

   1、跳表的实现更加灵活简单，并且在范围查找上非常方便，Redis 中 ZSet 就使用跳表 + 散列的结构。

   2、红黑树在空间复杂度上更胜一筹，通常发生了红黑树化的情况，都是数据量非常非常大时，此时红黑树空间占用小的优点将更加明显，并且 HashMap 的元素本身是无序的，即用不到跳表范围查找的优势。

特点

• 每个节点不是黑色就是红色，根节点是黑色。
• 红色节点的子节点必须是黑色。
• 从一个节点到每一个子孙节点的路径上的黑色节点数必须相同。

HashMap 中什么时候树化/树退化

1. 当链表长度达到 8 时进行树化

   在 HashMap 源码注解中有解释为什么是 8，大概意思是，红黑树的节点大小大约是正常节点大小的两倍，并且当节点数较少时链表与红黑树的查找效率差距可以忽略不记，在理想情况下，使用 0.75 作为负载因子，采用随机哈希算法，树化阈值与树化概率遵循泊松分布，选择 8 的概率是千万分之 6，7 的概率约是十万分之 1。

2. 当扩容后链表长度小于等于 6 进行树的退化。

   红黑树的节点大小大约是正常节点大小的两倍，并且当节点数较少时链表与红黑树的查找效率差距可以忽略不记，并且在插入和删除时维护红黑树的平衡性需要额外的开销

ConcurrentHashMap

1. 通过分段锁 Segment 保证线程安全，Segment 继承自 ReentrantLock，每一个 Segment 中都包含一个 volatile 的HashEntry 数组，一个 volatile 的 count 表示当前 Segment 中存储的 K-V 节点数，一个 Threshold 表示扩容阈值。
2. HashEntry 是基本存储单位，与 HashMap 中的Entry 基本一样，包含 Key，Value，next，hash，区别在于 HashEntry 的Value 是volatile 的，因此对 value 的修改对所有线程可见，并且 next 指针是 final 修饰，防止扩容时发生死链。
3. ConcurrentHashMap 默认有一个长度为 16 的 Segment 数组，在进行增删改查时，会根据 Key 对 16 取余得到具体处于哪个 Segment，对于 get 操作不加锁执行，对于 put 等修改操作，调用 Segment 的 lock 方法锁住当前段进行修改，不影响其他段的并发操作，在进行扩容时，也仅是对单个 Segment 进行扩容。
4. 1.8 的 ConcurrentHashMap 摒弃了 Segment，采用 CAS 和类似于分段锁的方式保证线程安全。
5. 大体结构与 HashMap 一样，在 put 操作时，若 Node 数组对应下标处为空，使用 CAS 的方式不加锁添加节点，若数组中当前位置链表头节点不为空，则对链表头节点加锁，在 Sychronized 同步代码块中执行与 HashMap 同样的逻辑。
6. ConcurrentHashMap 在扩容时的移动原数组节点到新数组的操作，可以由多个线程并发完成，从而大大提高效率，在进行移动时，会将当前线程正在移动的头节点包装为一个 ForwardNode，用来标识当前位置正在移动，当其他线程遍历到数组中的ForwardNode节点时，就会忽略并继续遍历，从而保证线程安全，并且在扩容时，仍然可以执行增删改查操作，这些操作通过头节点的hash 判断是否是一个 ForwardNode 节点，若是，则调用 helpTransfer 方法，并发的帮助完成扩容动作，完成后再回到循环中执行put。
7. get 方法也是通过 Unsafe 的 getObjectVolatile 进行读取，不加锁。

TreeMap

底层是红黑树。

LinkedHashMap

采用 HashMap 来存储节点，用一个双向链表存储 HashMap 的 Node 节点使其有序。

HashTable

使用 Sychronized 锁住方法来保证线程安全，并且默认初始容量为 11，每一次扩容为 oldCap * 2 + 1。

Iterator 迭代器

1. 用来进行集合的遍历，不同的集合有不同的实现，例如 ArrayList 通过一个 cursor 指向下一个遍历的元素的下标，用一个 lastRet 表示上一个遍历的元素的下标。
2. Iterator 接口中主要包含三个基本方法，hasNext 判断是否还有下一个元素，next 表示遍历获取下一个元素，remove 表示删除元素。
3. 常见的三种遍历方式，fori，foreach，Iterator，其中 fori 只能用于知道集合中具体元素数量时，fori 和 foreach 只能用于知道集合中元素具体类型时，foreach 底层就是 Iterator 的方式遍历。
4. 三种遍历方式的删除fori：

   在 fori 进行删除时，问题在于删除当前下标会导致之后的元素前移，比如 “A，B，B，C，C”，在 fori 中判断若元素等于 B 就删除，则会导致 i = 1 时，进行删除后，i = 2 位置的 B 到达 1 的位置，即 “A，B，C，C”，而此时 i 已经到达 2 的位置，即 i 指向 C，从而造成漏删，可以通过删除后让 i - 1，或者反向遍历删除解决。

   foreach：对于 ArrayList 等迭代器是 fail-fast 的集合，在遍历时底层是使用迭代器进行遍历，但在删除元素时，由于没有显式的获取迭代器，因此调用的是 List 的 remove 方法，会触发迭代器的 fail-fast 机制，抛出异常中断程序。

   Iterator：没有任何问题。

5. fail-fast：迭代器实现了 fail-fast 机制的集合，在集合中都会维护一个 modCount 成员变量，用来表示对集合的修改次数，在获取迭代器时，在迭代器中会为一个 ExpectedModCount 变量赋值为当前的 modCount，在执行 next，remove，hasnext方法之前，会先对迭代器的 ExpectedModCount 与集合的 modCount 进行比较，若不相等直接抛出异常。
6. fail-safe：Java 中实现 fail-safe 迭代器的集合主要都是通过 Copy-On-Write 方法实现的，例如 CopyOnWriteList，其内部有一个 ReentrantLock 锁对象，在进行增删改操作时，先加锁，将原有的数组拷贝一份，在新的数组上进行修改，而获取迭代器时，会用一个 final 变量指向当前的数组，在旧的数组上进行遍历。

本文文档