分类

Java集合的底层原理（List、Set、Map） - 图1

Collection(接口)

List(接口)

List中:

  1. 元素有序，即添加顺序和取出顺序一致
  2. 元素可重复，且可为null
  3. 每个元素都有对应的顺序索引

    Vector

    1. 实现方式：Object类型的数组

    ![44G13W@PI{6V3{9NZV7W}M.png

    2. 源码

    （1）线程安全的，操作方法带synchronized
    举例：
    ]`I(YMDW06G2CEKL$GSYJ@W.png
    （2）扩容机制
    如果是无参，默认10，满了按2倍扩容；如果指定大小，每次按2倍扩容

  • 无参构造器

    1. public static void main(String[] args) {
    2.   Vector vector = new Vector();
    3.   for (int i = 0; i < 10; i++) {
    4.       vector.add(i);
    5.   }
    6.   vector.add(100);
    7. }
    • 第2行：无参构造器创建Vector，给默认值10，再调用有参构造器

FV(F6SIZJCQYTC5I8D8}K{U.pngB04M$5ZS(G4A)(7MDP0Z_N6.png

  • 第4行：添加数据到集合

![PTZ[BD%C)IUYZH$V09GLCL.png

  • 第6行：这一次添加需要扩容

QQ截图20220405201553.png
32QM5D4(_)JI%%HB9G`9{KO.png
QQ截图20220405202538.png

  • 有参构造器

    1. Vector vector = new Vector(8);
    • 创建

{38SPNS90]~L96(J8(6)D1G.png(BR$@VJ`~TL6UIJ3GUHS0Z5.png

  • 扩容

MW@T0E41M{7]F01L}FNBS57.png

ArrayList

1. 实现方式：数组

2. 源码

（1）底层维护一个Object类型的数组elementData
  1. /**
  2.     * The array buffer into which the elements of the ArrayList are stored.
  3.     * The capacity of the ArrayList is the length of this array buffer. Any
  4.     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
  5.     * will be expanded to DEFAULT_CAPACITY when the first element is added.
  6. */
  7. transient Object[] elementData; // non-private to simplify nested class access
  9. /**
  10.     * The size of the ArrayList (the number of elements it contains).
  11.     *
  12.     * @serial
  13. */
  14. private int size;

transient表示该属性不会被序列化

（2）构造器

![B7BUC%A39)JPZ6JL(A}6%B.png

（3）扩容机制

当创建ArrayList对象时，如果使用无参构造器，初始elementData容量为0，第1次添加，扩容为10，再次扩容，扩容为elementDate的1.5倍
如果使用的是指定大小的构造器（ArrayList(int)），初始elementDate容量为指定大小，如果需要扩容，则直接扩容elementData为1.5倍

  • 无参构造器

    1. public class ArrayListSource {
    2.   public static void main(String[] args) { 
    3.       //使用无参构造器创建ArrayList对象
    4.       ArrayList list = new ArrayList();
    5.       //使用for给list集合添加 1-10数据
    6.       for (int i = 1; i <= 10; i++) {
    7.           list.add(i);
    8.       }
    9.       //使用for给list集合添加 11-15数据
    10.       for (int i = 11; i <= 15; i++) {
    11.           list.add(i);
    12.       }
    13.   }
    14. }
    • 第4行：使用无参构造器创建ArrayList对象，创建了一个空的elementData

QQ截图20220405173625.png![`AS)E(NJ}9TDVL])6{CYQ2.png

  • 第6行：i = 1时，即第一次添加元素，执行add方法

}~KG_S4BMH(K{G3_~E3W}$9.png
20220405182142.png
实际的扩容方法grow
QQ截图20220405183630.png

  • 第6行：i=11，会进行第2次扩容，前面的流程都跟第1次一样，grow方法：

第2次及以后，都按1.5倍扩容
QQ截图20220405184018.png

  • 有参构造器

    1. ArrayList list = new ArrayList(8);
    • 第一次添加

QQ截图20220405194358.png

  • 之后扩容按1.5倍扩容
    （4）线程不安全，执行效率高
    如下面的add方法，没有进行线程安全的设置
    QQ截图20220405171011.png

    LinkedList

    1. LinkedList底层实现了双向链表

    2. 源码

    （1）底层维护了一个双向链表
    size是链表大小，first和last分别指向首节点和尾节点
    D]DO9V$3LG%9C`TUQSX{HOX.png
    （2）创建
    1. LinkedList linkedList = new LinkedList();
    创建了空的LinkedList,first和last都是null
    %4H`M87%DINIKVGGZUM`G)7.png$8B2PEH@54EJ7W3}NBG5I)V.png
    （3）添加，同理，删除节点等都是双向链表的操作
    W@OJ}`9}~8CT302DQ@`8AKN.png
    将新节点加到双向链表尾部
    KW)7`GIZN9@OA1BUCVC0~SW.png
    （4）线程不安全

    Set(接口)

    Set中：
  1. 元素无序
  2. 不允许有重复元素，最多有一个null
  3. 不能用索引

    TreeSet

    1. 底层是TreeMap

    2. 特点：可以排序

    （1）使用无参构造器，是无序的
    （2）使用传入比较器的构造器，进行指定规则排序
    ![%_06X~%8L(NFZUI08AAZAX.png
    举例：按字符串大小比较
    1. TreeSet treeSet = new TreeSet(new Comparator() {
    2.          @Override
    3.          public int compare(Object o1, Object o2) {
    4.              //下面 调用String的 compareTo方法进行字符串大小比较
    5.              return ((String) o2).compareTo((String) o1); 
    6.          }
    7.      });
    628K_])SHM)GG02KI](CO]Y.png
    OEMJ}0J~GX{I7FQRV5N30~X.png

    HashSet

    1. 底层实际上是HashMap

    2. 源码

    （1）创建
    1. Set hashSet = new HashSet();
    0S$Q@4Z}VSH~4__}W63ZP_4.png
    （2）HashSet的底层是HashMap，HashMap底层是数组+链表+红黑树
  • 添加一个元素时，先得到hash值，再转成索引
  • 找到存储数据表table，看这个索引位置有没有存放元素
  • 如果没有存放元素，直接加入
  • 如果有，调用equals比较，如果相同，放弃添加；如果不相同，添加到最后

  • 一条链表的元素个数达到TREEIFY_THRESHOLD(默认8)且table大小>=MIN_TREEIFY_CAPACITY(默认64)会进行树化，否则对table扩容

    1. hashSet.add("java");

    7LG8GYS2L6~9C%4CYXQXBNW.png
    PRESENT作为Map中所有的值，起占位的作用
    ![]B)HY~9RMWUTD[B5N7B%[I.png
    执行put方法，key是传入的字符串”java”，value是PRESENT
    ![N0[ZGC@KT$IBTUHK~RZOGY.png
    得到key对应的hash值，hash值不是hashCode，而是(h = key.hashCode()) ^ (h >>> 16)
    81KLK8UP%{K6(2J}{4J5EH8.png
    执行putVal方法，源码如下：

    1. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
    2.                  boolean evict) {
    3.       Node<K,V>[] tab; Node<K,V> p; int n, i;
    4.       // table是HashMap的一个属性，类型为Node[]
    5.       // 如果当前的table为空或大小为0，第一次扩容
    6.       if ((tab = table) == null || (n = tab.length) == 0) 
    7.           n = (tab = resize()).length; // 扩到16
    8.       // 根据传入的hash计算该key应该存放到table表的哪个索引位置，并把这个位置的对象赋给p
    9.       // 如果这个位置为null，就创建一个Node把key存在这个位置
    10.       if ((p = tab[i = (n - 1) & hash]) == null)
    11.           tab[i] = newNode(hash, key, value, null);
    12.       else {
    13.           Node<K,V> e; K k;
    14.           // 如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样
    15.           // 并且满足以下两个条件之一就不能加入：
    16.           // 1. 准备加入的key和当前位置结点（p）的key是同一个对象
    17.           // 2. k不为null，不是同一个对象但是经过equals判断内容相同
    18.           if (p.hash == hash &&
    19.               ((k = p.key) == key || (key != null && key.equals(k))))
    20.               e = p;
    21.           // 再判断是否是一颗红黑树，如果是，就调用putTreeVal添加
    22.           else if (p instanceof TreeNode)
    23.               e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    24.           else {
    25.               // 如果table对应索引位置是一个链表，就使用for循环比较
    26.               for (int binCount = 0; ; ++binCount) {
    27.                   // 如果比较到最后，都没有相同的，就将节点加到链表最后
    28.                   if ((e = p.next) == null) {
    29.                       p.next = newNode(hash, key, value, null);
    30.                       // 添加到链表后，判断是否达到8个节点，到了8个就调用treeifyBin进行树化
    31.                       // 但再在treeifyBin方法中
    32.                       /*
    33.                           static final int MIN_TREEIFY_CAPACITY = 64;
    34.                           if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    35.                               resize();
    36.                       */
    37.                       // 表的大小不到64，暂时不进行树化，先扩容
    38.                       if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    39.                           treeifyBin(tab, hash);
    40.                       break;
    41.                   }
    42.                   // 比较过程中，如果有相同，不能加入，直接break
    43.                   if (e.hash == hash &&
    44.                       ((k = e.key) == key || (key != null && key.equals(k))))
    45.                       break;
    46.                   p = e;
    47.               }
    48.           }
    49.           // 失败情况
    50.           if (e != null) { // existing mapping for key
    51.               V oldValue = e.value;
    52.               if (!onlyIfAbsent || oldValue == null)
    53.                   e.value = value;
    54.               afterNodeAccess(e);
    55.               return oldValue;
    56.           }
    57.       }
    58.       ++modCount;
    59.       // threshold，在resize里改变的，第一次是12
    60.       // 大于临界值，就要扩容
    61.       if (++size > threshold)
    62.           resize();
    63.       afterNodeInsertion(evict);// 空的，留着给HashMap子类
    64.       return null;
    65.   }

    threshold：
    ![8QH8[$O59WC(13U%AZ5`BD.png

    （3）扩容

  • 第一次添加，table数组扩容到16，临界值(threshold=12)=16*加载因子(loadFactor=0.75)

  • 当table数组到达临界值12，就会扩容到162=32，新的临界值为320.75=24
  • 一条链表的元素个数达到TREEIFY_THRESHOLD(默认8)且table大小>=MIN_TREEIFY_CAPACITY(默认64)会进行树化，否则对table扩容
  • 与临界值比较，每向hashSet增加一个Node，就是增加了一个（不是table表被用了threshold个）。putVal方法：

EAU15{WC4C$BL~A)H5B`7`N.png

LinkedHashSet

1. 底层是一个LinkedHashMap，维护了一个数组+双向链表

双向链表维护元素的次序，确保插入顺序和遍历顺序一致

2. 源码

（1）LinkedHashMap维护了一个hash表和双向链表，LinkedHashMap有head和tail属性，每一个节点有before和after属性

![3AC~B$X]{Y0CVH2[[TTA2.png](https://cdn.nlark.com/yuque/0/2022/png/26273875/1649213127270-6addd615-94dd-4a94-b843-83cbe1d778e2.png#clientId=u62ef936c-a352-4&crop=0&crop=0&crop=1&crop=1&from=ui&id=u9f967181&name=3AC~B%24%60X%5D%7BY0CVH2%5B%5B%60TTA2.png&originHeight=186&originWidth=463&originalType=binary&ratio=1&rotation=0&showTitle=false&size=19886&status=done&style=none&taskId=ub6747df4-0a67-4377-b31c-0dac5444ddd&title=)
Java集合的底层原理（List、Set、Map） - 图29

（2）添加

HashSet的子类，因此操作与添加和扩容等操作与HashSet一样，只是变成了双向链表
添加一个元素时，先求hash值，得到索引，确定在table中的位置，然后再把元素加入双向链表。如果已经存在，不添加
第一次添加时，直接将数组table 扩容到16，存放的结点类型是LinkedHashMap$Entry
![`JKSWKH(2YWD~HBFQL@S0O.png
![S~VQJ]G$I{U[S0A5_CP~_W.png](https://cdn.nlark.com/yuque/0/2022/png/26273875/1649214615570-4d3d8e3d-7479-48f4-89e3-f96148837290.png#clientId=u62ef936c-a352-4&crop=0&crop=0&crop=1&crop=1&from=ui&id=u94f7dc4d&name=S~VQJ%5DG%24I%7BU%5BS0A5_CP~_W.png&originHeight=167&originWidth=969&originalType=binary&ratio=1&rotation=0&showTitle=false&size=26589&status=done&style=none&taskId=u926d6ee0-c01c-44fb-b580-4db25805cac&title=)
添加时还是HashMap的add
![$Q_M0C}KH8TU82}4EPR7T5.png

Map(接口)

  1. 保存具有映射关系的数据key-value

  2. key不允许重复，value可以重复。有相同key时，替换value

    Hashtable

    1. 底层数组 Hashtable$Entry[]

    4L]JS521MN~DD]U~)0FOS_J.png
    %I2`8JOKO_]$L3)0MD5FIYC.png
    由put方法， Hashtable对象的key、value值均不可为null。

    2. 源码

    （1）线程安全的

    （2）再次插入key相同的，value会覆盖

    （3）初始化大小为11，临界值threshold=11*0.75=8

    H2}YGP$UK0L97UCD_Y6SFJH.png

    （4）扩容

    按旧容量*2+1扩
    addEntry方法：
    BJ3FCU5ZI]TGIJ(_CD1}G4R.png![@$FC4306_KCQ7WDB`05R20.png

    Properties

    继承Hashtable，用于从xx.properties文件中加载数据到Properties类对象，进行读取和修改

    HashMap

    1. 底层是数组+链表+红黑树

    2. 源码

    （1） 一对k-v存放在一个HashMap$Node中，HashMap的putVal中：

    ![{6]P5K0_E7X(CY@ZBJZNFL.png
    4PR1J}O98OO)KLEI`F$YZMJ.pngXC82$10%CT]_WV_M17{LS94.png
    为了方便遍历，还会创建EntrySet集合 ，该集合存放的元素的类型 Entry, 而一个Entry对象就有k,v EntrySet> 即： transient Set> entrySet;
    entrySet 中， 定义的类型是 Map.Entry ，但是实际上存放的是HashMap$Node：
    static class Node implements Map.Entry
    Map.Entry有方法K getKey(); V getValue();

    （2）再次添加相同的key，value会覆盖

    putVal方法遇到相同的key：
    F`B3{(BO9(0$HCI5GO@I%UL.png

    （3）扩容

    与HashSet部分的源码相同

    • HashMap底层维护了Node类型的数组table，默认为null
    • 创建对象时，加载因子初始化为0.75
    • 添加k-v时，通过k的哈希值得到在table的索引，判断该索引处是否有元素，如果没有元素直接添加，如果有元素，继续判断该元素的k和准备加入的k是否相等，相等，直接替换v，不相等，判断是树结构还是链表结构，做出相应处理。添加时容量不够，扩容
    • 第一次添加，table扩容至16，临界值为12
    • 之后再扩容，table扩容至2倍32，临界值24
    • 如果一条链表的元素个数超过EREEIFY_THRESHOLD(默认8)，且table>=MIN_TREEIFY_CAPACITY(默认64)，树化（红黑树）

      （4）线程不安全的

      LinkedHashMap

      见LinkedHashSet部分

      TreeMap

      见TreeSet部分