【搞定Java集合框架】第1篇：Java 集合框架梳理

短命女 2022-04-22 17:42 174阅读 0赞

本文参考自：[https://blog.csdn.net/a724888/article/details/80215706][https_blog.csdn.net_a724888_article_details_80215706]，部分内容为自己原创。

本文介绍了Java集合类的基本框架，接口结构以及部分源码分析，并且通过自己实现一些集合类来更好地剖析Java集合类的整体结构。

本文只是对集合类框架进行一个大概的梳理，毕竟集合框架中包含的类太多了，一篇文章不可能讲完，这里先开一个头，对整体框架有一个清晰认识之后，再去探索各个接口实现类的奥秘。

后面会专门地写几篇关于集合类的文章，分别介绍一下List，Map，Set以及Stack等等这些接口的实现类，敬请期待。

具体代码在我的GitHub中可以找到：[https://github.com/h2pl/MyTech][https_github.com_h2pl_MyTech]

在编写Java程序中，我们最常用的除了八种基本数据类型、String对象外还有一个集合类，在我们的的程序中到处充斥着集合类的身影！

## **本文目录：** ##

**1、Java 集合框架概览**

**2、Collection 接口**

**3、List 接口**

**3.2、LinkedList**

**4、Set 接口**

**4、Map**

**5、Queue**

**6、转发文章：关于 Java 集合的小抄**

**7、异同点**

**8、对集合的选择**

--------------------

## 1、Java 集合框架概览 ##

Java中集合大家族的成员实在是太丰富了，有常用的ArrayList、HashMap、HashSet，也有不常用的Stack、Queue，有线程安全的Vector、HashTable，也有线程不安全的LinkedList、TreeMap等等！

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70][]

上面的图展示了整个集合大家族的成员以及他们之间的关系。下面就上面的各个接口、基类做一些简单的介绍(主要介绍各个集合的特点。区别)。

下面几张图更清晰地介绍了结合类接口间的关系：

*  **Collections 和 Collection、Arrays 和 Collections：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1][]

*  **Collection 子接口：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 2][]

*  ** map 的实现类：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 3][]

--------------------

## 2、Collection 接口 ##

Collection 接口是最基本的集合接口，它不提供直接的实现，Java SDK提供的类都是继承自Collection的“子接口”。如：List 和 Set。Collection 所代表的是一种规则，它所包含的元素都必须遵循一条或者多条规则。如有些允许重复而有些则不能重复、有些必须要按照顺序插入，而有些则是散列，有些支持排序但是有些则不支持。

我们先来看下 Collection 接口的源码（Java7）：

package java.util;
    
    public interface Collection<E> extends Iterable<E> {
        // 集合中元素的个数
        int size();
    
        // 判断集合是否为空
        boolean isEmpty();
    
        // 判断集合中是否包括o元素
        boolean contains(Object o);
    
        // 迭代遍历集合
        Iterator<E> iterator();
    
        // 将集合转换为数组
        Object[] toArray();
    
        // 支持泛型：将集合转换为数组
        <T> T[] toArray(T[] a);
    
        // 向集合中添加一个元素e
        boolean add(E e);
    
        // 从集合中移除元素o
        boolean remove(Object o);
    
        // 判断当前集合中是否包含另外一个小集合中的所有元素
        boolean containsAll(Collection<?> c);
    
        // 将一个小集合中的所有元素添加到当前集合中
        boolean addAll(Collection<? extends E> c);
    
        // 将当前集合中移除指定小集合中的元素
        boolean removeAll(Collection<?> c);
    
        // 移除当前集合中不包含在小集合c中的元素
        boolean retainAll(Collection<?> c);
    
        // 清空集合：移除集合中所有元素
        void clear();
    
        // 判断两个集合是否相等
        boolean equals(Object o);
    
        // 当前集合的hash值
        int hashCode();
    }

我们看到 Collection 接口中定义的方法无非就是对集合中原始的增、删、是否包含、遍历等等。其中对元素的遍历功能来自于其继承了 Iterable 接口，Iterable 接口源码如下：

package java.lang;
    
    import java.util.Iterator;
    
    public interface Iterable<T> {
    
        Iterator<T> iterator();
    }

在 Java 中所有实现了 Collection 接口的类都必须提供两套标准的构造函数，一个是无参：用于创建一个空的Collection；另一个是带有 Collection 参数的有参构造函数，用于创建一个新的 Collection，这个新的 Collection 与传入进来的Collection 具备相同的元素。

*  **要求实现一个自定义集合：具备基本的增删改查方法，并且需要能够转换为数组类型**

package com.zju.collection;
    
    import java.util.Collection;
    import java.util.Iterator;
    
    /**
     * 自定义一个集合
     */
    public class customCollection implements Collection{
    
    	@Override
    	public int size() {
    		return 0;
    	}
    
    	@Override
    	public boolean isEmpty() {
    		return false;
    	}
    
    	@Override
    	public boolean contains(Object o) {
    		return false;
    	}
    
    	@Override
    	public Iterator iterator() {
    		return null;
    	}
    
    	@Override
    	public Object[] toArray() {
    		return null;
    	}
    
    	@Override
    	public boolean add(Object e) {
    		return false;
    	}
    
    	@Override
    	public boolean remove(Object o) {
    		return false;
    	}
    
    	@Override
    	public boolean containsAll(Collection c) {
    		return false;
    	}
    
    	@Override
    	public boolean addAll(Collection c) {
    		return false;
    	}
    
    	@Override
    	public boolean removeAll(Collection c) {
    		return false;
    	}
    
    	@Override
    	public boolean retainAll(Collection c) {
    		return false;
    	}
    
    	@Override
    	public void clear() {
    
    	}
    	
    	// 省略部分代码
    	
    	@Override
    	public Object[] toArray(Object[] a) {
    		return new Object[0];
    	}
    }

--------------------

## 3、List 接口 ##

List 接口为 Collection 子接口。List 所代表的是有序的 Collection，即它用某种特定的插入顺序来维护元素顺序。用户可以对列表中每个元素的插入位置进行精确地控制，同时可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。实现List接口的集合主要有：ArrayList、LinkedList、Vector、Stack。

*  List 接口的源码分析

package java.util;
    
    public interface List<E> extends Collection<E> {
        
        int size();
        
        boolean isEmpty();
    
        boolean contains(Object o);
    
        Iterator<E> iterator();
    
        Object[] toArray();
    
        <T> T[] toArray(T[] a);
    
        boolean add(E e);
    
        boolean remove(Object o);
    
        boolean containsAll(Collection<?> c);
    
        boolean addAll(Collection<? extends E> c);
    
        boolean addAll(int index, Collection<? extends E> c);
      
        boolean removeAll(Collection<?> c);
    
        boolean retainAll(Collection<?> c);
    
        void clear();
    
        boolean equals(Object o);
    
        int hashCode();
    	
    // 上面的方法都是继承自Collection接口中的
    //.....................................................
    // 下面的方法是List接口自己定义的
    	
        // 获取元素：获取下标为index的元素
        E get(int index);
    	
        // 修改元素：将下标为index的元素修改为element
        E set(int index, E element);
    
        // 添加元素：在下标为index的位置插入元素element
        void add(int index, E element);
    
        // 删除元素：将下标为index的元素移除
        E remove(int index);
    
        // 返回集合中第一个等于o的元素的下标
        int indexOf(Object o);
    
        // 返回集合中最后一个等于o的元素的下标
        int lastIndexOf(Object o);
    
        // 遍历集合：list集合迭代器
        ListIterator<E> listIterator();
    
        // 遍历集合：从Index下标开始
        ListIterator<E> listIterator(int index);
    
        // 截取集合：从 fromIndex 到 toIndex
        List<E> subList(int fromIndex, int toIndex);
    }

### 3.1、ArrayList ###

ArrayList是一个动态数组，也是我们最常用的集合。它允许任何符合规则的元素插入，甚至包括null。每一个ArrayList都有一个初始容量（10），该容量代表了数组的大小。随着容器中的元素不断增加，容器的大小也会随着增加。在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作。所以如果我们明确所插入元素的多少，最好指定一个初始容量值，避免过多的进行扩容操作而浪费时间、效率。

size、isEmpty、get、set、iterator 和 listIterator 操作都以固定时间运行。add 操作以分摊的固定时间运行，也就是说，添加 n 个元素需要 O(n) 时间（由于要考虑到扩容，所以这不只是添加元素会带来分摊固定时间开销那样简单）。

ArrayList 擅长于随机访问。同时ArrayList是非同步的，即非线程安全的。

## 3.2、LinkedList ##

同样实现List接口的LinkedList与ArrayList不同，ArrayList是一个动态数组，而LinkedList是一个双向链表。所以它除了有ArrayList的基本操作方法外还额外提供了get，remove，insert方法在LinkedList的首部或尾部。

由于实现的方式不同，LinkedList不能随机访问，它所有的操作都是要按照双向链表的需要执行。在列表中索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。这样做的好处就是可以通过较低的代价在List中进行插入和删除操作。

与ArrayList一样，LinkedList也是非同步的。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List： List list = Collections.synchronizedList(new LinkedList(…));

### 3.3、Vector  ###

与ArrayList相似，但是Vector是同步的。所以说Vector是线程安全的动态数组。它的操作与ArrayList几乎一样。

### 3.4、Stack  ###

Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop 方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

--------------------

## 4、Set 接口 ##

**Set是一种不包括重复元素的Collection**。它维持它自己的内部排序，所以随机访问没有任何意义。与List一样，它同样运行null的存在但是仅有一个。由于Set接口的特殊性，所有传入Set集合中的元素都必须不同，同时要注意任何可变对象。如果在对集合中元素进行操作时，导致e1.equals(e2)==true，则必定会产生某些问题。实现了Set接口的集合有：EnumSet、HashSet、TreeSet。

*  Set接口的源码

可以看到Set接口继承自Collection接口，其中的方法都来自于Collection接口。

Set接口规定将set看成一个集合，并且使用和数组类似的增删改查方式，同时提供iterator迭代器。

package java.util;
    
    public interface Set<E> extends Collection<E> {
        
        int size();
    
        boolean isEmpty();
    
        boolean contains(Object o);
    
        Iterator<E> iterator();
    
        Object[] toArray();
    
        <T> T[] toArray(T[] a);
    
        boolean add(E e);
    
        boolean remove(Object o);
    
        boolean containsAll(Collection<?> c);
    
        boolean addAll(Collection<? extends E> c);
    
        boolean retainAll(Collection<?> c);
    
        boolean removeAll(Collection<?> c);
    
        void clear();
    
        boolean equals(Object o);
    
        int hashCode();
    }

### 3.1、EnumSet  ###

是枚举的专用Set。所有的元素都是枚举类型。

### 3.2、HashSet  ###

**HashSet堪称查询速度最快的集合，因为其内部是以HashCode来实现的**。它内部元素的顺序是由哈希码来决定的，所以它不保证set 的迭代顺序，特别是它不保证该顺序恒久不变。

### 3.3. TreeSet ###

基于 TreeMap，生成一个总是处于排序状态的 Set，内部以TreeMap来实现。它是使用元素的自然顺序对元素进行排序，或者根据创建Set 时提供的** **`Comparator `进行排序，具体取决于使用的构造方法。

--------------------

## 4、Map ##

**Map与List、Set接口不同，它是由一系列键值对组成的集合，提供了 key 到 value 的映射**。同时它也没有继承Collection。在 Map 中它保证了 key 与 value 之间的一一对应关系。也就是说一个 key 对应一个 value，所以它不能存在相同的 key 值，当然 value 值可以相同。实现 map 的有：HashMap、TreeMap、HashTable、Properties、EnumMap。

Map接口是最上层接口，Map接口实现类必须实现 put 和 get 等哈希操作。并且要提供 keyset 和 values，以及 entryset 等查询结构。

*  **Map接口的源码**

可以看到 Map 是“原生”的接口，没有继承任何接口。内部还是对元素的增删改查操作。

其内部由一个内部接口：Entry，用于操作 Map 集合中的键 key（或者hashCode），将其封装成 Set集合类型，这是因为 Map集合并没有继承 Iterator 接口，所以自己无法遍历集合中的元素，所以将所有的键值封装到 Set 集合中，采用这样的方式来遍历集合中的元素。

package java.util;
    
    public interface Map<K,V> {
        // 集合大小
        int size();
    
        // 判断集合是否为空
        boolean isEmpty();
    
        // 判断集合中是否存在key
        boolean containsKey(Object key);
    
        // 判断集合中是否存在value
        boolean containsValue(Object value);
    
        // 获取元素：获取键为key的元素
        V get(Object key);
    
        // 插入元素
        V put(K key, V value);
    
        // 删除元素
        V remove(Object key);
    
        // 插入多个元素
        void putAll(Map<? extends K, ? extends V> m);
    
        // 清空集合
        void clear();
    
        // map集合中key的集合，Set类型
        Set<K> keySet();
    
        // map集合中value的集合
        Collection<V> values();
    
        // 返回Map集合中的所有key
        Set<Map.Entry<K, V>> entrySet();
    
        // Entry内部接口
        interface Entry<K,V> {
            
            K getKey();
    
            V getValue();
    
            V setValue(V value);
    
            boolean equals(Object o);
    
            int hashCode();
        }
    
        // 判断两个map集合是否相等
        boolean equals(Object o);
    
        // 计算当前map集合的hash值
        int hashCode();
    }

### 4.1、HashMap  ###

以哈希表数据结构实现，查找对象时通过哈希函数计算其位置，它是为快速查询而设计的，其内部定义了一个hash表数组（Entry\[ \] table），元素会通过哈希转换函数将元素的哈希地址转换成数组中存放的索引，如果有冲突，则使用散列链表的形式将所有相同哈希地址的元素串起来，可能通过查看 HashMap.Entry 的源码它是一个单链表结构。

### 4.2、TreeMap  ###

键以某种排序规则排序，内部以 red-black（红-黑）树数据结构实现，实现了 SortedMap 接口。

### 4.3、HashTable  ###

也是以哈希表数据结构实现的，解决冲突时与 HashMap 也一样也是采用了散列链表的形式，不过性能比 HashMap 要低。

--------------------

## 5、Queue ##

Queue：队列，它主要分为两大类：

一类是：**阻塞式队列**，队列满了以后再插入元素则会抛出异常，主要包括：ArrayBlockQueue、PriorityBlockingQueue、LinkedBlockingQueue。

另一类队列则是：**双端队列**，支持在头、尾两端插入和移除元素，主要包括：ArrayDeque、LinkedBlockingDeque、LinkedList。

*  **Queue 接口的源码**

package java.util;
    
    public interface Queue<E> extends Collection<E> {
        // 插入元素，如果队列已满，则抛出一个IIIegaISlabEepeplian异常
        boolean add(E e);
    
        // 添加一个元素并返回true，如果队列已满，则返回false
        boolean offer(E e);
    	
        // 移除并返回队列头部的元素，如果队列为空，则抛出一个NoSuchElementException异常
        E remove();
    
        // 移除并返问队列头部的元素，如果队列为空，则返回null
        E poll();
    
        // 返回队列头部的元素，如果队列为空，则抛出一个NoSuchElementException异常
        E element();
    
        // 返回队列头部的元素，如果队列为空，则返回null
        E peek();
    }

--------------------

## 6、转发文章：[关于 Java 集合的小抄][Java] ##

在尽可能短的篇幅里，将所有集合与并发集合的特征、实现方式、性能捋一遍。适合所有”精通Java”，其实还不那么自信的人阅读。

期望能不止用于面试时，平时选择数据结构，也能考虑一下其成本与效率，不要看着API合适就用了。

### 6.1、List ###

*  **1. ArrayList **

以数组实现。节约空间，但数组有容量限制。超出限制时会增加50%容量，用System.arraycopy（）复制到新的数组。**因此最好能给出数组大小的预估值。默认第一次插入元素时创建大小为10的数组。**

按数组下标访问元素－get（i）、set（i,e） 的性能很高，这是数组的基本优势。

如果按下标插入元素、删除元素－add（i,e）、 remove（i）、remove（e），则要用System.arraycopy（）来复制移动部分受影响的元素，性能就变差了。

越是前面的元素，修改时要移动的元素越多。直接在数组末尾加入元素－常用的add（e），删除最后一个元素则无影响。

*  **2. LinkedList **

以双向链表实现。链表无容量限制，但双向链表本身使用了更多空间，每插入一个元素都要构造一个额外的Node对象，也需要额外的链表指针操作。

按下标访问元素－get（i）、set（i,e） 要悲剧的部分遍历链表将指针移动到位 （如果i > 数组大小的一半，会从末尾移起）。

插入、删除元素时修改前后节点的指针即可，不再需要复制移动。但还是要部分遍历链表的指针才能移动到下标所指的位置。

只有在链表两头的操作－add（）、addFirst（）、removeLast（）或用iterator（）上的remove（）倒能省掉指针的移动。

Apache Commons 有个TreeNodeList，里面是棵二叉树，可以快速移动指针到位。

*  **3. CopyOnWriteArrayList **

**并发优化的ArrayList。基于不可变对象策略，在修改时先复制出一个数组快照来修改，改好了，再让内部指针指向新数组。**

因为对快照的修改对读操作来说不可见，所以读读之间不互斥，读写之间也不互斥，只有写写之间要加锁互斥。但复制快照的成本昂贵，典型的适合读多写少的场景。

虽然增加了addIfAbsent(e) 方法，会遍历数组来检查元素是否已存在，性能可想像的不会太好。

*  **遗憾 **

无论哪种实现，按值返回下标contains(e) , indexOf(e) , remove(e) 都需遍历所有元素进行比较，性能可想像的不会太好。

没有按元素值排序的SortedList。

除了CopyOnWriteArrayList，再没有其他线程安全又并发优化的实现如ConcurrentLinkedList。凑合着用Set与Queue中的等价类时，会缺少一些 List 特有的方法如 get(i)。如果更新频率较高，或数组较大时，还是得用Collections.synchronizedList(list)，对所有操作用同一把锁来保证线程安全。

### 6.2、Map ###

*  **1. HashMap**

**以Entry\[ \]数组实现的哈希桶数组，用Key的哈希值取模桶数组的大小可得到数组下标。**

**插入元素时，如果两条Key落在同一个桶**（比如哈希值1和17取模16后都属于第一个哈希桶），我们称之为**哈希冲突**。

JDK的做法是**链表法**，Entry用一个next 属性实现多个Entry以单向链表存放。查找哈希值为17的key时，先定位到哈希桶，然后链表遍历桶里所有元素，逐个比较其Hash值然后key值。

**在JDK8里，新增默认为 8 的阈值，当一个桶里的Entry超过阈值，就不以单向链表而以红黑树来存放以加快Key的查找速度。**

当然，最好还是桶里只有一个元素，不用去比较。所以默认当Entry数量达到桶数量的75%时，哈希冲突已比较严重，就会成倍扩容桶数组，并重新分配所有原来的Entry。扩容成本不低，所以也最好有个预估值。

取模用与操作（hash & （arrayLength-1））会比较快，所以数组的大小永远是2的 N 次方， 你随便给一个初始值比如17会转为32。默认第一次放入元素时的初始值是16。

iterator() 时顺着哈希桶数组来遍历，看起来是个乱序。

*  **2. LinkedHashMap **

**扩展HashMap，每个Entry增加双向链表，号称是最占内存的数据结构。**

支持iterator()时按Entry的插入顺序来排序（如果设置accessOrder属性为true，则所有读写访问都排序）。

插入时，Entry 把自己加到 Header Entry 的前面去。如果所有读写访问都要排序，还要把前后 Entry 的 before/after 拼接起来以在链表中删除掉自己，所以此时读操作也是线程不安全的了。

*  **3. TreeMap **

以红黑树实现，红黑树又叫自平衡二叉树：**对于任一节点而言，其到叶节点的每一条路径都包含相同数目的黑结点。   
上面的规定，使得树的层数不会差的太远，使得所有操作的复杂度不超过 O(logn)，但也使得插入，修改时要复杂的左旋右旋来保持树的平衡。**

支持iterator()时按Key值排序，可按实现了Comparable接口的Key的升序排序，或由传入的Comparator控制。可想象的，在树上插入/删除元素的代价一定比HashMap的大。

支持SortedMap接口，如firstKey()，lastKey() 取得最大、最小的key，或sub（fromKey, toKey）, tailMap（fromKey）剪取Map的某一段。

*  **4. EnumMap **

EnumMap的原理是，在构造函数里要传入枚举类，那它就构建一个与枚举的所有值等大的数组，按Enum. ordinal（）下标来访问数组。性能与内存占用俱佳。

美中不足的是，因为要实现Map接口，而 V get(Object key) 中key是Object而不是泛型K，所以安全起见，EnumMap每次访问都要先对Key进行类型判断，在JMC里录得不低的采样命中频率。

*  **5. ConcurrentHashMap **

并发优化的HashMap。

**在JDK5里的经典设计，默认16 把写锁（可以设置更多），有效分散了阻塞的概率。数据结构为Segment\[ \]，每个Segment一把锁。Segment里面才是哈希桶数组。Key先算出它在哪个Segment里，再去算它在哪个哈希桶里。**

也没有读锁，因为put/remove动作是个原子动作（比如put的整个过程是一个对数组元素/Entry 指针的赋值操作），读操作不会看到一个更新动作的中间状态。

但在JDK8里，Segment\[ \]的设计被抛弃了，改为精心设计的，只在需要锁的时候加锁。

支持ConcurrentMap接口，如 putIfAbsent(key，value) 与相反的 replace(key，value) 与以及实现CAS的 replace(key, oldValue, newValue) 。

*  **6. ConcurrentSkipListMap **

JDK6新增的并发优化的SortedMap，以SkipList（跳表）结构实现。Concurrent包选用它是因为它支持基于CAS的无锁算法，而红黑树则没有好的无锁算法。

原理上，可以想象为多个链表组成的N层楼，其中的元素从稀疏到密集，每个元素有往右与往下的指针。从第一层楼开始遍历，如果右端的值比期望的大，那就往下走一层，继续往前走。

典型的空间换时间。每次插入，都要决定在哪几层插入，同时，要决定要不要多盖一层楼。

它的size()同样不能随便调，会遍历来统计。

### 6.3、Set ###

**所有Set几乎都是内部用一个Map来实现，因为Map里的KeySet就是一个Set，而value是假值，全部使用同一个Object即可。**

Set的特征也继承了那些内部的Map实现的特征。

**HashSet：**内部是HashMap。

**LinkedHashSet：**内部是LinkedHashMap。

**TreeSet：**内部是TreeMap的SortedSet。

**ConcurrentSkipListSet：**内部是ConcurrentSkipListMap的并发优化的SortedSet。

**CopyOnWriteArraySet：**内部是CopyOnWriteArrayList的并发优化的Set，利用其addIfAbsent()方法实现元素去重，如前所述该方法的性能很一般。

好像少了个ConcurrentHashSet，本来也该有一个内部用ConcurrentHashMap的简单实现，但JDK偏偏没提供。Jetty就自己简单封了一个，Guava则直接用java.util.Collections.newSetFromMap(new ConcurrentHashMap())  实现。

### 6.4、Queue ###

Queue是在两端出入的List，所以也可以用数组或链表来实现。

*  **1. 普通队列 **

**（1）LinkedList：**

**LinkedList 是以双向链表实现的。LinkedList 既是 List，也是 Queue。**

**（2）ArrayDeque ：**

以循环数组实现的双向Queue。大小是2的倍数，默认是16。

为了支持FIFO，即从数组尾压入元素（快），从数组头取出元素（超慢），就不能再使用普通ArrayList的实现了，改为使用**循环数组**。

有队头队尾两个下标：弹出元素时，队头下标递增；加入元素时，队尾下标递增。如果加入元素时已到数组空间的末尾，则将元素赋值到数组\[0\]，同时队尾下标指向0，再插入下一个元素则赋值到数组\[1\]，队尾下标指向1。如果队尾的下标追上队头，说明数组所有空间已用完，进行双倍的数组扩容。

**（3）PriorityQueue **

**用平衡二叉最小堆实现的优先级队列**，不再是 FIFO，而是按元素实现的 Comparable 接口或传入 Comparator 的比较结果来出队，**数值越小，优先级越高，越先出队**。但是注意其 iterator() 的返回不会排序。

平衡最小二叉堆，用一个简单的数组即可表达，可以快速寻址，没有指针什么的。最小的在queue\[0\] ，比如queue\[4\]的两个孩子，会在queue\[2\*4+1\] 和 queue\[2\*（4+1）\]，即queue\[9\]和queue\[10\]。

入队时，插入queue\[size\]，然后二叉地往上比较调整堆。

出队时，弹出queue\[0\]，然后把queque\[size\]拿出来二叉地往下比较调整堆。

初始大小为11，空间不够时自动50%扩容。

*  **2. 线程安全的队列 **

**（1）ConcurrentLinkedQueue/Deque **

**无界的并发优化的Queue，基于链表，实现了依赖于CAS的无锁算法。**

ConcurrentLinkedQueue的结构是单向链表和head/tail两个指针，因为入队时需要修改队尾元素的next指针，以及修改tail指向新入队的元素两个CAS动作无法原子，所以需要的特殊的算法。

*  **3. 线程安全的阻塞队列 **

BlockingQueue，一来如果队列已空不用重复的查看是否有新数据而会阻塞在那里，二来队列的长度受限，用以保证生产者与消费者的速度不会相差太远。当入队时队列已满，或出队时队列已空，不同函数的效果见下表：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 4][]

**（1）ArrayBlockingQueue **

定长的并发优化的BlockingQueue，也是基于循环数组实现。有一把公共的锁与notFull、notEmpty两个Condition管理队列满或空时的阻塞状态。

**（2）LinkedBlockingQueue/Deque **

可选定长的并发优化的BlockingQueue，基于链表实现，所以可以把长度设为Integer.MAX\_VALUE成为无界无等待的。

利用链表的特征，分离了takeLock与putLock两把锁，继续用notEmpty、notFull管理队列满或空时的阻塞状态。

**（3）PriorityBlockingQueue **

无界的PriorityQueue，也是基于数组存储的二叉堆（见前）。一把公共的锁实现线程安全。因为无界，空间不够时会自动扩容，所以入列时不会锁，出列为空时才会锁。

**（4）DelayQueue **

内部包含一个PriorityQueue，同样是无界的，同样是出列时才会锁。一把公共的锁实现线程安全。元素需实现Delayed接口，每次调用时需返回当前离触发时间还有多久，小于0表示该触发了。

pull()  时会用 peek() 查看队头的元素，检查是否到达触发时间。ScheduledThreadPoolExecutor 用了类似的结构。

*  **4. 同步队列 **

SynchronousQueue 同步队列本身无容量，放入元素时，比如等待元素被另一条线程的消费者取走再返回。JDK线程池里用它。

JDK7还有个 LinkedTransferQueue，在普通线程安全的 BlockingQueue 的基础上，增加一个 transfer(e) 函数，效果与SynchronousQueue 一样。

--------------------

## 7、异同点 ##

本部分内容转自于：[http://cmsblogs.com/?p=106][http_cmsblogs.com_p_106]

### 7.1  Vector 和 ArrayList ###

> 1、Vector是线程同步的，所以它也是线程安全的，而 ArrayList 是线程异步的，是不安全的。如果不考虑到线程的安全因素，一般用arraylist效率比较高。
> 
> 2、如果集合中的元素的数目大于目前集合数组的长度时，Vector 增长率为目前数组长度的100%,而ArrayList 增长率为目前数组长度的50%.如过在集合中使用数据量比较大的数据，用 Vector 有一定的优势。
> 
> 3、如果查找一个指定位置的数据，Vector 和ArrayList 使用的时间是相同的，都是0(1),这个时候使用 Vector和ArrayList 都可以。而如果移动一个指定位置的数据花费的时间为 O(n - i)，n 为总长度，这个时候就应该考虑到使用linklist,因为它移动一个指定位置的数据所花费的时间为0(1)，而查询一个指定位置的数据时花费的时间为0(i)。

ArrayList 和 Vector 是采用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，都允许直接序号索引元素，但是插入数据要设计到数组元素移动等内存操作，所以索引数据快插入数据慢，Vector 由于使用了 synchronized 方法（线程安全）所以性能上比 ArrayList 要差，LinkedList 使用双向链表实现存储，按序号索引数据需要进行向前或向后遍历，但是插入数据时只需要记录本项的前后项即可，所以插入数度较快！

### 7.2  A**arraylist 和 Linkedlist** ###

> 1、ArrayList是实现了基于动态数组的数据结构，LinkedList 基于链表的数据结构。
> 
> 2、对于随机访问 get 和 set，ArrayList觉得优于LinkedList，因为 LinkedList 要移动指针。
> 
> 3、对于新增和删除操作 add 和 remove，LinedList 比较占优势，因为 ArrayList 要移动数据。这一点要看实际情况的。若只对单条数据插入或删除，ArrayList 的速度反而优于 LinkedList。但若是批量随机的插入删除数据，LinkedList的速度大大优于ArrayList。因为 ArrayList 每插入一条数据，要移动插入点及之后的所有数据。

### 7.3  HashMap 和 TreeMap ###

> 1、HashMap 通过 hashCode 对其内容进行快速查找，而 TreeMap 中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap（HashMap中元素的排列顺序是不固定的）。HashMap 中元素的排列顺序是不固定的）。
> 
> 2、HashMap 通过 hashCode 对其内容进行快速查找，而 TreeMap 中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap（HashMap中元素的排列顺序是不固定的）。集合框架”提供两种常规的Map实现：HashMap 和 TreeMap (TreeMap实现SortedMap接口)。
> 
> 3、在 Map 中插入. 删除和定位元素，HashMap 是最好的选择。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap 会更好。使用 HashMap 要求添加的键类明确定义了 hashCode() 和 equals() 的实现。 这个 TreeMap 没有调优选项，因为该树总处于平衡状态。

### 7.4  HashTable与HashMap ###

> 1、历史原因：HashTable 是基于陈旧的 Dictionary 类的，HashMap 是 Java 1.2 引进的 Map 接口的一个实现 。
> 
> 2、同步性：Hashtable 是线程安全的，也就是说是同步的，而 HashMap 是线程序不安全的，不是同步的 。
> 
> 3、值：只有 HashMap 可以让你将空值作为一个表的条目的 key 或 value 。

--------------------

## 8、对集合的选择 ##

### 8.1  对 List 的选择 ###

> 1、对于随机查询与迭代遍历操作，数组比所有的容器都要快。所以在随机访问中一般使用 ArrayList
> 
> 2、LinkedList 使用双向链表对元素的增加和删除提供了非常好的支持，而 ArrayList 执行增加和删除元素需要进行元素位移。
> 
> 3、对于 Vector 而已，我们一般都是避免使用。
> 
> 4、将 ArrayList 当做首选，毕竟对于集合元素而已我们都是进行遍历，只有当程序的性能因为List的频繁插入和删除而降低时，再考虑LinkedList。

### 8.2  对 Set 的选择 ###

> 1、HashSet 由于使用 HashCode 实现，所以在某种程度上来说它的性能永远比 TreeSet 要好，尤其是进行增加和查找操作。
> 
> 2、虽然 TreeSet 没有 HashSet 性能好，但是由于它可以维持元素的排序，所以它还是存在用武之地的。

### 8.3  对 Map 的选择 ###

> 1、HashMap 与 HashSet 同样，支持快速查询。虽然 HashTable 速度的速度也不慢，但是在 HashMap 面前还是稍微慢了些，所以 HashMap 在查询方面可以取代 HashTable。
> 
> 2、由于TreeMap 需要维持内部元素的顺序，所以它通常要比 HashMap 和 HashTable 慢。

[https_blog.csdn.net_a724888_article_details_80215706]: https://blog.csdn.net/a724888/article/details/80215706
[https_github.com_h2pl_MyTech]: https://github.com/h2pl/MyTech
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70]: /images/20220327/d5c4b39b7f434584958209b50b148d53.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1]: /images/20220327/408768a9aab44cf18b9f7c1386613f00.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 2]: /images/20220327/c59be3ffb9464f559552bb642f7fc4cc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 3]: /images/20220327/0ac2bc25754c4051ad19d567596cc246.png
[Java]: http://calvin1978.blogcn.com/articles/collection.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 4]: /images/20220327/5723f093881c4f37923716371e168812.png
[http_cmsblogs.com_p_106]: http://cmsblogs.com/?p=106