Java核心技术读书笔记9-1 Java集合概述

1.Java集合概述

在最初的Java版本只为常用的数据结构提供了很少的一组类：Vector、Stack、HashTable、BitSet与Enumeration。
随着Java2（JavaSE 1.2）的推出，设计人员推出了一组功能完善优点清晰又易于学习的数据结构。

1.1 将集合的接口与实现分离
Java将数据结构具有的功能定义在接口中，而每种数据结构的不同实现方式定义在类中，这些类需要实现接口以此完成了数据结构特性与实现特性的分离，达到了更简单使用和灵活的效果。例如：LinkedList是链表类，由于它实现了List和Deque(Queue的子接口)接口，因此可以用它实现列表和队列两种逻辑结构。
在实际使用时，可以使用接口变量引用实际的集合类对象，
如List list = new ArrayList<>();
或者List list = new LinkedList<>();
这样，使用者就可以忽略具体的实现方式，而专心考虑集合的功能就可以。如果对于集合的操作需求有变化，那么也只要更改对象创建处的代码即可。

Java提供了很多Abstract开头的类，这些类转为类库实现着而设计用于实现自己的相关类。

1.2 Collection接口
该接口继承自Iterable接口，其两个基本方法为add和iterator。分别是添加元素与获得迭代器。

1.3 迭代器

for each循环可以遍历数组和实现了Iterable接口的对象。
forEachRemaining(element -> do something with element)可以更简单的通过一个lambda表达式对迭代器的每一个元素调用lambda表达式。例如

list.iterator().forEachRemaining(System.out::println); //快速遍历实现了Iterable接口的集合

对于迭代器，元素被访问顺序取决于集合类型。如果对ArrayList迭代，将是顺序访问元素。如果对HashSet迭代，元素同样可以全部访问到，但每次将按随机且无法预知的次序出现。
Java的迭代器可以认为是处于两个元素之间，当调用next时，迭代器越过下一个元素，并返回这个元素的引用。

这个操作与InputStream.read类似。

调用remove方法将返回上次调用next方法返回的元素。显然，你不能用刚刚构建的迭代器直接使用remove()方法。

1.4 泛型使用方法
使用Conllection与Iterator两个泛型接口，可以编写出适用于任何集合类型的实用方法。同时，想要编写一个集合类也可以扩展AbstractCollection类，该类包含一些集合通用操作方法的实现。

1.5 集合框架接口

List：数组和链表的实现方式不同将会带来不同操作性能上的很大差异。Java 4引入了一个标记接口RandomAccess。这个接口不包括任何方法，但可以用它来测试一个集合是否支持随机访问：
c instanceof RandomAccess

Set：Set不允许包含重复元素。相同元素调用hashCode方法会得到相同的散列码。

2.具体的集合

2.1 链表
在Java中，所有链表都是双向链表。因此可以使链表对get方法有微小的优化，若果查找索引大于size()/2就从列表的尾端开始搜索元素。

ListIterator extends Iterator，该接口支持反向遍历链表。
E previous()
boolean hasPrevious()

需要注意，迭代器的remove总是删除刚刚越过的元素，即先previous再remove删除的是迭代器右侧元素。

使用迭代器的add方法会将当前元素插入到迭代器的前面。add方法依赖于迭代器的位置。remove方法依赖于迭代器的状态。

        LinkedList list = new LinkedList<>();
        ListIterator it = list.listIterator(); // |
        it.add("1"); // 1 |
        it.add("2"); // 1 2 |
        System.out.println(it.previous()); //1 | 2
        it.add("2.5"); // 1 2.5 | 2
        System.out.println(it.next()); // 1 2.5 2 |
        it.add("3"); // 1 2.5 2 3 |

防止并发修改问题，每个迭代器维护有一个计数只可以对比当前集合的操作次数和自己的操作次数。若不同则会抛出一个异常。因此，在实际使用时可以为容器附加许多只读迭代器，再单独附加一个既能读又能写的迭代器。

链表计数只跟踪结构性修改：添加、删除。而不跟踪set操作。

2.2 数组列表
ArrayList用以取代Vector，因为Vector是线程同步的，可以由两个线程安全的访问。但对于只有一个线程访问Vector的情况，会在同步操作上耗费大量的时间。

2.3 散列集
对于散列集HashSet，其实现为采用拉链法解决散列冲突的散列表，每个列表被称为桶。散列集不会存储重复元素，且由于每个存储元素的位置由其散列码hash code经过散列函数得到（因此更改了元素的散列值会改变元素在set中的位置），所以直接输出元素，其顺序是无序且不可知的。
为了防止聚集，最好将桶数设置为一个素数（标准类库默认值为16，若提供值，则大小自动转化为最接近的2的下一个幂），桶数一般会设置为预计元素个数的75%~150%。若表太满则需要扩容再散列（rehashed），装填因子（load factor）决定了何时再散列（如默认值0.75表示超过了75%的位置已经含有元素需要再散列）。

2.4 树集
树集与散列集类似，不过树集由红黑树实现，是一个有序集合。可以按任意顺序将元素插入到集合中，在对集合进行遍历时，每个值都会自动按照排序后的顺序呈现。将元素添加到树集中要比添加到散列表慢（logn次比较），但检查重复元素时要比数组与链表快很多。与使用Arrays.sort排序数组类似，树集中的元素要么实现了Comparable接口，要么在构造数集时提供一个Comparator。
树集虽然有序且检查元素重复效率高插入开销也并没有那么大，但要求所有元素必须可比，这对于一些需求是很难满足的。

2.5 队列与双端队列
双端队列（Deque）支持在队列头部或尾部同时添加或删除元素。其可由ArrayDeque和LinkedList这两个实现了Deque接口的类实现。

对于实现栈（Stack），官方建议不要再使用Stack类，而是通过双端队列模拟。

2.6 优先级队列
优先级队列(priority queue)中的元素可以按照任意的顺序插入，却总是按照排序的顺序进行检索。即不误何时调用remove方法，总会会的当前优先级队列中最小的元素。优先级队列是用堆（heap）实现的，因此它并没有对元素进行排序，而是每次用迭代的方式调整这些元素。
同样队列中的元素要么实现了Comparable接口，要么在构造数集时提供一个Comparator。
使用优先级队列的典型场景，是不断获得队列中值最小或最大（传入反向的比较器）的元素。

3.映射（Key-Value）

Java类库对映射的两个通用实现：HashMap与TreeMap，和HashSet与TreeSet类似，都是对键进行处理(散列表与红黑树)，所以数据结构的选择依据也是类似。

Map的键不可以重复，同时只有HashMap的键可以为空，而HashMap和TreeMap的值都可以为空但两种映射都是线程不安全的。

对于Map可能会出现键为空的情况，这时若想根据键获取值可能还有判断是否为空。因此，可以使用getOrDefault(key, default)方法返回一个默认值。
对于Map的遍历可以采用forEach方法传入一个lambda表达式：map.forEach((k, v) -> do something)

3.1 更新value
更新value但可能当前map尚不存在对应的键值对，三种处理方式：

map.put(key, map.getOrDefault(key, 0) + 1); //若为空则返回一个默认值

map.putIfAnscent(key, 0); //不存在赋予默认值
map.put(key, map.get(key) + 1); 

map.merge(key, 1, Integer::sum); //null返回1，否则将1和get(key)结果作为参数调用sum返回计算结果

3.2 映射视图
集合框架不认为映射（map）本身是一个集合。但可以得到对应映射的视图（view）——这是实现了Collection接口或某个子接口的对象。map的视图有三种，分别是键集（Set）、值集合(Collection)以及键/值集(Set)。获取方法为：

Set keySet()
Collection values()
Set> entrySet()  

Map.Entry是实现了Map.Entry接口的类的对象，可以通过entry.getKey()与emtry.getValue()方法查看对应的键值。遍历entrySet()返回的集可以很好的遍历map。不过现在可以更好地通过forEach方法得到。
对于键集和条目集（entrySet），可以通过调用迭代器的remove方法将对应map中的元素删掉。但对于视图是不允许添加元素的。

3.3 弱散列映射与Java四种引用
从java 2(jdk 1.2)开始，java对于对象的引用分为四个级别，从强到弱分别是强、软、弱、虚引用。由于java的对象存储在堆中，长时间不适用会造成内存溢出，这就需要对对象进行回收，而对于不同引用级别的对象，涉及的垃圾回收方式也不同。
强引用，构建一个对象时，使用类型变量对其进行引用。存在该引用的对象即使发生内存溢出也不进行回收。

Employee e = new Employee(); //构建了一个对象，并用类型变量引用它，该引用是强引用。
e = null; //去除e的强引用，这个对象现在不存在任何引用，垃圾回收时会被回收。

Reference是下述三种引用类的超类，是一个抽象类，提供了一个T get()方法用以返回引用指向的对象（虚引用除外）。

软引用，使用SoftReference softRe变量引用的对象，若只有该引用，内存充足时不会进行回收，内存不足时将会回收。软引用建立时可以和一个引用队列联合使用，引用队列初始为空，当该引用指向的对象被回收时，jvm就会把该引用加入到队列中。

Employee e = new Employee(); //一个强引用
SoftReference softRef1 = new SoftReference<>(e); //再建立软引用（注意，是新增一个引用）
//SoftReference SoftReference= new SoftReference<>(e, rq); //和引用队列联合使用，引用对象回收时将SoftReference加入到引用队列中。
SoftReference softRef2 = new SoftReference<>(new Employee()); //只被一个软引用引用的对象，内存不足时将会回收。

弱引用，使用WeakReference weakRe变量引用的对象，若只有该引用，只要进行垃圾回收就会回收掉它。弱引用建立时可以和一个引用队列联合使用。

Employee e = new Employee(); //一个强引用
WeakReference weakRef1 = new WeakReference<>(e); //再建立弱引用（注意，是新增一个引用）
WeakReference weakRef2 = new WeakReference<>(new Employee()); //只被一个弱引用引用的对象，只要进行垃圾回收就会回收掉它。

虚引用，使用PhantomReference phanRe变量引用的对象，若只有该引用，只要进行垃圾回收就会回收掉它。虚引用建立时必须和一个引用队列联合使用。虚引用本身相当于无引用，你甚至不能根据虚引用获取其引用的对象，其存在的唯一目的就是跟踪引用的对象的回收状态。

        Employee e = new Employee(); // 强引用
        ReferenceQueue rq = new ReferenceQueue<>(); // 引用队列
        PhantomReference phanRe = new PhantomReference<>(e, rq); // 新增一个虚引用指向对象（实际目的为关联引用队列）
        System.out.println(phanRe.get()); // 返回null 在当前对象存在的情况下，你甚至都无法通过虚引用获取对象
        e = null; // 取消强引用
        System.gc();
        System.out.println(phanRe.isEnqueued());
        TimeUnit.SECONDS.sleep(6);
        System.gc();
        System.out.println(phanRe.isEnqueued());
        System.out.println(rq.poll()); // java.lang.ref.PhantomReference@7cca494b

一个关于引用的小例子：

        Employee e = new Employee(); // 强引用
        WeakReference weakReference = new WeakReference<>(e); // 新增一个弱引用指向对象
        System.out.println(weakReference.get()); // 会打印返回的Employee对象
        e = null; // 去除强引用，此时只剩弱引用指向对象。不加这一句表明对象依然被强引用（此时被一强一弱两个引用），不会回收
        System.gc(); // 建议gc进行垃圾回收
        System.out.println(weakReference.get()); // 已经被回收 打印null

弱散列映射WeakHashMap
理解完四种Java对对象的引用级别，理解其弱散列映射就容易许多了。WeakHashMap维护了一个ReferenceQueue，保存了所有存在引用的Key对象。在WeakHashMap中，所有key都是弱引用对象，没有外部强引用/软引用（或者缓存，如字符串池）指向map中的key时，key与其对应的value会被立即回收掉。然后WeakHashMap中存在一个expungeStaleEntries()方法，会将被回收掉的key值（由ReferenceQueue记录）对应的元素移除。expungeStaleEntries会在WeakHashMap对象取map容量，扩容和getTable时调用。

注意，key是弱引用但value不是，expungeStaleEntries会将对应的value置为null协助gc回收。
显然，WeakHashMap最好的应用是作为一种缓存使用。

3.4 链接散列集和映射（LinkedHashSet与LinkedHashMap）
这两种数据结构为元素(Set)与key(Map)建立了一个额外的双向链表，用这个链表可以记住每次插入元素项的顺序。
对于LinkedHashMap，它不仅支持按插入顺序排序key，还可以启用LRU算法（最近最少用），这时将按访问顺序对元素排序。使用get或put方法都会将受影响的元素从链表的当前位置删除然后插入到链表尾。
这需要使用public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)构造器，且最后一个参数置为true。

        LinkedHashMap map = new LinkedHashMap<>(5, 0.75f, true);
        map.put(1, "1");
        map.put(2, "2");
        map.put(4, "4");
        map.put(3, "3");
        map.put(5, "5");
        map.put(3, "3.4");
        String s = map.get(4);
        map.entrySet().iterator().forEachRemaining(System.out::println);

3.5 枚举集与映射（EnumSet与EnumMap）
EnumSet是一个枚举类型元素集的高效实现。由于枚举类型只有有限个实例，所以EnumSet内部用为位序列实现（数据结构为一个数组）。即值在集中，序列的相应位置为1。

EnumMap是一个键类型为枚举的映射。

3.6 标识散列映射IdentityHashMap
这个映射使用的hash值来自于System.identityHashCode即Object.hashCode方法，根据对象的内存地址作为hash code来存储元素。所以两个元素比较时使用的是==，而不是equals。

该类在实现对象遍历算法（如对象串行化）时非常有用。