Java 容器

Java 容器

单列集合
顶层接口
  Iterable 定义了用于迭代器循环的接口
  Collection 定义的一套统一单列集合的接口。其中有isEmpty、add、remove、size等常用方法
   List 接口 继承重写了Collection接口的一些函数，同时增加了一些如 sort、indexOf等函数。 其允许重复元素的一种有序的集合。
   Set 接口 继承Collection，重写部分函数。 该集合不包含重复元素，不保证插入顺序的访问。
   Queue 接口 定义队列一种先进先出的数据结构的接口，继承Collection 接口，增加了 poll、peek、element等方法。

List 实现类
顺序存储，线性结构的单列集合
    ArrayList
    非线程安全的，内部基于数组实现。
    扩容操作：默认空数组，第一次添加单条数据时，初始化大小为10的数组，一次扩容1.5倍。若用addAll 添加数据，超出1.5倍按实际大小扩容，不足按1.5倍扩。
    其中 插入扩容移除操作时，涉及到对数组的拷贝，较影响性能。
    LinkedList
    非线程安全的，内部基于双向链表实现。
    链式存储结构，将不连续的内存连续起来，方便允许插入和删除，只需要改变指针指向的位置。不允许随意存取。
    Vector
    方法前用synchronized关键字保证线程安全，内部基于数组实现。
    扩容操作：默认初始化一个大小为10，扩容容量为0的数组。
    若扩容容量小于等于0，一次扩容2倍，否则按扩容容量扩容。
        Stack 栈
        继承自Vector，增加入栈（向数组尾部加入数据），出栈（取出最后一条数据，并移除）操作。

Set 实现类
    HashSet
    内部用HashMap实现，添加的元素作为key，value为固定的Object。
    LinkedHashSet
    继承自HashSet，内部用LinkedHashMap实现。保证有序访问。
    TreeSet
    内部用TreeMap实现，添加的元素作为key，value为固定的Object。

Queue 实现类
    AbstractQueue
        PriorityQueue 非阻塞队列
        根据比较器排序的优先级队列，内部用数组实现。

        扩容机制：默认初始化一个大小为11的数组，若队列大小小于64，一次扩容+2，否则1.5倍扩。
        入队时，保证队首数据是最小的，根据siftUp方法向上筛选。出队时，取出队首数据，根据siftDown方法向下筛选，选出新的队首数据。
        ConcurrentLinkedQueue 非阻塞队列
        基于单链表实现，链表用volatile修饰。CAS机制保证线程安全。
        CAS: compare and swap 比较再交换。当预期值相同时，再修改为新值。原子操作。
    BlockingQueue 阻塞队列
        ArrayBlockingQueue
        有界阻塞队列，内部用数组实现，必须指定数组大小。通过ReentrantLock实现线程安全访问，Condition实现等待阻塞机制。
        LinkedBlockingQueue
        内部基于单链表实现，默认容量为Integer.MAX_VALUE。
        PriorityBlockingQueue
        内部基于数组实现，有优先级的无界阻塞队列。内部实现与扩容机制跟PriorityQueue差不多。
        SynchronousQueue
        内部只有一个元素的队列。
        DelayQueue
        内部基于PriorityQueue实现，根据时间排序的队列。take取数据时，若未到出队时间，则阻塞。
    Deque
    定义双端队列接口 既能从头部添加又能从尾部添加，也可以从两端取。
        LinkedList
        非线程安全的非阻塞式双端队列
        LinkedBlockingDeque
        阻塞式双端队列

键值对集合
顶层接口 Map 定义了一套键值对存储集合的接口。包含size、put、get、remvoe等常用方法
实现类:

HashMap
内部用数组+链表的方式实现。指定的数组大小会计算为接近的2的幂次方大小，默认大小为16，阈值为0.75倍。
添加数据超过阈值一次扩容2倍，同时阈值*2.
hash算法：key的hash值高16位与低16位异或，以保留全部位的特性，减少hash冲突。
扩容后，重新计算链表所在下标位置，重新赋值。（原链表下标+(cap&hash)）
当一个链表长度超过8时，会生成一个红黑树（根据key值比较排序），加速查找和插入。当结点因为移除分裂操作少于6个时，消除树结构。
红黑树：一种自平衡的二叉树。每个节点都带有红色或黑色属性的二叉查找树。当对红黑树进行插入和删除操作时，为了保证树的性质，会对树进行旋转(左旋，右旋);
LinkedHashMap
继承自HashMap，用LinkedHashMapEntry作为链表的节点，这是一个双向链表。同时内部维护head以及tail节点，以保证顺序访问。默认以插入顺序。
accessOrder 设置为true，最近最少访问顺序，再get方法时，将得到的元素移动至尾节点。
TreeMap
内部用红黑树实现，以保证key值的排序方式。
HashTable
数组+链表实现，通过锁关键字保证线程安全。

注 保证线程安全的集合 可以通过Collections.synchronized 方法达到，其返回一个线程安全的集合。