ArrayList

  • 数据结构为Array数组;
  • 通过索引下标实现了随机取值效率高;
  • 增删效率低,因为增加或删除需要移动数组中的元素;

Vector

  • 数据结构同于ArrayList
  • 底层比ArrayList多一个Synchronized锁;

  • CopyOnWriteArrayList

  • 数据结构与ArrayList相同,数组Array
  • 写时加锁复制:ReetrantLock保证线程安全,修改数组之前拷贝一份,操作新数组,并赋值给Array,旧数组丢弃;
  • 读取操作无锁,读取的是旧数组,写不会阻塞读,读写分离
  • 弱一致性:写操作会生成新的数组,读的数据就可能被修改,迭代器也是弱一致性,读的是快照;

LinkedList

  • 数据结构: 链表,维护一个内部类Node,元素以Node节点的Item属性存在,同时维护next和prev记录前驱后继的指针;
  • 双端队列,实现了Deque接口,支持首部和尾部存取元素;

ArrayBlockingQueue数组阻塞队列

  • 静态数组,容量固定必须指定长度,没有扩容机制,没有元素的下标位置null占位;
  • 锁:ReentrantLock,读取使用同一把锁,操作的是同一个数组对象;
  • 阻塞:

    notEmpty 出队: 队列count为0,无元素可取时,阻塞在该对象上;
    notFull 入队: 队列count为数组length,放不进元素时,阻塞在该队列上;

  • 入队 从队列首部开始添加元素,记录putIndex(到队尾时位置为0)唤醒notEmpty;
  • 出队 从队列首部取元素,记录takeIndex 唤醒notFull;
  • 先进先出,读写互相排斥;

LinkedBlockingQueue

  • 数据结构: 链表Node 容量可选,默认为Integer.MAX_VALUE,内部类Node存储元素;
  • 锁分离: 存取胡不排斥,操作是不同的Node对象;

    takeLock 取Node节点保证前驱后继不会乱;
    putLock 存Node节点保证前驱后继不会乱;

  • 阻塞同ArrayBlockingQueue
  • 入队: 队尾入队 记录last节点
  • 出队: 队首出队 记录head节点
  • 删除元素时两把锁一起加
  • 先进先出

HashMap

  • JDK1.7 HashMap

    数据结构 数组+链表
    存储下标 = hashcode % length

  • JDK1.8 HashMap

    数据结构 数组+单向链表+红黑树
    红黑树: 当链表高度达到8,数组长度达到64时采用红黑树;

ConcurrentHashMap

  • JDK1.7

    数据结构 Segement extend ReentrantLock + HashEntry(Node)