Debug

• 自行回顾跟随源码所得理解
• 能力有限，有问题还请求指正

List

ArrayList

• 维护的是一个 Object 类型的数组 elementData
• 使用的几乎都是 ArrayList 内部类

无参构造器

• 起初构造器给一个空 Object 数组：this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

第一次添加

• add 方法进入，：

• add() 内每次执行 ensureCapacityInternal(size + 1); ( size：0 —> 1，是已存储个数，就是后面的 minCapacity )

  • ensureCapacityInternal(int minCapacity) 内：

    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

    • calculateCapacity() 判断是否 elementData[] 是否为空，空则默认分配 DEFAULT_CAPACITY = 10 返回 ( minCapacity：1 —> 10 )

    • ensureExplicitCapacity(int minCapacity) ：修改加一，确定是否扩容：

      minCapacity - elementData.length > 0 就 grow() 扩容 ( 第一次时 length 还为零 )

  • 真正扩容 —— grow()：

    • 新容量为旧的 1.5 倍 ( int newCapacity = oldCapacity + (oldCapacity >> 1); )，因为第一次零，所以需要修正将初始 10 赋给新 newCapacity ( 只有第一次要修正 )
    • ( 如果超出了包装类某上限会触发 hugeCapacity()，一般不会 )
    • elementData = Arrays.copyOf(elementData, newCapacity); copyOf() 将旧值复制进新扩容后的数组，完成扩容操作

• add() 内 elementData[size++] = e; 新值添加，size++ 移动到下一位，返回 true 完成添加

第二次添加

• add() 执行 ensureCapacityInternal(size + 1);
  • calculateCapacity() 只有在首次添加 elementData 为空时才有作用
  • ensureExplicitCapacity() 修改加一，扩容否
• add() 内 elementData[size++] = e; 依此类推

有参构造器

• 构造器：this.elementData = new Object[initialCapacity];
• 步骤似无参，只是第一次不需要再默认分配零，也不用 grow 扩容
• 直到首次 minCapacity - elementData.length > 0 要存入的、所需的最小容量大于数组现有容量，就 grow() 扩容 1.5 倍 ( 扩容后 copyOf 新 elementData )

Vector

• 维护的是一个 Object 类型的数组 elementData

无参构造器

• 直接 this(10); ——> 调用 ( 单 ) 有参构造器 public Vector(int initialCapacity) 的方法：this(initialCapacity, 0); 再调用 ——> ( 双 ) 有参构造 public Vector(int initialCapacity, int capacityIncrement)，initialCapacity：10，capacityIncrement：0，返回
  • 其中 capacityIncrement 是在 grow 扩容的时候才会用到的，自定义的扩容大小：int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);

第一次添加

• add() 方法：

  • 修改加一

  • ensureCapacityHelper(minCapacity) 判断是否需要扩容

    if (minCapacity - elementData.length > 0)：grow(minCapacity)

    • 扩容时判断：无参的话就是扩容为旧容量两倍的大小
    • 其余似 ArrayList，也是 Arrays.copyOf()

  • elementData[elementCount++] = e; 添加新值，返回 true

第二次添加

• 依此类推

有参构造器

• 参照无参时执行构造器方法的代码部分
• 添加似无参，仅在扩容部分不同

LinkedList

• 维护的是一个双向链表
• 两个属性 first 和 last，分别指向首节点和尾节点
• 存储是用 Node 节点：item、next、prev

无参构造器

• 只有无参构造器

添加

• add() 添加

  • 调用方法 linkLast(e);

    • 方法里的 last 是每上一次添加的链尾 Node 节点，第一次添加时 last 为 null

    • l = last

    • newNode = 新值 ( prev，item，next ) 定下 prev、值

      final Node<E> newNode = new Node<>(l, e, null);

    • last = newNode

    • l 空则定链首 first = newNode ( 第一次才走此语句，即首尾都是第一次添加的 ) —— 只有第一次添加才执行

    • 否则就 l.next = newNode，定下 next，双向链表完成 —— 只有第一次添加不执行

    • size、modCount 皆加一

Set

HashSet

• 底层实际为 HashMap ( 只有开头构造器和 add() 是 HashSet 的内部类 )
• HashMap 底层为：数组 + 链表 + 红黑树

无参构造器

• 直接 map = new HashMap<>();，所以实际是就 HashMap
• new 后无参的 HashMap 定下了临界因子 loadFactor = 0.75
• 多个 Node 存进 table ( 有 entrySet )

添加

• add() 调用 map 的 put() 方法，PRESENT 空 Object 占位 ( HashSet 只存一组对象 )

  return map.put(e, PRESENT)==null;：只有返回 null 才添加成功

  • put() 里返回 putVal()，其中先计算 key 的哈希值

    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);：计算返回给 hash(key)，一起进入 putVal() 内

    • 另起分析核心代码 putVal()

• 表空否

  • 空的话就扩容：
  • resize() 给 16 大小，临界为 0.75 * 16 = 12，返给 table
  • n = 扩容后长度

• 继续执行，计算索引处空否 ( p = 存在 table 的索引 )

  • 为空的话就直接放进去 newNode

• 索引处不为空的话，辅助用：Node e

  1. 索引处 hash 等 && 同对象或同值否

     • true 就 e = p

  2. 红黑树否

     • e = ...

  3. 与索引处链首不等且不是树，索引处 next 开始死循环链表

     1. ( 链表内无同 k ) e = p.next 为 null ( 链尾 ) — 判断时更新 e

        p = newNode，此时 e == null

        if 单链大于 8，treeifyBin() ( 树化条件一达成 )

        break

     2. 链表内有同 e.hash 等 && 与 e 同对象或同值否，break

     3. p = e，每次循环把被比较的值存进 e

  4. e 空否 ( 都要经过，上述1. 2. 3. 最多只执行其一 )

     • 存 e.value ( 1. 是索引处链首值 3. 是旧值 )

     • ( 同 k ) 替换 v 为新值

     • return，后面不再执行

• 修改成功 + 1

• ++size > 临界值否

  • true，大了就 resize() 再扩容

• 返回 null ( 表示添加成功 )

LinkedHashSet

• 底层是一个 LinkedHashMap ( HashMap 的子类 )
• 维护了一个数组 + 双向链表 ( 跨表索引连接 )
• newNode(hash, key, value, null);

无参构造器

• LinkedHashSet里 的 super(16, .75f, true); —— HashSet 构造器，new LinkedHashMap 调 LinkedHashMap 构造器
• LinkedHashMap里 的 super(initialCapacity, loadFactor); —— HashMap 构造器

添加

• HashSet 的 add() 返回 map 的 put()

  return map.put(e, PRESENT)==null;

  • put() 里返回 putVal()，其中先计算 key 的哈希值
  • 后面都是同 HashSet 分析部分，参照文章上面所述

• 但是不同在 newNode 时此处会先存 Entry 中：( HashSet 里 newNode 只是单纯调用了 Node 构造器 ) LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);，然后调用 linkNodeLast(p);：

  • last = tail，第一次的话就全 null
    • 不是第一次的话，就是将上一个添加的值放 last 里
  • tail = p 把新值放链尾
  • last 空的话就表示第一次添加
    • head = p 定开头
  • 否则就表示非第一次
    • p.before = last
    • last.after = p
    • 上一个添加的值和新添加的值建立前后联系指向

• 即：在决定好新值 newNode 存放处前就已经和上一个添加的值双链表连接上了，便是完成了跨表索引的连接

  • head 开头，tail 结尾
  • before 链内指向上一个值，after 链内指向后一个

TreeSet

• 参照最后的 TreeMap
• 因为 TreeSet 底层就是 TreeMap

有参构造器

• 构造器里 this(new TreeMap<>(comparator));
• 在 TreeMap 的构造器里 this.comparator = comparator;
• add() 调用了 map 的 put()，用了占位 PRESENT，return m.put(e, PRESENT)==null;
  • put() 方法具体与本文最后的 TreeMap 部分一致
  • 返回 null 便是添加成功

Map

都是需要具体输入 k - v 元素

HashMap

无参构造器

• 存储同 HashSet

• 构造器仅定下了临界因子 loadFactor = 0.75

添加

• 具体详见 HashSet 从调用 map 的 put() 方法
• 只不过 Map 在 put() 方法时携参都是具体值 key、value，不会再用空 Object 占 value 的位置了，剩下的添加思路皆一致

Hashtable

• 底层就是 Entry 数组

无参构造器

• this(11, 0.75f);
• 重载的有参构造器里分 table 给 11 大小，并临界算得 8
• put() 内
  • 判断 value 不能为空，否则报错
  • Entry<?,?> tab[] = table;
  • int hash = key.hashCode(); 得 hash，然后再算出应在表的索引值 index
  • Entry<K,V> entry = (Entry<K,V>)tab[index]; 取出索引所在值 Entry
  • 同 key 就替换 value 值
  • addEntry()
    • 修改 +1
    • 若是已达临界值，便扩容 rehash();，机制是扩为旧容量的两倍加一
    • 没达临界就存新值到计算哈希值所得到的 table 表索引处
    • count++
  • 返回 null 完成存放

Properties

• 继承了 Hashtable
• 扩容和 put 添加都是 Hashtable 的内部类，过程一致

TreeMap

无参构造器：

• comparator = null;
  • TreeMap 内定义 private final Comparator<? super K> comparator;
• k 空就报错，Comparable<? super K> k = (Comparable<? super K>) key;
• cmp = k.compareTo(t.key);
• 无参默认 ASCII

有参使用匿名内部类：

• 在重写匿名内部类的方法时可以自行决定排序规则

• public TreeMap(Comparator<? super K> comparator) { this.comparator = comparator; }

• 第一次 put 添加

  • 新值存 root ( private transient Entry<K,V> root —— 之后也都是 Entry 形式存放 k-v )
  • compare(key，key)：没有接收，对后面没影响，只是检测是不是为空
  • 直接添加

• 第二次 put 添加

  • 接收匿名内部类方法 Comparator<? super K> cpr = comparator;
  • t = root ( 查找开始的根部，第二次的话就是第一次存的值 )
  • cpr != null，即有参重写过的话继续 ( 无参构造器的话就默认方式 ASCII 存新值 )
  • do
    • parent = t
    • cpr.compare 得知值放 parent 左 / 右 ( 只是定下 )
  • while，t == null 退出，即找到可以放进新值的空处
  • e 存新值
  • parent 左 / 右 = e ( 真正存放进去 )
  • fixAfterInsertion(e); 树化更新 root
  • 大小、修改次数 ++
  • 返回 null

• 第三次 put 添加

  • ...... ( 前面一致 )
  • cpr.compare 得知值放 parent 左 / 右 ( 只是定下 )
  • 若是 parent 左 / 右 != null，无法存进
    • 循环 parent = 左 / 右非空有值的 Entry
    • compare 得知值放 parent 左 / 右
    • 直到应放位置为空了，退出循环
  • e 存新值
  • parent 左 / 右 = e ( 真正存放进去 )
  • ...... ( 后面也都一致 )

• 依此类推，但注意，若是存放值 key 是 “ z、a、o ”，这种情况，会在真正存放完新值 o 时经过 fixAfterInsertion(e); 方法 ( 红黑树 ) 将 root 改为 o ( 处中间 )，即 o.left 为 a，o.right 为 z

  • 断 a - z 为 a - o - z