最近又看了看Java集合方面的内容，想来还是记录下比较好，回头再看是也有个头绪，下面的内容仅作为本人的总结和学习记录，有些混乱，还望想细看的朋友不要捶胸顿足。

在Java1.2之前，其实也有类似于集合方面的数据结构，但是因为缺少统一的规范和接口，所以在使用上极为的不方便，于是在Java1.2时重新设计了Java集合框架。

Java中的集合主要分为两大类，Collection和Map。

集合分类

Collection

在集合中的每个位置只有一个元素。继承自Iterable接口，用来产生获取迭代器。

Collection是所有集合接口的根本父接口，一个Collection中包含有一组Object元素，Collection并没有直接的可直接使用的实现类，而是作为其他具体集合的父集合。

List

元素有序，允许重复元素出现。

可以基于数组也可以基于双向链表来存储元素。

插入和删除元素会引起其他元素索引位置的变化，所以其插入和删除的效率不会太高。

也会根据需要动态增加List的长度来容纳更多元素。

因为每个元素都有确切的位置，所以其检索效率也要高一些。

Set

元素无序，不允许重复元素出现。

因为元素无序，所以元素没有确切的位置，因此插入和删除效率高，但是其查询效率不高。

Quene

队列结构，元素先进先出。

Map

一组键值对对象。在集合中每一个位置都是按照一个“键”对应一个“值”的结构。替代了之前的Dictionary类。

集合UML

对于JDK中的常用集合类做了一个简单的整理，画了一个UML类图，用来帮助理解和记录。

集合特点

接口和实现类分离

Java集合类把接口与实现类做了分离，在程序中只要使用某种接口的集合，只需要在实例化集合类时选择合适的实现类即可，在更换时，也可指更换接口的实现类，而不需要更改接口调用的方法。

集合框架中所有的接口都不是有直接的实现类，而是继承对应接口的抽象类，抽象类实现了接口中的方法。

循环数组是一个有界集合，即内部的元素数量是有限的，如果碰到某些不可预估数量的对象集合，还是用链表比较好。

迭代器

Iterator

Collection接口中有一个iterator()可以返回一个迭代器，用此迭代器便可依次访问集合中的元素。

public interface Iterator<E> {
    boolean hasNext();
    E next();
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

通过调用next()可以逐个访问集合中的元素
hasNext()用来确认集合中是否还有可以访问的元素

调用next()到集合的最后一个元素时，如果继续调用next()就会出错，所以在每次调用next()前应当先调用hasnext()来确认集合中是否还有元素可以读取。

删除元素时，可以调用remve()，用来删除上一次调用next()时返回的元素。因为next()只会返回一个元素，所以在调用next()后只能调用一次remove()。

如果在调用remove()前未调用next()或成功执行了一次remove()后又调用一次，则会抛出IllegalStateException异常。

Collection和Iterator都是泛型接口，Java的设计者也在JDK中为我们提供了预先写好的很多重要的方法，如size()、isEmpty()、clear()等。

for each

从Java5.0开始，Java中加入了for each循环，可以遍历任何实现了Iterable接口的对象。Collection接口继承了Iterable接口，因此for each自然可以遍历所有集合。

1
2
3

for (Element e : 集合){
  集合中元素e的操作
}

数据结构

集合的实现有多种数据结构，比较普遍的是数组的方式，另外还有链表、树等结构。

数组

此种数据结构下，在指定位置添加和删除元素比较费时，因为增加或删除元素后，此位置后的数据都要进行位置变动。

添加元素时，后面的元素往后移动；
删除元素时，后面的元素往前移动。

链表

链表中元素通过标记前一个元素和后一个元素来连接所有元素，因此在插入和删除的操作上比较省力。如果要查看链表中第N个元素，就必须越过链表中N-1个元素，效率很低。因此，不推荐在用索引访问元素时采取链表结构，如果需要使用数字索引来访问元素，那就使用数组或ArrayList。

如果集合数据中元素不多，可以使用ArrayList，如果元素过多，就选择使用链表结构LinkedList。

数组列表

此种结构下，元素都是存储在独立的节点中，在每个节点上也都保存着下一个节点的引用。双向链表结构中，每个节点除了保存着下一个元素的引用外，还保留着前一个节点的引用。

不管是单向还是双向链表，在插入和删除元素时，都较之数组结构高效很多，因为不再需要移动元素，而只需要改变插入（或删除）点前后元素的引用即可。

如果要从数组或数组列表中删除一个元素时，会非常费力，因为元素被删除后，其后面的元素都要向前端移动。同样的，如果在数组或数组列表的中间插入一个元素也会费力。

List接口来表示有序集合，有两种方式来访问其中的元素：迭代器，get方法。get方法并不适用于链表结构的集合，虽然在Java的LinkedList中个提供了get方法来获取元素，但效率并不高。而ArrayList则封装了一个动态改变的数组来实现数组列表。

Vector也可以用来做动态数组的操作，并且内部的方式也是同步的，是线程安全的。但是ArrayList就不是同步的，线程不安全的，在不需要进行同步和跨线程操作时，就可以使用ArrayList。

散列集

散列集也就是哈希表，可以实现快速查找对象。在散列集中，每一个对象都有一个唯一的散列码，就是我们通常所说的，hash code，是一个整数类型，可能为正也可能为负。

每个列表叫做桶（bucket），元素按照索引存放在这一个桶中，不管是插入还是删除都要先把元素的索引计算出来。首先计算出桶的散列码，然后用这个散列码除以桶的数目所得到的余数就是元素的索引。

在散列集中还有一个装填因子（load factor），用来决定何时对散列表进行再散列，通常为（0, 1]，当散列集中的元素超过‘因子 * 100%’时，会用双倍桶数进行再散列。75%的因子是比较何时的。

散列集还有迭代器，会依次访问所有的桶。因为所有的元素都是分散性的存放在散列集中的各个位置，所以访问时也是随机的，没有确定的顺序来访问这些元素。

Java中有一个HashSet实现了散列集合，但是其内部还是用了HashMap来存储数据，把放入HashSet中的元素放入HashMap中的key，并根据key来计算哈希值，而对应的value都是统一的假对象Object。

树集

树集是有序集合，内部元素按照顺序排列。元素插入时，就会按照一定顺序来存储，所以在遍历时也会按照顺序来访问内部元素。树集中元素的排序用到了树形结构来完成。

因为插入时要对元素排序，所以插入效率自然没有散列集高，但是仍然会优于数组或链表。

Java中提供了TreeSet来实现树形集合，要想实现元素的排序，插入的每个元素就都要实现Comparable接口，此接口内部只有一个方法compareTo。如果两个元素a、b比较，则根据a、b的顺序可以得到不同的返回值：

a排序在前，b排序在后，compareTo返回值小于0；
a排序在后，b排序在前，compareTo返回值大于0；
a与b排序相同，compareTo返回值等于0。

TreeSet与HashSet有些类似的地方是，都用了Map的键来存储数据。HashSet内部实际用到的是HashMap，而TreeSet其内部的存储实际用到了TreeMap。都是把要存入Set中的数据放在了Map中的key上，而对应的value就是一个傀儡般的Object对象。

Object类中没有提供compareTo的默认实现，因此如果想往TreeSet中添加自定义对象时，内部的元素就必须实现Comparable接口，并在compareTo方法内部提供排序规则。但是有一个问题就是，如果在此元素对象的类中实现了这个接口，也规定了排序规则，但是元素被插入到了不同的TreeSet中，不同的TreeSet中的元素排序规则又不一样，那要怎么办呢？

此时要了解另一个接口叫做Comparator，其内部用于比较的方法为int compare(T o1, T o2)，应该把需要比较的两个对象传入其中。TreeSet也提供了一个构造方法用来传入Comparator对象用于比较。Comparator的实现类只是一个定义了规则的比较器，其内部并没有任何的数据，不像Comparable的实现类中有数据存在。

树集与散列集相比较而言，树集虽然插入效率会比散列集略低，但是其元素是有序的，并且效率也没有低太多，后续操作会更方便。但是这个排序的过程是费时的，需要对元素内部的某些属性做运算对比，是更为精确的比较。而散列函数就是把数据随机存储而已。

所以，实际使用中到底用散列集HashSet还是用树集TreeSet，还是应该具体看业务如何安排，也要看比较的规则是否复杂等多种情况。

队列与双端队列

队列支持在消息的尾部添加元素，在头部删除元素。有两个端头的队列叫双端队列，可在头部和尾部都添加和删除元素。

Java中有Deque接口来定义队列，实现类有ArrayDeque和LinkedList，可在需要的时候增加队列的长度。

优先级队列

优先级队列是一种特殊的队列，元素是随机插入，但是在取的时候却是按照排序来获取优先级最高的元素，如果删除元素的话，也是删除优先级最低的元素。但是当迭代遍历这个队列时，就不会按照一定的顺序来读取了。

优先级队列采用队（heap）实现，是一个可以自我调整的二叉树，在对树进行增删时可以让最小的元素移动到根。

既然是可以排序的集合，则元素也都必须是实现了Comparable接口，或者提供一个比较器，就类似于TreeSet一样。

Java中提供了PriorityQueue来做优先级队列，在初始化方法中可以自定义队列容量和比较器，如果不提供队列容量，默认为11。

映射表

映射表（map）用来存放键值对的数据，提供键然后找到对应的值。

Java中提供了两个基本的映射表的实现，散列型的HashMap和树类型的TreeMap。无论是散列型还是树型，都是对键进行的散列或排序。散列型的映射表因为是无序的，所以要稍微快一些；树型映射表因为要对键进行排序，速度上多少会有些影响。

映射表中的键是唯一的，不能出现多个相同的键，如果往映射表中前后插入相同键，后插入的键对应的值会取代之前插入的值。

映射表有3个视图：键集，值集合，键值对集。

1
2
3

Set<K> keySet()
Collection<K> values()
Set<Map.Entry<K, V>> entrySet()

总结

上面写的有些乱，当然这只是简单的记录，后面还会针对每一种数据结构做进一步的学习和记录，小弟才疏学浅，难免会有错误或偏差的地方，还望朋友能针对我的不准确的地方给予提醒，万分感谢。