Java-API-容器-list、set、map

Java中的容器主要分为两类：

• Collection：存放列表的

• Map：存放键值对的

• 链表（Linked）

  • 有序
  • 增加或删除元素比较快
  • 通过存在元素中的指针联系到一起

• 数组（Array）

  • 有序
  • 找需要的元素比较快
  • 元素在内存中连续存放

• 哈希（Hash）

  • 无序

Collection

• Array：数组实现
• Linked：链表实现

Queue：队列接口

• Queue：队列接口
  • ArrayBlockingQueue
    • 线程安全的
    • 固定大小，有界阻塞队列
  • LinkedBlockingQueue
    • 线程安全的
    • 要想支持阻塞功能，队列的容量一定是固定的
    • 实现取数据和读数据的锁分离
  • PriorityQueue
    • 线程不安全的
    • 大小不固定，有界阻塞队列
  • PriorityBlockingQueue
    • 线程安全的
    • 大小不固定，有界阻塞队列
    • 可以根据任务自身的优先级顺序先后执行
  • LinkedTransferQueue
  • SynchronousQueue
    • 没有容量，每个插入操作都要等待一个相应的删除操作
    • 在线程池中使用该队列，通常要设置很大的maximumPoolSize值，否则很容易执行拒绝策略
• Deque：双端队列接口
  • LinkedBlockingDeque：
    • 线程安全的
    • 有界阻塞队列
  • ConcurrentLinkedDeque
    • 线程安全的

List：有序的列表

• ArrayList
  • Vector
    • 线程安全的
    • 内部的方法基本都是synchronized（不推荐使用）
    • 非常类似ArrayList
  • Stack
    • 继承自Vector
    • 实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。
  • CopyOnWriteArrayList
    • 线程安全的
    • 多运用在读多写少的场景
• LinkedList：实现了Deque接口
  • ConcurrentLinkedQueue
    • 线程安全的

Set：不重复的列表

• HashSet
  • 线程不安全的
  • 无序的
  • 哈希表实现
• TreeSet
  • 线程不安全的
  • 有序的，自然顺序，也可以指定比较函数
  • 通过TreeMap实现的，红黑树实现
• LinkedHashSet
  • 有序的
  • 也是一个hash表，但是同时维护了一个双链表来记录插入的顺序。基本方法的复杂度为O(1)。
• ConcurrentSkipListSet
  • 线程安全
  • 有序的
  • 通过ConcurrentSkipListMap实现的
• CopyOnWriteArraySet
  • 线程安全的

Map

• HashMap：线程不安全的，哈希表实现
  • WeakHashMap
    • 一种改进的HashMap，它对key实行“弱引用”，如果一个key不再被外部所引用，那么该key可以被GC回收。
  • LinkedHashMap
    • 有序的HashMap
    • 也是一个hash表，但是同时维护了一个双链表来记录插入的顺序。基本方法的复杂度为O(1)。
  • ConcurrentHashMap：
    • 线程安全的HashMap
    • 内部分成若干个小的HashMap，称之为段（SEGMENT），写操作对某个段加锁就行
• TreeMap：
  • 线程不安全的
  • 有序的，自然顺序，也可以指定比较函数
  • 红黑树实现
• HashTable
  • 线程安全的
  • 内部的方法基本都是synchronized（不推荐使用）
• ConcurrentSkipListMap
  • 有序的
  • 线程安全的
  • 内部是SkipList（跳表）结构，在理论上能够在O(log(n))时间内完成查找、插入、删除操作
  • 在非多线程的情况下，应当尽量使用TreeMap。
  • 此外对于并发性相对较低的并行程序可以使用Collections.synchronizedSortedMap将TreeMap进行包装，也可以提供较好的效率。
  • 对于高并发程序，应当使用ConcurrentSkipListMap，能够提供更高的并发度。