备战面试日记（1.1） - (JavaSE内容.集合篇)

本人本科毕业，21届毕业生，一年工作经验，根据简历，并根据所学知识复习准备面试。

记录日期：2021.12.28

大部分知识点只做大致介绍，具体内容根据推荐博文链接进行详细复习。

• • 集合包
  • • List
    • • 1. ArrayList
      • • 1.1 介绍
        • 1.2 ArrayList关注点
        • • 1.2.1 时间复杂度
          • 1.2.2 扩容
          • 1.2.3. baseRemove方法
          • 1,2.4 序列化
      • 2. linkedList
      • • 1.1 介绍
        • 1.2 linkedList关注点
        • • 1.2.1 复杂度
      • 3.Vector(不做重点)
      • • 1.1 介绍
        • 1.2 Vector关注点
        • • 1.2.1 线程安全
          • 1.2.2 扩容
    • Set
    • • 1. HashSet
      • • 1.1 介绍
    • Map
    • • 1. HashMap（重点）
      • • 1.2 HashMap关注点
        • • 1.2.1 负载因子等参数含义
          • 1.2.2 扩容
          • 1.2.3 1.7与1.8的区别
          • 1.2.4 红黑树与链表的转换
      • 2. CocurrentMap（重点）
      • • 1.2 CocurrentMap关注点
        • • 1.2.1 sizeCtl变量
          • 1.2.2 counterCells变量
          • 1.2.3 1.7和1.8的区别
          • 1.2.4 并发扩容
      • 3. HashTable
      • • 1.1 介绍
        • 1.2 HashTable关注点
        • • 1.2.1 线程安全
          • 1.2.2 hash冲突的四种解决方式（延申）
      • 4. linkedHashMap
      • • 1.1 介绍
        • 1.2 linkedHashMap关注点
        • • 1.2.1 标志位accessOrder
          • 1.2.2 重写迭代器
      • 5.TreeMap
  • 总结

博文参考链接: 再也不担心问到Java集合了，一文讲透Java中的数据结构

本人博文链接: Java1.8源码阅读摘记-集合(1)-ArrayList

java.util.ArrayList，基于数组实现，使用连续的内存空间。

线程不安全。

构造参数上，无参时使用默认容量为10，有参为Integer时传入作为容量，有参为Collection时传入调用Arrays.copyOf()复制集合。

底层操作的对象是 Object[] elementData数组。

底层数组存/取元素效率非常的高(get/set)，时间复杂度是O(1)，而查找，插入和删除元素效率似乎不太高，时间复杂度为O(n)，频繁进行插入和删除会造成频繁的数组复制。

默认扩容到原数组的1.5倍。

方法调用链 : ensureCapacity -> ensureExplicitCapacity -> grow -> hugeCapacity

	
    private void grow(int minCapacity) {
        int oldCapacity = elementData.length; // 原数组的长度
        int newCapacity = oldCapacity + (oldCapacity >> 1); // 原数组的长度 + 原数组的长度 / 2 即原长度1.5倍
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity; // 1.5倍原长度扩容量 < 传入的扩容量时，使用传入的扩容量
        if (newCapacity - MAX_ARRAY_SIZE > 0) // 要更新的扩容量长度大于最大长度，则扩容到 Integer 的最大长度
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity); // 数组复制扩容并赋值
    }

baseRemove方法：在714行，该方法有两个作用，一个是用于批量删除，另一个是用于求交集，通过布尔值complement来控制是否求交集，代码如下。

    private boolean batchRemove(Collection c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false; // 是否修改成功的标识符
        try {
            for (; r < size; r++) // 遍历elementData数组
                if (c.contains(elementData[r]) == complement) // 如果在c集合中存在对应索引的元素
                
                    elementData[w++] = elementData[r];
        } finally { // 遍历完成之后
            // Preserve behavioral compatibility with AbstractCollection <=> 保持与 AbstractCollection 的行为兼容性
            // even if c.contains() throws. <=> 即使 c.contains() 抛出
            
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            
            if (w != size) { // w == size 时，说明数组相同， w ！= size时，清空 >= w 的所有元素被垃圾回收
                // 清空 w 后面的所有元素，保证被gc回收
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w; // 添加修改次数
                size = w; // 缩长，去除多余的容量
                modified = true; // 更改为已修改标识
            }
        }
        return modified;
    }

数组被transient修饰的原因，在序列化中有说明，ArrayList的序列化，主要是过滤掉所有空位，减少多余的占用空间。

    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // Write out element count, and any hidden stuff
        int expectedModCount = modCount;
        s.defaultWriteObject();

        // Write out size as capacity for behavioural compatibility with clone()
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (int i=0; i