Java集合

1.ArrayList和LinkedList

  • 是否线程安全：两者都不是线程安全的
  • 底层数据结构：Object数组，双向链表
  • 是否支持快速随机访问
  • 插入删除元素速度
  • 空间占用：ArrayList尾部会预留一定的容量

RandomAccess接口

  1. public interface RandomAccess {
  2. }

RandomAccess是一个标志性接口，没有任何定义。标志实现这个接口的类具有随机访问的功能。

在binartSearch()方法中，会判断传入的list是否RandomAccess实现

2.ArrayList,Vectors,CopyOnWriteArrayList

CopyOnWriteArrayList

  • 实现了List接口
  • 内部持有一个ReentrantLock lock = new ReentrantLock();
  • 底层是用volatile transient声明的数组 array
  • 读写分离，写时复制出一个新的数组，完成插入、修改或者移除操作后将新数组赋值给array

增删改都需要获得锁，并且锁只有一把，而读操作不需要获得锁，支持并发。

CopyOnWriteArrayList为什么并发安全且性能比Vector好？

我知道Vector是增删改查方法都加了synchronized，保证同步，但是每个方法执行的时候都要去获得锁，性能就会大大下降，而CopyOnWriteArrayList 只是在增删改上加锁，但是读不加锁，在读方面的性能就好于Vector，CopyOnWriteArrayList支持读多写少的并发情况。

3.HashSet,CopyOnWriteArraySet

HashSet

  • HashSet实际上就是HashMap，只是将value设置成null
  • HashSet中的元素不重复的
  • HashSet中的元素是无序的

CopyOnWriteArraySet

HashSet对应的并发类为什么叫CopyOnWriteArraySet，而不是叫CopyOnWriteHashSet呢？
  1. public class CopyOnWriteArraySet<E> extends AbstractSet<E>
  2.         implements java.io.Serializable {
  3.     private static final long serialVersionUID = 5457747651344034263L;
  5.     private final CopyOnWriteArrayList<E> al;
  7.     /**
  8.      * Creates an empty set.
  9.      */
  10.     public CopyOnWriteArraySet() {
  11.         al = new CopyOnWriteArrayList<E>();
  12.     }
  13.     ...
  14. }

CopyOnWriteArraySet的底层存储结构竟然是CopyOnWriteArrayList，那么我们就可以知道它的名字的由来了，并且知道它支持并发的原理跟CopyOnWriteArrayList是一样的。

4.ConsurrentHashMap，HashMap，Hashtable

HashTable

  • 底层数组+链表实现，无论key还是value都不能为null，线程安全，实现线程安全的方式是在修改数据时锁住整个HashTable，效率低。
  • 初始size为11，扩容：newsize = olesize*2+1
  • 计算index的方法：index = (hash & 0x7FFFFFFF) % tab.length

ConcurrentHashMap

  • 在JDK1.7的时候，ConcurrentHashMap（分段锁） 对整个桶 数组进⾏了分割分段(Segment)，每⼀把锁只锁容器其中⼀部分数据，多线程访问容器⾥不同数 据段的数据，就不会存在锁竞争，提⾼并发访问率。
  • 到了 JDK1.8 的时候已经摒弃了Segment的 概念，⽽是直接⽤ Node 数组+链表+红⿊树的数据结构来实现，并发控制使⽤ synchronized 和 CAS 来操作，每次对一个桶上锁。
  • synchronized只锁定当前链表或红⿊⼆叉树的⾸节点，这样只要hash不冲突，就不会产⽣并发，效率⼜ 提升N倍

5.HashMap

参数

  • DEFAULT_INITIAL_CAPACITY = 1<<4 // 缺省容量
  • MAXIMUM_CAPACITY = 1 << 30 // 最大容量
  • DEFAULT_LOAD_FACTOR = 0.75 // 缺省装载因子
  • TREEIFY_THRESHOLD = 8 // 将链表变成红黑树的阈值
  • UNTREEIFY_THRESHOLD = 6 // 将红黑树变回链表的阈值
  • MIN_TREEIFY_CAPACITY = 64 // 会转换成红黑树的最小容量，就是说如果map的容量低于64， 就算一个桶里面数量大于8也不会转换成红黑树
  • size // 数量
  • modCount // modify的次数
  • threshold // 扩容阈值，超过这个阈值，将扩容
  • loadFactor // 装在因子

Node

  • hash
  • key
  • value
  • next

注意点

  • 在put的时候，会对key进行一个hash，但并不是直接将key的hashCode进行hash，而需要进行一步处理
  1.   // 注意在hash过程中，会进处理。(h = key.hashCode()) ^ (h >>> 16); 相当于在散列过程中同时考虑高16位的信息
  2.   static final int hash(Object key) {
  3.       int h;
  4.       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  5.   }

  • jdk 1.8 与 1.7 的区别 ： Entry-> Node, 添加红黑树, 头插改成尾插

    头插改成尾插的原因是：为了防止resize过程中形成循环链表

  • 设置成Java集合 - 图1的目的

    1. 在hash的过程中，需要对size取模，而如果size的长度是Java集合 - 图2，则可通过Java集合 - 图3的计算方法得到。
    2. 创建Map过程中，初始的size不一定是Java集合 - 图4, 如果不是，则会进行处理：
  1.   // 这是java11中的写法，与java8中有所不同
  2.   static final int tableSizeFor(int cap) {
  3.      int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
  4.      return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
  5.   }
  1. 3. resize过程中需要rehash, 因为扩容成原来的两倍，所以原本桶中的Node有两种rehash可能：留在原桶;rehash到index+oldCap的位置，而判断的方法只需要对于原来的hash值在进行一次hash，&oldCap即可：举个例子，如果oldCap=8 (oX1000)，则扩容后是16，原本在桶7位置的只需要判断是放在7还是放在15，所以只需要将hash &= oldCap 即可。
  • key为null时

    key如果为null，会默认将hash为0，hash后放在桶0中。 注意：在ConcurrentHashMap中是不能插入key为null的，ConcurrentHashMap不能put null 是因为 无法分辨是key没找到的null还是有key值为null，这在多线程里面是模糊不清的，所以压根就不让put null。

6.如何选用集合

主要根据集合的特点来选⽤，⽐如我们需要根据键值获取到元素值时就选⽤Map接⼝下的集合，需要排序时选择TreeMap,不需要排序时就选择HashMap,需要保证线程安全就选⽤ConcurrentHashMap.当我们只 需要存放元素值时，就选择实现Collection接⼝的集合，需要保证元素唯⼀时选择实现Set接⼝的集合 ⽐如TreeSet或HashSet，不需要就选择实现List接⼝的⽐如ArrayList或LinkedList，然后再根据实现 这些接⼝的集合的特点来选⽤。