接口
- 集合有两个基本接口 Collection 和 Map
- List 是一个有序集合。元素会增加到容器中的特定位置。
- Set<E>集。Set 接口等同于 Collection 接口，不过其方法的行为有更严谨的定义，不能添加重复的对象
- Iterator<E>
- iterator.forEachRemaining(element -> do something with element);
- iterator.next()，当调用 next 时，迭代器就越过下一个元素，并返回刚刚越过的那个元素的引用。
- iterator.remove()，将会删除上次调用 next 方法时返回的元素。
it.next(); // skip over the first element
it.remove(); // now remove it
- ListIterator 定义了一个方法用于在迭代器位置前面增加一个元素。void add(E element)
- RandomAccess 为标记接口，不包含任何方法。可以用来测试一个特定的集合是否支持高效的随机访问。
if (c instanceof RandomAccess){
use random access algorithm
else{
use sequential access algorithm
}
类
- ArrayList 可以动态增长和缩减的索引序列
- LinkedList 可以在任何位置进行高效地插人和删除操作的有序序列
- ArrayDeque 用循环数组实现的双端队列
- HashSet 没有重复元素的无序集
- TreeSet 有序集
- EnumSet 包含枚举类型值的集
- LinkedHashSet 可以记住元素插人次序的集
- PriorityQueue 允许高效删除最小元素的集合
- HashMap 存储键 / 值关联的数据结构
- TreeMap 键值有序排列的映射表
- EnumMap 键值属于枚举类型的映射表
- LinkedHashMap 可以记住键 / 值项添加次序的映射表
- WeakHashMap 其值无用武之地后可以被垃圾回收器回收的映射表
- IdentityHashMap 用 = 而不是用 equals 比较键值的映射表
链表
Java 程序设计语言中， 所有链表实际上都是双向链接的。LinkedList
注意iterator的位置（“光标”）
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("this");
linkedList.add("is");
linkedList.add("a");
linkedList.add("sentence");
ListIterator<String> iterator = linkedList.listIterator();
while (iterator.hasNext()){
if (iterator.next() == "sentence")
iterator.add("complete");
}
- 用“ 光标” 类比时要格外小心。remove 操作与 BACKSPACE 键的工作方式不太一样。在调用 next 之后， remove 方法确实与 BACKSPACE 键一样删除了迭代器左侧的元素。但是， 如果调用 previous 就会将右侧的元素删除掉， 并且不能连续调用两次remove
- add 方法只依赖于迭代器的位置， 而 remove 方法依赖于迭代器的状态。
- 如果在某个迭代器修改集合时， 另一个迭代器对其进行遍历， 一定会出现混乱的状况。链表迭代器的设计使它能够检测到这种修改。 如果迭代器发现它的集合被另一个迭代器修改了， 或是被该集合自身的方法修改了，就会抛出一个ConcurrentModificationException 异常。
数组列表
List 接口用于描述一个有序集合，并且集合中每个元素的位置十分重要。 访问元素两种方法：
- 迭代器。适用于链表
- get和set方法随机访问。适用于数组
ArrayList 数组列表，封装了一个动态再分配的对象数组。比较 Vector，其方法都是同步的，一个线程访问 Vector, 代码要在同步操作上耗费大量的时间。在不需要同步时使用 ArrayList, 而不要使用 Vector。
散列集
链表和数组可以按照人们的意愿排列元素的次序。但是如果想要査看某个指定的元素， 却又忘记了它的位置， 就需要访问所有元素， 直到找到为止。所以，数据结构散列表上场啦
散列表为每个对象计算一个整数， 称为散列码（hash code)，是由对象的实例域产生的一个整数。
在 Java 中，散列表用链表数组实现。每个列表被称为桶 （ bucket ) 。
对象位置的计算：计算它的散列码， 然后与桶的总数取余。
例如， 如果某个对象的散列码为 76268, 并且有 128 个桶， 对象应该保存在第 108 号桶中（ 76268除以 128余 108 )直接插入到桶中即可。 不幸的是，当桶被占满时，发生散列冲突（ hash collision) ，需要用新对象与桶中的所有对象进行比较，査看这个对象是否已经存在 。
通常， 将桶数设置为预计元素个数的 75% ~ 150%。
如果散列表太满， 就需要再散列 （rehashed)。 如果要对散列表再散列， 就需要创建一个桶数更多的表，并将所有元素插入到这个新表中， 然后丢弃原来的表。装填因子（ load factor) 决定何时对散列表进行再散列。如果装填因子为 0.75 (默认值，) 而表中超过 75%的位置已经填人元素， 这个表就会用双倍的桶数自动地进行再散列。
散列表可以用于集Set中，Set的add方法首先在集中查找要添加的对象，如果不存在才添加进去。
散列集迭代器将依次访问所有的桶。 由于散列将元素分散在表的各个位置上，所以访问它们的顺序几乎是随机的。只有不关心集合中元素的顺序时才应该使用 HashSet。
可以看到HashSet实际就是HashMap
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
树集
TreeSet 比散列集有所改进，是有序集。实现使用的是红黑树。
SortedSet<Item> parts = new TreeSet<>();
parts.add(new Item("Hello", 1));
parts.add(new Item("This", 2));
parts.add(new Item("Is", 3));
NavigableSet<Item> sortByDescription = new TreeSet<>(
Comparator.comparing(Item::getDescription));
sortByDescription.addAll(parts);
队列与双端队列
支持在头部/尾部添加或删除元素。不支持在队列中间添加元素。ArrayDeque和LinkedList都提供了双端队列
优先级队列
priorityQueue 可以按照任意的顺序插入元素。优先级队列并没有对所有的元素进行排序，却总是按照排序的顺序进行检索。使用的数据结构为堆。堆是一个可以自我调整的二叉树，对树执行添加 （ add) 和删除（remove) 操作， 可以让最小或最大的元素移动到根，而不必花费时间对元素进行排序。
迭代不是按照元素的排列顺序访问。
而无论何时调用 remove 方法，总会获得当前优先级队列中最小的元素。
可以指定比较器进行排序。
PriorityQueue<Item> itemPriorityQueue = new PriorityQueue<>(Comparator.comparing(Item::getPartNumber));
itemPriorityQueue.addAll(parts);
映射
键-值对。HashMap 和 TreeMap
- 散列映射对键进行散列。
- 树映射用键的整体顺序对元素进行排序， 并将其组织成搜索树
- 散列或比较函数只能作用于键。
- 与集一样， 散列稍微快一些， 如果不需要按照排列顺序访问键， 就最好选择散列
- 设值时候需要之一NullPointerExp情况
HashMap<String, String> hashMap = new HashMap<>();
hashMap.putIfAbsent("word", "");
hashMap.put("word", hashMap.get("word") + "string");
hashMap.put("word", hashMap.getOrDefault("word", "defaultStr"));
hashMap.merge("word","defaultStr",String::concat);
映射视图
键集、值集合、键/值对集。
Set<String> hashMapKeySet = hashMap.keySet();
Collection<String> hashMapValues = hashMap.values();
Set<Map.Entry<String,String>> hashMapEntrySet = hashMap.entrySet();
遍历键值对集更快速方法：
hashMap.forEach((k,v) -> {
// do sth. with k v
});
弱散列映射
假定对某个键的最后一次引用已经消亡，不再有任何途径引用这个值的对象了。为什么垃圾回收器不能够删除它呢？答：垃圾回收器跟踪活动的对象。只要映射对象是活动的，其中的所有桶也是活动的， 它们不能被回收。
WeakHashMap 当对键的唯一引用来自散列条目时， 这一数据结构将与垃圾回收器协同工作一起删除键 / 值对。
机制：WeakHashMap 使用弱引用保存键。如果某个对象只能由 WeakReference 引用， 垃圾回收器仍然回收它，但要将引用这个对象的弱引用放入队列中。一个弱引用进人队列意味着这个键不再被他人使用， 并且已经被收集起来。于是， WeakHashMap 将删除对应的条目。
链接散列集与映射
LinkedHashSet LinkedHashMap 记住插入元素的顺序。
访问顺序对于实现高速缓存的“ 最近最少使用” 原则十分重要。
枚举集与映射
EnumSet 枚举类型元素集。
可以使用 Set 接口的常用方法来修改 EnumSet。
EnumSet<Weekday> weekdays = EnumSet.allOf(Weekday.class);//返回一个包含给定枚举类型的所有值的集。
EnumSet<Weekday> none = EnumSet.noneOf(Weekday.class);//返回一个空集，并有足够的空间保存给定的枚举类型所有的值
EnumSet<Weekday> workday = EnumSet.range(MONDAY, FRIDAY);//返回一个包含 from 〜 to 之间的所有值（包括两个边界元素）的集
EnumMap 是一个键类型为枚举类型的映射。
视图
方法返回一个包装了接口的对象。这种对象集合称为视图。
获取不可修改的视图
视图的更改器方法抛出一个 UnsupportedOperationException。
Collections 还有几个方法， 用于产生集合的不可修改视图。运行时执行检查，如果发现试图对集合进行修改， 就抛出一个异常，同时这个集合将保持未修改的状态。
Collections.unmodifiableCollection(parts);
Collections.unmodifiableList(linkedList);
Collections.unmodifiableSet(parts);
Collections.unmodifiableSortedSet(parts);
Collections.unmodifiableNavigableSet(sortByNumber);
Collections.unmodifiableMap(hashMap);
Collections.unmodifiableSortedMap(hashMap);
Collections.unmodifiableNavigableMap(hashMap);
视图只是包装了接口而不是实际的集合对象， 所以只能访问接口中定义的方法。不可修改视图并不是集合本身不可修改。仍然可以通过集合的原始引用（在这里是 hashMap / parts / linkedList)对集合进行修改。
视图 unmodifiableCollection 返回的集合，它的 equals 方法不调用底层集合的 equals 方法，继承的是Object 类的 equals 方法，检测两个对象是否是同一个对象。以同样的方式处理 hashCode 方法。
视图 unmodifiableSet 类和 unmodifiableList 类却使用底层集合的 equals 方法和hashCode 方法。
同步视图
视图的方法同步。如果一个线程试图将元素添加到散列表中，同时另一个线程正在对散列表进行再散列，其结果将是灾难性的。
类库的设计者使用视图机制来确保常规集合的线程安全， 而不是实现线程安全的集合类。
Map<String, Item> map = Collections.synchronizedMap(new HashMap<String,Item>());
便可以多线程访问map对象，get 和 put都是同步操作
受查视图
用来对泛型类型发生问题时提供调试。插入一个错误类型的元素，视图的方法拋出一ClassCastException。
Collections.checkedList(strings， String.class);
