如何使用Java类库设计传统的数据结构
Java集合类库将接口和实现分离。Java类库中也有以Abstract开头的类，如AbstractQueue，这些类是为类库实现者而设计的。
集合类的基本接口是Collection。
for each循环可以与任何实现了Iterable接口的对象一起工作
元素访问的顺序取决于集合类型
Java中链表实际上都是双向链表（doubly linked），每个结点还存储着前驱结点的引用
使用链表的唯一理由是尽可能减少在列表中插入、删除元素的代价
ListIterator是Iterator的子接口，用在List及子类中，描述集合的位置，用add()可以添加元素，previous()、hasPrevious()可以向前遍历List，next()、hasNext()可以向后遍历List
ListIterator的add()在迭代器位置之前添加一个元素。
多次调用add()，元素会依次添加到ListIterator当前位置之前
ListIterator的remove()，在next()调用之后会删除迭代器位置左侧的元素，在previous()调用之后会删除迭代器位置右侧的元素，且不能连续调用两次
ListIterator的set()方法会用一个新元素取代用next或previous方法返回的上一个元素
一个迭代器在修改集合时，另外的迭代器读写改集合会发生ConcurrentModificationException异常。一个简单的方法可以检测到并发修改的问题，集合可以跟踪改写操作的次数，每个迭代器都维护一个独立的计数值。在每个迭代器方法的开始处检查自己改写操作的计数值是否与集合的改写操作的计数值是否一致
ArrayList类不是同步的，Vector类是同步的
HashSet
HashSet可以快速查找元素，但无法控制元素的顺序
散列表为每个对象计算一个散列码（hash code），由对象的实例域产生的一个整数
Java中，散列表用链表数组实现，每个链表成为桶（bucket）。要表中对象的位置，需要先计算对象的散列码，对桶数取余，得到的结果就是这个对象桶数的索引。如果该桶没有其他元素，直接插入桶中就行。如果桶被占满，这种现象被成为散列冲突（hash collision）。这时就需要与桶中所有对象进行比较，查看该对象是否已经存在。如果散列码是合理且随机分布的，桶数足够大，需要比较的次数就会少。
TreeSet是个有序集合。可以以任意顺序将元素插入到集合中，对集合进行遍历时排序，当前使用红黑树这中树结构进行排序。迭代器总是以排好序的顺序访问每个元素
要使用TreeSet，必须能够比较元素
队列可以在尾部添加元素，在头部删除元素。双端队列可以在头部或尾部同时添加删除元素，不支持在队列中间添加元素。有Deque（double ended queue的缩写）接口，其有ArrayDeque、LinkedList类
优先级队列（PriorityQueue）可以按任意顺序插入，总是按排序顺序进行检索。使用的场景是任务调度，优先级最高的排在前。
优先级队列并没有对所有元素进行排序，而是使用了数据结构堆（heap），堆是一个可以自我调整的二叉树，执行添加、删除，最小元素会移动到根部
映射数据结构用来存放键值对
HashMap和TreeMap都实现了Map接口，HashMap快一些，对键进行了散列
更新映射项，当键不存在且首次更新时的解决方法如下：
1.counts.put(word, counts.getOrDefault(word, 0) + 1)
2.counts.putIfAbsent(word, 0);
counts.put(word, counts.get(word) + 1)
3.counts.merge(word, 1, Integer::sum)
映射视图的keySet是不是HashSet或TreeSet，而是实现了Set接口的其他类，可以像集合一样使用KeySet。对KeySet的迭代器调用remove()方法，会删除映射中的键和值
LinkedHashSet与LinkedHashMap可以记住元素项的顺序，当元素插入到表中，就会并入双向链表中
原文：https://www.cnblogs.com/minguo/p/10746720.html