在程序开发的过程中，数据结构必不可少。有了数据结构，程序开发变得更加简洁高效。 Java为开发者提供了类型丰富、功能强大的数据结构工具类。现代主流的数据结构类库都对数据结构的接口和实现进行了分离，java也不例外【1】。
在java中，数据结构的接口主要包括Collection，Map和Iterator。
接口Collection
首先我们来看接口Collection【2】。常用的集合类接口Set，List和Queue都是继承自Collection。其设计非常简单:
public interface Collection<E>{
boolean add(E element); Iterator<E> iterator();
. . .
}
Iterator
这里要着重介绍一下Iterator，即迭代器。
在集合类的框架中，这是最重要的一个工具类。迭代器模式是一种最简单也是最为常见的设计模式【3】【4】，他可以让使用者透过特定的接口去遍历集合中的元素，而不必关心集合的具体实现:
public interface Iterator<E>{
E next();
boolean hasNext();
void remove();
default void forEachRemaining(Consumer<? super E> action);
}
如何使用Iterator遍历集合
Collection<String> c = . . .;
Iterator<String> iter = c.iterator();
while (iter.hasNext()){
String element = iter.next();
do something with element
}
还有一种更简洁的遍历方式：Foreach
for (String element : c){
do something with element}
编译器会将“for each”的循环转化成iterator的循环。
通过iterator删除元素
除了遍历之外，iterator还支持对集合中元素的删除。而且，在遍历的过程中，必须通过iterator删除元素。否则，如果一个iterator发现集合已经被另一个iterator或者集合的方法修改，就会抛出一个异常ConcurrentModificationException。
根据iterator接口的定义，Remove方法会删除上一次next方法返回的元素。
Iterator<String> it = c.iterator();it.next();
// skip over the first element
it.remove(); // now remove it
更为重要的是，next和remove方法之间是存在依赖关系的。如果之前没有调用next方法，那么调用remove将导致一个IllegalStateException 异常的抛出。也就是说，如果你想删除2个相邻的节点，以下方式是错误的：
it.remove();
it.remove(); // ERROR
相反的，你必须首先调用next跳过将要被删除的元素。
it.remove();
it.next();
it.remove(); // OK
添加元素
Iterator本身并不支持添加元素的操作。如果当迭代到一半时调用iterator.add()方法，理论上来说，应该是要在当前这个元素E1后面新增一个元素E2，使得下次遍历此集合时，E2一定会出现在E1后面，也就是 [....E1, E2, ....] 假设add()方法是以这个语意为前提的话，那麽迭代器不提供此方法是很合理的，对于有序的集合(像是ArrayList)来说，在此元素后面新增一个元素是一个很简单的事情，但是对于无序的集合(像是HashSet)来说，不能保证新插入的这个元素E2一定会在E1后面(因为还得计算HashCode)，如此就违反了add()的语意了，这也就是为什麽Iterator接口不提供add()方法【5】
Iterator的子接口 ListIterator 定义了一个方法用于在iterator当前位置之前加入一个元素。
void add(E element)
Map
和Collection接口一样，Map是另集合的另一个基本接口。Map持有key/value对，分别用put方法添加数据，get方法取得数据。
V put(K key, V value)
V get(K key)
Collection内元素的排序
Collection接口不支持元素的排序，List接口是他的子接口，支持元素的排序。在List中，访问元素主要有两种方式，iterator和整数索引。整数索引又称作random access，因为可以以任何顺序访问元素，而iterator只支持顺序的访问元素。
坦率的说，集合框架的这一部分设计的并不好， 在实践中，有两种支持排序的collection接口，他们在不同场景表现出来的性能完全不同。一类排序Collection是由数组实现的，random access非常快，适合用整数索引进行操作。另一类是由链表实现的，尽管也支持排序，但是random access很慢，所以最好是通过iterator遍历。所以说，也许设计成两个接口是一个更好的选择。
作为补救，在java1.4 后引入了一个tag用的接口，RandomAccess，这个接口没有方法，只是用来测试一个特定的collection是否支持高效的random access。
具体的实现类
List
主要实现类为arrayList, linkedlist和Stack。LinkedList是双向链表，既可以作为Stack使用也可以作为Queue使用，在sequential（Iterator）访问的场景下效率更优。ArrayList是用数组实现的，主要支持Random访问。Stack继承自Vector，是线程安全的，大小可伸缩。
Set
Set 接口的行为比 Collection 接口中定义的更为严格。Add方法必须要决绝“相同的”元素。“相同”是由元素的equals 方法定义的。如果两个set包含的全部元素相同，那么就可以认为他们是相同的Set，而不用管元素的顺序是否相同。和List不同，Set中的元素的顺序是无法保证的。常用的Set的实现主要有三种，HashSet，TreeSet，LinkedHashSet。
-
HashSet
在不需要考虑元素的顺序的情况下，有一种常见的数据结构可以更快的找到元素，这就是hash table。Hash table 为每个元素生成一个称为hash code的整数。Hash code是以某种方式在元素的属性的基础上生成的。一个好的生成规则应该保证不同的属性生成不同的hash code。而且hash code的生成要兼容equals方法，即如果a.equals(b), 那么 a 和b 必须有相同的hash code.
在java中，hash table是用链表实现的。每个链表被称为一个bucket。为了找到table中的一个元素，首先要计算他的hash code，然后用计算得到的整数去取bucket数量的模，得到的数字就是存放元素的bucket的索引。当然，有些情况下，一个bucket可能已经存储了其他元素了，也就是发生了hash冲突。此时，equals方法将被用来判断新的元素是否和bucket中存储的某个元素相同。从Java8开始，当bucket满了的时候，将转为采取平衡二叉树的数据结构。
bucket.png - LinkedHashSet
按照插入顺序保存元素。 - TreeSet
元素是排序的，（红黑树，Introduction to Algorithms by Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein, The MIT Press, 2009.）。TreeSet内存放的元素必须是可以比较的，也就是说必须实现Comparable接口，或者使用者必须在构造TreeSet的时候提供一个Comparator类型的对象。
Map
Map：主要有三种。
- HashMap
参照前面介绍的HashSet。 - TreeMap的key是经过排序的，参照TreeSet。
- LinkedHashMap，是用双链表实现的，按照插入顺序保存key。
特别需要注意的是，如果制定的key并不在Map中，get方法将返回null。有些时候（例如更新map中的元素），这并不是开发者想要的行为。Java提供了一些内置的方法以默认值的方式为开发者提供了便利：
counts.put(word, counts.getOrDefault(word, 0) + 1);
或者：
counts.putIfAbsent(word, 0);counts.put(word, counts.get(word) + 1);
还有
counts.merge(word, 1, Integer::sum);
如果key之前并不存在，将word和1关联起来，否则将之前的值和1用Integer::sum 合并。
Queue
Java6引入了一个Deque接口，并提供了两种实现，ArrayDeque和LinkedList，他们的大小会根据需要增加。尽管可以用LinkedList实现Queue的功能，但是java还是专门提供了一些Queue的实现。
例如PriorityQueue，这是一种优先队列，接受支持排序的对象。当调用remove方法的时候，得到的是在当前优先队列中最小的元素。但是，优先队列并不是对所有的元素尽心排列，也就是说如果你遍历队列，就会发现他们的顺序并不被保证。在内部，优先队列是用heap（堆）保存元素的。Heap是一种自组织的二叉树，remove和add方法会使得最小的元素升至二叉树的根，而不必在排列所有元素上花费时间。和treeset一样，priorityQueue中的元素必须实现Comparable接口，或者使用者必须在构造priorityQueue的时候提供一个Comparator类型的对象。
【1】core java chapter 9 collection
【2】java 8 collection API
【3】设计模式详解——迭代器模式
【4】Iterator
【5】Java - 为什麽 Iterator接口 不提供 add(E) 方法 ?
