2020/08/24
2020/8/30
集合框架的基本设计
最初的Java只对最常用的数据结构提供了一些类和接口：Vector，Stack，Hashable，BitSet，Enumeration（接口）。他们的具体实现和功能之后再说。之后设计人员设计了新的框架，规模小且易于学习，而且又有STL率先提出的“泛型算法”那样的优点。
集合框架的特性
接口与实现分离
Java集合类库将接口与实现分离，也就是说，不需要关注类中方法的具体实现，而只要通过接口回调的方式来使用即可。
例如以下：
public interface queue<E> {
void add();
E remove();
int size();
}//虚构的一个最简单的接口
public class LinkedListQueue implements queue<E>{
private Link head;
private Link tail;
LinkedListQueue(){};
public void add(E element){};
public E remove(){};
public int size(){};
}
queue<customer> expressLane = new LinkedListQueue();//接口回调
expressLane.add(new customer("harry"));//只要知道接口中的方法即可，不需要在意具体的实现和数据结构
Collection接口
在Java类库中，所有集合类的基本接口是Collection接口，（Collections类是工具类，一个工具包）。这个接口有一些基本方法和许多实用的方法：
public interface Collection<E>{
boolean add(E element);
Iterator<E> Iterator;
int size();
boolean isEmpty();
boolean contains(Object obj);
boolean containsAll(Collection<?> c);
boolean equals(Object other);
boolean remove(Object obj);
void clear();
Object[] toArray();
……
}
迭代器
Iterator接口有四个方法：
public interface Iterator<E>{
boolean hasNext();
E next();
void remove();
default void forEachRemaining(Consumer<? super E> action);
}
因为Collection接口中有个返回迭代器iterator的方法，通过迭代器对象的next()方法，就可以获得集合中的下一个对象元素。但是要注意的是，如果指针已经到了最后一个元素，再使用next会报一个NoSuchElementException的异常，因此必须在每次next使用hasNext()方法来判断。
Collection c = ...;
Iterator<String> i = c.iterator();
while(i.hasNext()){
String element = i.next();
......
}
remove()方法要注意的是，删除的是已经查看过的元素，也就是说，删除的是指针前一个元素。由于一些特性，在调用remove()方法前，必须调用next()方法，否则会抛出一个异常IllegalStateException。例如下面的调用时错误的。
remove();
remove();
forEachRemaining()方法可以用来处理lambda表达式，对其中所有的元素都进行操作，例如：
iterator.forEachRemaining(element -> element-1);
“for each”循环可以使用在有实现Iterable接口的对象中，这个接口只有一个抽象方法Iterator<E> iterator()；
我觉得这里可以理解为，只要有这个方法，就能采用“for each”循环。
Collection<String> c = ...;
for (String element:c){
......
}
注释：本来也可以使用Enumeration接口来做迭代器接口，但是因为这个接口中方法的名字太长因此重新设计了新接口
Java的迭代器采用了一种我还不知道的操作，并不是按照数组索引建立的，因此不能向前或者根据索引来查找，它的查找操作与位置变更紧密耦合（啥意思？），每查找一个元素就“擦除”前一个元素。
泛型实用方法
因为Collection和Iterator接口都是泛型接口，因此就方便我们编写一些用来处理任何集合类型的实用方法。
例如可以编写一个泛型方法来判断任意一个集合类型的对象中是否包含了一个元素。
public static <E> boolean contains(Collection<E> c, Object obj){
for (E element:c){
if (element.equals(obj)) return true;
}
return false;
}
Colleation中包含许多抽象方法，因此如果要对Collection进行实现来编写自己的集合，就非常麻烦，因此提供了一个抽象类AbstractCollection，这个类实现了一部分例行方法，保持size和iterator为抽象方法，因此使用者就不需要编写那些东西，只需要继承抽象类，实现抽象方法，重写一些方法即可。
集合框架中的接口
有两个基本接口：Collection和Map
Map与集合不同，Map是存放一一对应的键值的表，用V put(K key, V value)方法来增加元素，用V get(K key)来查找。
List是有序集合，可以有两种访问方式：1，随机访问（random acess）2，迭代器访问。要注意的是链表对于随机访问的效率很差，因此引入了一个标记接口RandomAcess，可以用来测试一个特定的集合是否支持高效的随机访问，使用方法如下：
if (c instanceof RandomAcess){
//使用随机访问
}
else{
//使用迭代器
}
ListIterator接口是Iterator接口的一个子接口，它增加了一种方法void add(E element)。
Set接口等同于Collection，对其实现时需要更严格的定义，例如add和equals等。单独设立一个Set接口是从接口回调角度考虑的。
SortedSet和SortedMap接口会提供用于排序的比较器对象，这两个接口定义了，可以得到集合自己视图的方法。
具体集合
类
List：
数组列表（ArrayList，Vector）：
用数组作为内部实现，其特点是每一次增删操作都需要改变这个元素之后所有元素的位置，时间复杂度为O(n)；但是查改操作是根据数组索引，因此效率很高，时间复杂度为O(n)。
ArrayList和Vector的区别在于，Vector类的所有方法都是同步的，也就是线程安全的，但是同步操作是需要时间的，也就是说，如果不需要同步操作，最好使用ArrayList类。
链表（LinkedList）：
用链接（link）作为存储单元，每个元素存储在链接对象中，每个链接对象中还存放着下一个链接的引用（在Java中，所有链表都是双向链表，也存放着上一个链接的引用）
链表是一个有序集合，使用add方法可以把对象添加到链表的尾部，如果要添加到链表的中间：
虽然有add(int i，E element)等依靠索引的方法，但是要注意，一般不会使用，尤其是在循环中就不要使用，没有缓存效率很低。
所以有了ListIterator接口：
public interface ListIterator<E> extends Iterator<E>{
void add(E element);
void set(E element);
boolean hasPrevious();
E previous();
int nextIndex();
int previousIndex();
...
}
也就是说，在链表中间添加元素，要用ListIterator接口中的add方法，add方法总会在指针的左侧添加元素。
要注意的是，remove()方法，与迭代器的状态也有关系，如果调用了previous再remove，就会将指针右侧的元素删除。
如果同时有多个迭代器对一个对象进行读取，不会出现异常，但是如果其中有迭代器进行增删，后面的迭代器就会抛出一个ConcurrentModificationException异常，注意，set操作不会抛出异常，也就是说，只关注结构性修改。
集Set
有时候，并不需要关心元素在集合中的位置，只关心集合中的元素，就可以使用散列表，无需多余的浪费。
散列集（HashSet）
散列表（hash table 也就是哈希表）对列表中的每个对象计算出一个整数-散列码（hash code 也叫哈希码）。是根据对象的实例字段来计算的。
在Java中散列表用链表数组实现，如下图
数组中每个元素叫做桶（bucket），桶中存放着一个链表。散列表进行存放的时候，先计算元素的散列码，然后用散列码向桶的数量除余，得到的余数，就是要存放的桶的索引。
可以看到，会出现不同的元素放到同一个统中的情况，这种情况叫做散列冲突（hash collision），这时就要比较两个对象是否相同。
如果许多元素放入同一个桶，那就会影响散列表的查找效率，因此需要好的散列函数。
同时，如果知道最终有多少个元素要插入到散列表中，就可以设置桶数来提高性能。通常将桶数设置为总元素个数的75%~150%。
不知道总个数，当散列表太满，就会扩充桶数，进行再散列（rahashed）。装填因子（load factor）0.75表示，当表填满75%以上就会再散列。
树集（TreeSet）
是一个有序集合，可以以任意顺序插入元素，但是输出的是有序的顺序。
TreeSet是用一个树数据结构完成的（目前使用的是红黑树（red-black tree））。
因此添加一个数据时，TreeSet会比HashSet慢，但是查找更快。
元素必须实现Comparable接口，或者构造集时提供一个Comparator对象。但是并不是所有的类都能写出一个好的比较器。
优先队列（PriorityQueue）
使用了堆这个数据结构，同样需要一个比较器。
可以高效的删除最小元素。
映射Map
2020/8/31
映射的特点是：元素是键值对，不存在相同的键，每个键都对应一个值。
散列映射（HsahMap）
对键进行散列，通过查找键来获得与之相关联的值。
使用如下：
Map<String,Employee> staff = new HashMap<String, Employee>();
Employee harry = new Employee("Harry Hacker");
staff.put("1234",harry);//添加元素
String id = "1234";
Employee h = staff.get(id);//查找
Employee h = staff.getOrDefault(id, new Employee(""));//设定默认值
staff.forEach((k,v) ->
System.out.println("key="+k+"vaule="+v));//用lambda迭代处理
更新映射条目，例如更新让表中的word对应的值加一：
counts.put(word,counts.get(word)+1);//存在一个问题，可能没有word
counts.put(word,counts.getOrDefault(word,0)+1);//缺点是多次进行效率不高
counts.putIfAbsent(word,0);//如果没有word，或者映射到null，就会执行
counts.put(word,counts.get(word)+1);
couns=ts.merge(word,1,Integer::sum);//使用lambda
说一下merge方法，这个是Map中的一个抽象方法
default V merge(K key, V value, BiFunction<? super V,? super V, ? extends V> remappingFunction)
如果key与一个非null值v相关联，将函数应用到v和value，将key与结果相关联，或者如果结果为null，则删除这个键，否则，将key与value相关联，返回get(key)。
映射视图，有三种，键集，值集，键/值对集。使用下面的方法：
Set<K> keySet()
Collection<V> values()
Set<Map.Entry<K,V>> entrySet()
keySet方法返回的并不是常见的HashSet和TreeSet，是一个自己编写的实现了Set接口的类，因此可以使用Set接口中的方法。
因为，Map接口没有继承Iterable接口，所以不能直接使用迭代器和“for each”语句，需要先获得相应的视图，再使用迭代。如下
for(Map.Entry<String,Employee> entry : staff.entrySet){
String k = entry.getKey();
Employee = entry.getValue();
do something with k,v
}
也可以使用forEach方法
map.forEach((k,v) -> {do something with k,v})
弱散列映射（WeekHashMap）
假如整个程序中都不会用到表中的某个键/值对，那么这个键/值对就是多余，应该删去。但是散列映射并不会自动删除，因此可以使用弱散列映射，这个数据结构将与垃圾回收器协同工作一起删除键/值对。
链接散列集与映射（LinkedHashSet和LinkedHashMap）
如图，链接散列表可以记住插入元素的顺序，可以使用插入顺序或者访问顺序来迭代处理映射条目。
默认的构造是按照插入顺序来的，如果要使用访问顺序就需要调用
LinkedHashMap<K,V>(initialCapacity, loadFactor, true)
访问顺序的意思就是，每当使用get或者put，受影响的那个元素就会删除并放到链表尾部，也就是说，使用最频繁的会提出来，而频率较低的，之后就可以删除。
枚举集与映射
用来存放枚举集的
标识散列映射
类IdentityHashMap有特殊的用途。这个类中，键的散列值是用System.identityHashCode计算的，在两个对象比较时，这个类使用==，而不使用equals。
也就是说，不同的键对象即使内容相同，也被视为不同的对象。在实现对象遍历算法（如对象串行化）时，非常有用，可以用来跟踪哪些对象已经被遍历过（没看懂）。
树映射（TreeMap）
根据键的顺序构造搜索树
视图与包装器
什么是视图（view）
前面有提到过，HashMap需要用视图来进行迭代，例如使用ksySet返回一个实现了Set接口的类对象，看起来是重新构造了一个新的集，但事实上并不是，可以通过操纵这个集（set）来操控原映射，这样的集合叫做视图（view）
小集合（包装器）
Java9引入了一些静态方法，可以生成给定元素的列表，以及给对键值对的映射
List<String> names = List.of("a","b","c");
Set<Integer> numbers = Set.of(2,3,5);
Map<String,Integer> scores = Map.of("a", 2, "b", 3, "c", 5);
对于Map接口，有一个静态方法ofEntries，能接受任意多个Map.Entry<K,V>对象（可以用静态方法entry来创建这些对象）。例如
import static java.util.Map.*;
...
Map<String, Integer> scores = ofEntries(
entry("a", 2),
entry("b", 3),
entry("c", 5)
);
这些集合对象都是不可修改的，否则会抛出一个UnsupportedOperationException异常。
子范围
可以为很多集合建立子范围视图，如下
List<Employee> group2 = staff.subList(10,20)
这样可以获取源列表的的第10到19索引的一个视图，通过对这个视图进行任何操作，都会自动反映到整个列表。
有序集（SortedSet）和有序映射（SortedMap）都可以生成子范围视图
不可修改视图
顾名思义，一旦修改，就会抛出异常
可以用Collections.unmodifiablexxx来获得。
同步视图
如果从多个线程访问集合，就必须保证集合不会被意外破坏。
可以使用视图机制来确保常规集合是线程安全的。
没有实现线程安全的集合就要使用Collestions中的静态方法，synchronizedMap将任意一个映射转换成又同步访问方法的Map
例如
var map = Collections.synchronizedMap(new HashMap<String, Employee>());
这样这个映射的put，get等方法都是同步的，必须等一个线程完全结束，另一个线程才能调用另一个方法
Collections工具类的使用，详情看api文档。
算法
泛型算法
泛型算法的优点就是，算法只需要实现一次。
例如有个找到最大的元素的简单算法，一般来说，对于数组和链表会有不同的实现，但是在Java类库中，因为都实现了Collection接口，而且在找到最大元素的过程中，都只要遍历一遍列表，因此都可以采用迭代器来遍历找到最大元素。
也就是说，可以Collection层面就实现这个算法，从而减少重复编写。
排序与混排
可以使用Collections中的sort方法对List进行排序，或者List接口中的sort方法，如下
var staff = new LinkedList<String>();
fill...
Collections.sort(staff);
staff.sort(Comparator.comparingDouble(Employee::getSalary));
staff.sort(Comparator.comparingDouble( Employee::getSalary ).reverseOrder());
二分查找
Collections.binarySearch(c, element [, comparator])
简单算法
Collection中包含了一些有用的简单算法，具体看api文档。
批操作
很多操作会“成批”的复制或删除元素，例如
coll1.removeAll(coll2);
coll1.retainAll(coll2)；//和上面相反，会删除所有未在coll2中出现的元素
如果要找到两元素的交集就可以使用retainAll方法。
也可以对 视图 进行批操作，例如
staffMap.keySet().removeAll(terminatedIDs);
//在staffMap的键视图中，删除那些不需要的id，就可以在原映射中删除那些id。
遗留集合
就是现在一般不用的集合
HashTable类
作用跟HashMap一样，而且是线程安全的。现在一般不用。
属性映射（property map）
属性映射是一种特殊类型的映射结构，它有下面3个特性：
·键与值都是字符串
·这个映射可以很容易地保存到文件以及从文件加载
·有一个二级表存放默认值
实现的类是Properties。
栈（Stack）
Java中的栈扩展了Vector类，使用push和pop来添加删除元素。
位集（BitSet）
如果需要高效的存储位序列，就可以使用位集。
