整体框架

image.png

接口

  • Collection（单一元素）

  • Map（Key-Value）

    子接口

  • Collection

    • List（有序、可重复）
    • Queue
      • Deque
    • Set（无序，不重复）
      • SortedSet

  • Map

    类

  • List

    • ArrayList（随机访问，扩容1.5倍）
    • Vector（扩容2倍）
      • Stack
    • LinkedList
  • Queue（offer队尾，poll/peek队头）
    • LinkedList（队列，可以存null）
    • Deque
      • ArrayDeque（栈常用，也可用于队列，不可以存null，头尾增删更高效，内存使用更高效）
    • PriorityQueue

  • Set（底层其实是对应的Map，数值放key，value放PRESENT）

    • HashSet（采用HashMap的key来存储元素，无序）
    • LinkedHashSet（保留插入顺序）
    • SortedSet
      • TreeSet（红黑树，有序，速度没hashset快）

        ArrayList

  • Collection接口成员

  • Object[] elementData
  • 随机访问快，遍历快（连续），增删效率低（大量数据的复制迁移）、线程不安全
  • 初始化可以设置数组大小，默认空数组
  • 初始扩容后默认10
  • 扩容 oldSize + (oldSize >> 1)，然后复制
  • ArrayList不适合做队列，数组适合
  • clone浅拷贝
  • 迭代方式：索引/元素循环/迭代器Iterator<> it = list.iterator()/it.hasNext()/it.next()/it.remove()[注意ConcurrentModificationException-failfast]
  • subList不能序列化
  • Arrays.toList()返回的是内部ArrayList->原来是什么类型就返回什么类型
  • elementData不用private可以简化内部类的访问

  • 允许null

    HashMap

  • Key-Value 数组+链表

  • 1.7Entry 1.8Node
  • 1.7头插法 1.8尾插
  • resize: capacity/loadFactor0.75，2倍，rehash(index=HashCode(key)&(len - 1))->头插rehash链表倒置造成环形链表，尾插扩容会保持原本顺序
  • 1.8红黑树(==8时候，因为根据泊松分布8概率小于百万分之一)
  • 初始化容量1<<4=16（手动传也最好是2的幂，实现均匀分布）
  • 重写equal（冲突时比较）和hashCode（保证相同对象返回hashCode一样）
  • 并发HashTable/Collections.concurrentMap(map)并大度低，用ConcurrentHashMap

  • HashTable/ConcurrentHashMap(fastsafe,不知道key是不存在还是为空)不允许键值为null，HashMap都可以

    ConcurrentHashMap

  • 1.7segment(内部类继承ReentrantLock)分段锁+HashEntry(volatile修饰value和next) get不需要加锁

  • 1.7 put过程：
    • hash(key)
    • hash找对应segment下标j（没有需要创建）(hash>>>segmentShift)&segmentShift
    • 通过hash计算对应segment的HashEntry数组下标 (tab.length-1)&hash
    • 找到合适位置插入元素（tryLock、scanAndLockForPut）
  • 1.7 get过程：
    • 先定位到Segment
    • 在定位到HashEntry
  • 1.7 size过程：
    • 先乐观认为统计过程中未变化，发生了重试2次还不成功，则加锁统计
  • 1.8 CAS+synchronized（Node(volatile修饰value和next) ），红黑树
  • 1.8 put过程：
    • 根据key计算hashcode
    • 判断是否需要初始化
    • key定位出Node如果是空则CAS尝试写入，失败自旋
    • hashcodeMOVED-1当前正在扩容，则协助扩容
    • 都不满足，则synchronized锁写入
    • 如果数量大于8，转红黑树
  • synchronized1.8之后优化了所以可以用
  • 1.8 get过程：
    • 计算出来hashcode寻址，如果在桶上则直接返回值
    • 如果是红黑树则按照树查
    • 都不满足则按照链表遍历

  • 1.8 size过程：

    • 各自CounterCell

      PriorityQueue

  • heap，本质是数组

  • parent=(x-1)/2; leftchild=x*2+1; rightchild=leftchild+1

  • shiftUp(offer先放最后然后往上浮)/shiftDown(poll拿最后一个放到首位后往下沉)/heapify(从最后一个非叶子节点往前开始shiftDown，O(n))

    并发容器

    java.util.concurrent.*，都是安全失败(failsafe)

  • ConcurrentHashMap
    putIfAbset/replace都是原子操作

  • CopyOnWriteArrayList/CopyOnWriteArraySet 写时复制

  • CountDownLatch

    同步容器

  • Vector：ArrayList的同步版本，所有方法加上了锁，并发效率低，但是复合操作无法保证线程安全

  • Stack
  • Hashtable
  • Collections静态工厂方法创建的类 Collections.synchronizedList()