集合 - 图1

Collection

List

  1. 有序的；
  2. 可重复的； | 类 | 底层结构 | 增删的效率 | 改查的效率 | | —- | —- | —- | —- | | Vactor | 可变数组 | 较低 | 较低 | | ArrayList | 可变数组 | 较中 | 较高 | | LinkdList | 双向链表 | 较高 | 较低 |

Vactor

  1. Vactor是线程同步的，通过synchronized关键字实现线程安全；

  2. 若创建对象时不指定大小第一次扩容为10，后续扩容为原大小的2倍；

    ArrayList

  3. ArrayList是线程不安全的；

  4. 每次添加数据时，进行一次扩容检测，判断是否需要扩容，如果扩容则为原大小的1.5倍。
  5. 若创建对象时不指定大小，原大小为0则扩容为默认大小10；
  6. 创建数组时，可指定大小，后续扩容按照指定大小进行扩容；

  7. 扩容时会进行修改次数记录，多线程同时修改一个ArrayList的数组元素大小时，会抛出多线程操作异常；

    LinkdList

  8. LinkdList是线程不安全的；

  9. 底层实现了双向链表和双端队列特点；

image.png

Set

  1. 无序的

  2. 不允许重复

    HashSet

  3. 底层是HashMap，内部有一个map是HashMap对象，key是传入的对象，value是一个固定的占位对象；

  4. 内部顺序是固定的，但与添加的顺序无关；

  5. 可放一个null，不能放重复值（根据hash()和equals()方法判断是否相同）；

    TreeSet

  6. 底层是TreeMap

  7. 无参构造时无序，可通过有参构造函数传入指定排序规则的比较器实现有序；

    Map

    HashMap

  8. HashMap是线程不安全的；

  9. 数组加链表实现；
  10. jdk8中，当一条链表深度达到默认8，整个数组长度达到默认64，会变为红黑树结构，所有链表深度小于6时转为链表；
  11. 数组的扩容是按原大小的两倍；

image.png

  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.     if ((tab = table) == null || (n = tab.length) == 0)
  5.         n = (tab = resize()).length;//当tab为空则创建，长度为16
  6.     if ((p = tab[i = (n - 1) & hash]) == null)
  7.         tab[i] = newNode(hash, key, value, null);//hash算出的tab下标值为空，存放value
  8.     else {
  9.         Node<K,V> e; K k;
  10.         if (p.hash == hash &&
  11.             ((k = p.key) == key || (key != null && key.equals(k))))
  12.             e = p;//hashcode和equals都为ture，覆盖原来的值
  13.         else if (p instanceof TreeNode)//红黑树结构的put
  14.             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  15.         else {
  16.             for (int binCount = 0; ; ++binCount) {//遍历链表看是否有相同的key
  17.                 if ((e = p.next) == null) {
  18.                     p.next = newNode(hash, key, value, null);//没找到相同则存入链尾
  19.                     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
  20.                         treeifyBin(tab, hash);//扩容或tab长64链表长8则转红黑树
  21.                     break;
  22.                 }
  23.                 if (e.hash == hash &&
  24.                     ((k = e.key) == key || (key != null && key.equals(k))))
  25.                     break;
  26.                 p = e;//找到相同值覆盖value
  27.             }
  28.         }
  29.         if (e != null) { // existing mapping for key
  30.             V oldValue = e.value;
  31.             if (!onlyIfAbsent || oldValue == null)
  32.                 e.value = value;
  33.             afterNodeAccess(e);//LinkedHashMap的扩展方法
  34.             return oldValue;//存在相同的key，新值覆盖了原值，返回原值
  35.         }
  36.     }
  37.     ++modCount;
  38.     if (++size > threshold)
  39.         resize();//当tab长度大于阈值则扩容，总长度16则阈值为16*0.75=12，扩容为两倍
  40.     afterNodeInsertion(evict);//LinkedHashMap的扩展方法
  41.     return null;//key和value添加成功，返回null
  42.     }

TreeMap

  1. 空参构造无序，有参构造传入比较器实现有序；

  2. 底层是红黑树结构；

    HashTable

  3. HashTable是线程安全的，使用synchronized关键字；

  4. key和value都不允许为null，否则会抛出空指针异常；

  5. 数组初始大小为11，阈值为8，扩容为2倍+1；

    ConcurrentHashMap

  6. ConcurrentHashMap是线程安全的；

  7. 底层是数组加链表的结构，Segment数组加HashEntry数组，HashEntry数组中的每一个下标形成链表；
  8. 内部类Segment实现了ReentrantLock接口，通过在添加数据时tryLock和unLock实现线程安全；

image.png