[Java知识库]Java 集合大全（一）

接口总览

列表/栈（List/Stack）

Vector

Vector 是矢量队列，它是JDK1.0版本添加的类。继承于AbstractList，实现了List, RandomAccess, Cloneable这些接口。
Vector 继承了AbstractList，实现了List；所以，它是一个队列，支持相关的添加、删除、修改、遍历等功能。
Vector 实现了RandmoAccess接口，即提供了随机访问功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的。在Vector中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。
Vector 实现了Cloneable接口，即实现clone()函数。它能被克隆。
和ArrayList不同，Vector中的操作是线程安全的。
Vector支持Enumeration遍历.

Enumeration接口中定义了一些方法，通过这些方法可以枚举（一次获得一个）对象集合中的元素。
这种传统接口已被迭代器取代，虽然Enumeration 还未被遗弃，但在现代代码中已经被很少使用了。尽管如此，它还是使用在诸如Vector和Properties这些传统类所定义的方法中，除此之外，还用在一些API类，并且在应用程序中也广泛被使用。

Stack

java工具包中的Stack是继承于Vector(矢量队列)的，由于Vector是通过数组实现的，这就意味着，Stack也是通过数组实现的，而非链表。
Stack中的操作是线程安全的。

ArrayList

ArrayList 是一个数组队列，相当于 动态数组。与Java中的数组相比，它的容量能动态增长。它继承于AbstractList，实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。
ArrayList 继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。
ArrayList 实现了RandmoAccess接口，即提供了随机访问功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的。在ArrayList中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。稍后，我们会比较List的“快速随机访问”和“通过Iterator迭代器访问”的效率。
ArrayList 实现了Cloneable接口，即覆盖了函数clone()，能被克隆。
ArrayList 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。
和Vector不同，ArrayList中的操作不是线程安全的。所以，建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList。

LinkedList

LinkedList是基于链表实现的，所以先讲解一下什么是链表。

链表原先是C/C++的概念，是一种线性的存储结构，意思是将要存储的数据存在一个存储单元里面，这个存储单元里面除了存放有待存储的数据以外，还存储有其下一个存储单元的地址（下一个存储单元的地址是必要的，有些存储结构还存放有其前一个存储单元的地址），每次查找数据的时候，通过某个存储单元中的下一个存储单元的地址寻找其后面的那个存储单元。

这么讲可能有点抽象，先提一句，LinkedList是一种双向链表，双向链表我认为有两点含义：

1. 链表中任意一个存储单元都可以通过向前或者向后寻址的方式获取到其前一个存储单元和其后一个存储单元
2. 链表的尾节点的后一个节点是链表的头结点，链表的头结点的前一个节点是链表的尾节点
   LinkedList底层的数据结构是基于双向循环链表的，且头结点中不存放数据。

集合（Set）

HashSet

HashSet底层采用 HashMap 来保存所有元素，是一个不允许有重复元素的集合。
HashSet的实现其实非常简单，它只是封装了一个 HashMap 对象来存储所有的集合元素，所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存。
HashSet允许有 null 值。
HashSet是无序的，即不会记录插入的顺序。
HashSet不是线程安全的， 如果多个线程尝试同时修改 HashSet，则最终结果是不确定的。 您必须在多线程访问时显式同步对 HashSet 的并发访问。
HashSet实现了 Set 接口。

LinkedHashSet

LinkedHashSet是Set集合的一个实现，具有set集合不重复的特点，同时具有可预测的迭代顺序，也就是我们插入的顺序。
linkedHashSet是一个非线程安全的集合。如果有多个线程同时访问当前linkedhashset集合容器，并且有一个线程对当前容器中的元素做了修改，那么必须要在外部实现同步保证数据的冥等性。
linkedHashSet继承于HashSet，并且HashSet为LinkedHashSet提供了构造函数：

	HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

TreeSet

TreeSet是用来排序的, 可以指定一个顺序, 对象存入之后会按照指定的顺序排列。
当我们构造TreeSet时：

1. 若使用不带参数的构造函数，则TreeSet默认按照类中Comparable的顺序
2. 若用户需要使用自定义的比较器，则需要使用带比较器的参数
3. 如果都没有提供就报错ClassCastException
4. Comparator优先于Comparable
   TreeSet实际上是TreeMap实现的。
   TreeSet是非线程安全的。
   TreeSet实现java.io.Serializable的方式。当写入到输出流时，依次写入“比较器、容量、全部元素”；当读出输入流时，再依次读取。

EnumSet

EnumSet 是一个专为枚举设计的集合类，EnumSet中的所有元素都必须是指定枚举类型的枚举值，该枚举类型在创建EnumSet时显式或隐式地指定。

• EnumSet的集合元素也是有序的，EnumSet以枚举值在Enum类内的定义顺序来决定集合元素的顺序。
• EnumSet在内部以位向量的形式存储，这种存储形式非常紧凑、高效,因此EnumSet对象占用内存很小，而且运行效率很好。尤其是进行批量操作（如调用containsAll()和retainAll()方法）时，如果其参数也是EnumSet集合，则该批量操作的执行速度也非常快。
• EnumSet集合不允许加入null元素，如果试图插入null元素，EnumSet将抛出NullPointerException异常。
• EnumSet类没有暴露任何构造器来创建该类的实例，程序应该通过它提供的类方法来创建EnumSet对象。
• 如果只是想判断EnumSet是否包含null元素或试图删除null元素都不会抛出异常，只是删除操作将返回false，因为没有任何null元素被删除。

package com.qupeng.collection;

import java.util.EnumSet;

public class TestEnumSet {
    public static void main(String[] args) {
        EnumSet enumSet = EnumSet.allOf(COUNTRY.class);
        System.out.println(enumSet);

        enumSet = EnumSet.noneOf(COUNTRY.class);
        System.out.println(enumSet);
        enumSet.add(COUNTRY.AMERICA);
        System.out.println(enumSet);

        enumSet = EnumSet.of(COUNTRY.CHINA, COUNTRY.GERMAN);
        System.out.println(enumSet);

        enumSet = EnumSet.range(COUNTRY.ENGLAND, COUNTRY.JAPAN);
        System.out.println(enumSet);

        EnumSet enumSet1 = EnumSet.copyOf(enumSet);
        System.out.println(enumSet1);

        EnumSet enumSet2 = EnumSet.complementOf(enumSet);
        System.out.println(enumSet2);
    }

    enum COUNTRY {
        CHINA,
        AMERICA,
        ENGLAND,
        JAPAN,
        GERMAN
    }
}

队列/栈（Queue/stack）

PriorityQueue

PriorityQueue，即优先队列。优先队列的作用是能保证每次取出的元素都是队列中权值最小的（Java的优先队列每次取最小元素，C++的优先队列每次取最大元素）。这里牵涉到了大小关系，元素大小的评判可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较器（Comparator，类似于C++的仿函数）。
Java中PriorityQueue实现了Queue接口，不允许放入null元素；其通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue的底层实现。

ArrayDeque

Queue的结构是一个单端的队列，从一端进另一端出，Deque是一个双端队列。而ArrayDeque是一个使用循环数组实现的双端队列了。双端队列可以实现单端队列的先入先出的方式，也可以实现栈结构的先入后出的方式，使用比较灵活，看具体需求。ArrayDeque是线程非安全的，所以如果需要实现线程安全，就需要自己处理了。

字典（Map）

HashMap

HashMap

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。

散列表（Hash table，也叫哈希表）
是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

哈希冲突
哈希算法存在一个缺点就是哈希冲突。例如，我们进行数据存储时，我们通过对关键字进行hash时得到的地址已经存储过数据了，这时就会出现哈希冲突。因此，哈希函数的设计至关重要，好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀。但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢？哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法，而HashMap即是采用了链地址法，也就是数组+链表的方式

HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。
HashMap 实现了 Map 接口，根据键的 HashCode 值存储数据，具有很快的访问速度，最多允许一条记录的键为 null，不支持线程同步。
HashMap 是无序的，即不会记录插入的顺序。
HashMap 继承于AbstractMap，实现了 Map、Cloneable、java.io.Serializable 接口。
HashMap的数组长度一定是2的次幂

重写equals方法需同时重写hashCode方法
尽管我们在进行get和put操作的时候，使用的key从逻辑上讲是等值的（通过equals比较是相等的），但由于没有重写hashCode方法，所以put操作时，key(hashcode1)–>hash–>indexFor–>最终索引位置 ，而通过key取出value的时候 key(hashcode1)–>hash–>indexFor–>最终索引位置，由于hashcode1不等于hashcode2，导致没有定位到一个数组位置而返回逻辑上错误的值null（也有可能碰巧定位到一个数组位置，但是也会判断其entry的hash值是否相等，上面get方法中有提到。）
所以，在重写equals的方法的时候，必须注意重写hashCode方法，同时还要保证通过equals判断相等的两个对象，调用hashCode方法要返回同样的整数值。而如果equals判断不相等的两个对象，其hashCode可以相同（只不过会发生哈希冲突，应尽量避免）。

LinkedHashMap

LinkedHashMap继承了HashMap，并且在Hash表的基础上又维护了一个双向链表，并且依靠着双向链表保证了迭代顺序是插入的顺序。
LinkedHashMap比HashMap多了一个头指针head（private权限），header指针是一个标记指针不存储任何数据。标记after和before两个指针。
LinkedHashMap的实体Entry也比HashMap的Entry多了before和after两个指针。

    private static class Entry<K,V> extends HashMap.Entry<K,V>{
        Entry<K,V> before, after;
    }

LinkedHashMap还有一个私有变量accessOrder（private final boolean accessOrder；），默认为false，即按照插入顺序遍历;如果设置为true则按照访问顺序遍历。
只能通过这个构造函数设置：

    public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

package com.qupeng.collection;

import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;

public class TestLinkedHashMap {
    public static void main(String[] args) {
        Map<Integer, String> map = new LinkedHashMap<>(16, 0.75f,true);
        int amount = 10;
        while (amount > 0) {
            --amount;
            map.put(amount, String.valueOf(amount));
        }
        System.out.println(map);

        map.get(1);
        map.get(5);
        System.out.println(map);

        for(Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator(); iterator.hasNext();)
        {
            Map.Entry entry = iterator.next();
            System.out.println(entry.getKey()+"->"+map.get(entry.getKey()));
        }

        for(Iterator<Integer> iterator = map.keySet().iterator(); iterator.hasNext();)
        {
            Integer name = iterator.next();
            System.out.println(name+"->"+map.get(name));
        }

    }
}

LinkedHashMap非线程安全。

TreeMap

TreeMap

TreeSet是一个有序集合，可以以任意顺序将元素插入到集合中，在对集合进行遍历的时候，每个元素将自动按照排序后的顺序呈现。底层使用的是二叉树(更具体点是红黑树)实现，对于元素之间排序，如果不指定自定义的比较器Comparator，那么插入的对象必须实现Comparable接口，元素按照实现此接口的compareTo()方法去排序。如果指定了自定义的比较器Comparator，优先使用Comparator去对元素进行排序。比较规则决定了元素是否可以重复，以及元素的排序结果。

HashTable

HashTable

Hashtable是原始的java.util的一部分， 是一个Dictionary具体的实现 。
然而，Java 2 重构的Hashtable实现了Map接口，因此，Hashtable现在集成到了集合框架中。它和HashMap类很相似，但是它支持同步。
像HashMap一样，Hashtable在哈希表中存储键/值对。当使用一个哈希表，要指定用作键的对象，以及要链接到该键的值。
Hashtable的方法是同步的。
HashTable的Key不允许为null。

Properties

Properties（Java.util.Properties），该类继承Hash Table，主要用于读取Java的配置文件，不同的编程语言有自己所支持的配置文件，配置文件中很多变量是经常改变的，为了方便用户的配置，能让用户够脱离程序本身去修改相关的变量设置。就像在Java中，其配置文件常为.properties文件，是以键值对的形式进行参数配置的。
getProperty(String key) 在此属性列表中搜索具有指定键的属性。如果在此属性列表中找不到该键，则会检查默认属性列表及其默认值（递归）。如果未找到该属性，则该方法返回默认值参数。
list(PrintStream out) 将此属性列表打印到指定的输出流。此方法对于调试很有用。
load(InputStream inStream) 从输入字节流中读取属性列表（键和元素对）。输入流采用加载（Reader）中指定的简单的面向行的格式，并假定使用ISO 8859-1字符编码;即每个字节是一个Latin1字符。不在Latin1中的字符和某些特殊字符在使用Unicode转义符的键和元素中表示。 此方法返回后，指定的流仍保持打开状态。
setProperty(String key, String value) 调用 Hashtable 的方法 put 。他通过调用基类的put方法来设置 键值对。
store(OutputStream out, String comments) 将此Properties表中的此属性列表（键和元素对）以适合使用load（InputStream）方法加载到Properties表的格式写入输出流。 此Properties方法不会写出此Properties表的defaults表中的属性（如果有）。
storeToXML(OutputStream os, String comment, String encoding) 使用指定的编码发出表示此表中包含的所有属性的XML文档。
clear() 清除此哈希表，使其不包含任何键。
stringPropertyNames() 返回此属性列表中的一组键，其中键及其对应的值是字符串，如果尚未从主属性列表中找到相同名称的键，则包括默认属性列表中的不同键。键或键不是String类型的属性将被省略。

WeakHashMap/IdentityHashMap/EnumMap

WeakHashMap

WeakHashMap类位于java.util包中。 这是一个Map实现，其中存储了对其键的弱引用。 当key丢失所有的强引用和软引用时， WeakHashMap中的条目将自动删除。

强引用
强引用就是指在程序代码之中普遍存在的，类似“Object obj = new Object()”这类的引用，只要强引用还存在，垃圾收集器永远不会回收掉被引用的对象。当内存空间不足，Java虚拟机宁愿抛出OutOfMemoryError错误，使程序异常终止，也不会靠随意回收具有强引用的对象来解决内存不足问题。
软引用（SoftReference）
软引用是用来描述一些还有用但并非必需的对象。对于软引用关联着的对象，在系统将要发生内存溢出异常之前，将会把这些对象列进回收范围之中进行第二次回收。如果这次回收还没有足够的内存，才会抛出内存溢出异常。在JDK 1.2之后，提供了SoftReference类来实现软引用。只要垃圾回收器没有回收它，该对象就可以被程序使用。软引用可用来实现内存敏感的高速缓存。
弱引用（WeakReference）
弱引用也是用来描述非必需对象的，但是它的强度比软引用更弱一些，被弱引用关联的对象只能生存到下一次垃圾收集发生之前。当垃圾收集器工作时，无论当前内存是否足够，都会回收掉只被弱引用关联的对象。在JDK 1.2之后，提供了WeakReference类来实现弱引用。不过，由于垃圾回收器是一个优先级很低的线程， 因此不一定会很快发现那些只具有弱引用的对象。
虚引用（PhantomReference）
虚引用也称为幽灵引用或者幻影引用，它是最弱的一种引用关系。一个对象是否有虚引用的存在，完全不会对其生存时间构成影响，也无法通过虚引用来取得一个对象实例。为一个对象设置虚引用关联的唯一目的就是能在这个对象被收集器回收时收到一个系统通知。在JDK 1.2之后，提供了PhantomReference类来实现虚引用。

package com.qupeng.collection;

import java.util.Map;
import java.util.WeakHashMap;

public class TestWeakHashMap {
    public static void main(String[] args) {
        Map<Product, String> map = new WeakHashMap<>();
        map.put(new Product("a"), "a");
        map.put(new Product("b"), "b");
        map.put(new Product("b"), "c");
        Product d = new Product("d");
        map.put(d, "d");
        System.out.println(map);
        System.gc();
        System.out.println(map);
    }

    static class Product {
        private String name;
        public Product(String name) {
            this.name = name;
        }
    }
}

IdentityHashMap

IdentityHashMap也是Map的一个子类，其也是一个有特性的Map。一样是通过Hash表的方法实现了Map接口，但是其比较键值是否相等的时候，并没有使用compare方法，而是使用是否是同一个引用来判断。所以k1和k2只有完全是同一个的时候才会相等k1==k2(通常是都不为null时k1.equals(k2)来判断)。

package com.qupeng.collection;

import java.util.*;

public class TestIdentityHashMap {
    public static void main(String[] args) {
        Map<Product, String> idMap = new IdentityHashMap<>();
        idMap.put(new Product("a"), "a");
        idMap.put(new Product("a"), "b");
        idMap.put(new Product("a"), "c");
        System.out.println(idMap);

        Map<Product, String> hashMap = new HashMap<>();
        hashMap.put(new Product("a"), "a");
        hashMap.put(new Product("a"), "b");
        hashMap.put(new Product("a"), "c");
        System.out.println(hashMap);
    }

    static class Product {
        private String name;
        public Product(String name) {
            this.name = name;
        }

        @Override
        public boolean equals(Object o) {
            return true;
        }

        @Override
        public int hashCode() {
            return 1;
        }
    }
}

EnumMap

EnumMap，该类是专门针对枚举类设计的一个集合类。集合中的所有键必须是同一个枚举类的实例。当EnumMap创建后，会表现成一个数组array，这种表现方式是紧凑高效的。EnumMap的顺序，由枚举类实例的定义顺序决定。集合视图的迭代器是弱一致（weakly consistent）的，不会抛出并发异常ConcurrentModificationException。当迭代器运行时不会展示另一个线程对map的修改。空的键是不被允许的。线程不安全，最好在创建的时候调用Collections#synchronizedMap方法来进行同步。注意，所有基础操作都是常量级时间。

迭代器

操作，算法

不可变包装类

同步包装类

类型检查包装类

空集合类

单体集合包装类

其它包装类

数组算法、操作类