读《Java核心技术卷I》有感之第9章集合

集合这一章，我个人的理解就是讲述了Java中对于经典数据结构的各种实现。这里的实现有别于STL中每个数据结构的具体实现，而是通过接口为骨架，结合各种相关的抽象基类和数据结构类所搭建起来的Java型数据结构。所以这一章的关键在于，理解每个原生接口的关系，以及它们内部的方法；理解每个集合类的继承与接口关系以及内部的方法实现，从而了解它们是怎么形成的。

所以这一章主要从宏观的概念来理解，每一种集合类，其实都是标准数据结构的一种，Java只是添加了一些特色功能，这里的关键不是摸清楚每个类的具体实现，而是将每个类与数据结构标准类的定义对应起来即可。至于Java集合中的方法调用，万物归宗，必然常用的都是数据结构定义本身的东西，在实际工作去理解即可（因为我学Java是为了用而不是刷题）。

9.1 Java集合框架

Java设计者以STL为参考基础自己搞了一套框架（集合接口框架和集合类框架），不得不说，搞的拓展性比STL好多了（毕竟STL的各个标准容器是不能被继承的，所以你想搞自己的容器就得参照STL重新写，换句话说就是疯狂自己造轮子）。

Java设计之初的几个数据结构有：Vector、Stack、Hashtable、BitSet与Enumeration接口。

9.1.1 将集合的接口与实现分离

这里是Java集合设计的核心关键，涉及到三个关键点：

在接口中定义集合所需实现的方法，而具体的集合类来“

可选的

”实现这些方法（实现接口就必须定义接口中的方法，这里的可选即表示集合API中某些可选操作，其表示了某些集合类在定义所实现的接口的某些方法时，并没有真正定义这个方法的含义，而是抛出UnsupportedOperationException异常。所以这种情况只有在调用了进行了可选操作的方法时，才会排除这个异常）。

public void add(int index, E element) { throw new UnsupportedOperationException(); }
定义集合类型时，通过具体的类来进行构造，通过接口类型来存放集合的引用（这样的好处是一旦发现需要修改存储类型时，修改构造器中的具体集合类的类型即可，不需要对于后面变量相关的所有代码进行改动）。

Set<String> set = new HashSet<>();
集合类框架中，Abstract开头的类（AbstractList、AbstractSet、AbstractQueue、AbstractMap）是为类库设计者而涉及的，当需要实现自定义的列表、集、队列和映射时继承上面的四种Abstract类即可。

9.1.2 Collection接口

这个接口是集合类的基本接口，包含几个关键方法，并实现了Iterable接口。Collection接口的主体以及两个基本方法，还有Iterable接口的实现如下：

public interface Iterable<T> 
{
    Iterator<T> iterator();

    default void forEach(Consumer<? super T> action) 
    {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }
    
    default Spliterator<T> spliterator() 
    {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

public interface Collection<E> extends Iterable<E>
{
	boolean add(E element);
	Iterator<E> iterator();
	...
}

9.1.3 迭代器Iterator

迭代器即Iterator接口，其主要包含以下4个方法：

public interface Iterator<E>
{
	boolean hasNext();
	
	E next();
	
	default void remove() 
	{ 
		throw new UnsupportedOperationException("remove");
	}
	
	default void forEachRemaining(Consumer<? super E> action) 
	{
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

Collection接口作为集合类的基本接口，实现了Iterable接口的意义如下：

要求实现者必须定义iterator()这个方法，即为任何集合都保证了迭代器的实现，从而标准类库中的任何集合都可以使用“for each”循环的写法；‘
实现了forEach方法，可以使用forEach方法在内部调用lambda表达式的方式实现集合的遍历操作（当然这种方法属于老方法明，现在都是推荐使用1中的方法）。

list.forEach(element->System.out.println(element))

迭代器Iterator本身的方法定义也有几个关键意义：

C++中的迭代器是根据数组索引建模的，可以实现迭代器的++以及–等操作，并且其查找操作与位置变量分离（即可以只进行迭代器的移动而不进行查找），所以C++的迭代器被认为直接指向元素本身。Java的迭代器是独立实现的，查找操作与位置变更紧密相连（即移动与查找相互伴随），所以

Java的迭代器被认为指向两个元素之间，当调用next时，迭代器就越过下一个元素，并返回刚刚越过的那个元素的引用

；
Java的迭代器

初始默认在首元素的左边（如果有首元素的话）

，所以未进行next移动时，当前迭代器未指向任何元素的引用，从而无法执行remove操作。同样的，当remove方法删除掉当前迭代器指向的引用后，无法再次调用remove，需要通过next更新当前迭代器引用后才能继续操作。所以，

next方法与remove方法的调用具有相互依赖性，remoave方法前必须调用一个next方法

。

9.1.4 泛型实用方法

Collection接口和Iterator接口都是泛型接口，它们在设计时会在其中声明许多的方法，所有实现这些泛型接口的类都需要提供这些方法的实现。但是实际情况下类设计者可能并不想提供这么多方法的实现（使用一部分即可达到想要完成的功能），所以Java类库又提供了各种Abstract类（比如AbstractCollection），这些Abstract类抽象化了某些基础方法，但是为很多借口中声明的方法提供了默认实现，便于类设计者的自定义功能。

（当然，SE 8之后通过在Collection、Map、List等接口中添加各种声明方法的默认实现即可完成上述功能。这里不得不吐槽一句，这么好的默认方法功能为嘛不早点加，还整这么多幺蛾子哈哈）

9.1.5 集合框架中的接口

Java集合框架为不同类型的集合定义了大量接口，这些接口之间有大量的继承关系，是Java集合类设计的骨架。

在这里插入图片描述

上面的图讲的很清楚了，Collection接口、Map接口、Iterator接口与RandomAccess是四个独立的根接口，尤其Collection接口与Map接口实现了数据结构相关的所有集合，其中有几个与传统数据结构不同的接口需要着重说明一下：

RandomAccess接口：不包含任何方法，用于测试一个集合是否支持高效的随机访问（即实现了高效随机访问的集合会实现该接口）；
ListIterator接口：一种双向运行迭代器，可以向前或向后移动，适用于双向链表（传统的Iterator是单向的）

if(c instanceof RandomAccess) 实现了高效随机访问 else 未实现高效随机访问;
SortedSet与SortedMap接口：提供用于排序的比较器对象（即将红黑树实现的集合类给这种类型的对象）；
NavigableSet与NavigableMap接口：SE 6开始引入的接口，在SortedSet/Map的基础上，包含了一些用于在有序的Set或Map中搜索和遍历元素的方法（这些方法在TreeSet和TreeMap集合类中具体实现，没有再单独设计两个类来实现，所以这两个接口中的方法理应仍处于SortedSet/Map中，只是不知道为什么又单独搞了两个接口）

9.2 具体的集合

Java库中的所有集合类，都是基于9.1.5节中的接口图为骨架，而设计出来的各种数据结构型集合类。其中后缀带Map的都是实现了Map接口的，没带Map后缀的都是实现了Collection接口的，其相关的表具体如下：

集合类型	描述
ArrayList	一种可以动态增长和缩减的索引序列
LinkedList	一种可以在任何位置高效的插入和删除操作的有序序列
ArrayDeque	一种用循环数组实现的双端队列
HashSet	一种没有重复元素的无序集合
TreeSet	一种有序集
EnumSet	一种包含枚举类型值的集
LinkedHashSet	一种可以记住元素插入次序的集
PriorityQueue	一种允许高效删除最小元素的集合
HashMap	一种存储键/值关联的数据结构
TreeMap	一种键值有序排列的顺序表
EnumMap	一种键值属于枚举类型的映射表
LinkedHashMap	一种可以记住键/值项添加次序的映射表
WeakHashMap	一种其值无用武之地后可以被垃圾回收器回收的映射表
IdentityHashMap	一种用==而不是equals比较键值的映射表

而所有类之间的继承关系如下，这里切记

Abstract类中是实现了一些方法的，并非所有的方法都是声明，它只是在定义类时前面被加了abstract修饰符而已

。（图里最右边的应该是ArrayDeque，这书好多错别字。。。）

在这里插入图片描述

当然，只有每个集合类的继承关系可不全，集合类在实现过程还涉及一些接口的实现，具体如下，注意图中的接口、抽象类和集合类的区别（当然这个图不全而且漏洞百出，比如没有Queue接口下的实现，以及新出的NavigableSet与NavigableMap接口等等，我也没找到更好的图，将就着看吧）。

在这里插入图片描述

从这里开始就是一个一个来的讲几个主接口下的集合类实现了，怎么说呢，这些东西其实了解数据结构本身都很好理解，因为本身这里的集合类就是为了实现数据结构本身，所以后面主要都是泛泛而谈，主要是Java中这个集合类实现时的一些特色或者说值得一提defined。

至于多数集合类都实现了的

Serializable接口

，这个接口用于保持对应的集合类能够序列化和反序列化，也就是把对象转换为字节序列文件的过程，和把持久化的字节文件数据恢复为对象的过程。

9.2.1 链表

这里的链表指LinkedList（特指双向链表），其类的声明如下，相关的特性如下：

特色：使用ListIterator迭代器来实现迭代器的双向移动，其他的都是标准双向链表的东西；
优点：查询需要遍历所以慢，增删只需前后连接所以快，其实就是双向链表本身的优点；
缺点：线程不安全也就是不同步，所以效率高。
（不知道Java的LinkedList设计的咋样，反正STL的list就是个垃圾，大数据存储时数据的随机存放导致数据查询效率缓慢的问题直接给他判了死刑，不知道Java中有没有对这个问题进行优化）

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

9.2.2 数组列表

ArrayList类封装了一个动态再分配的对象数组，相关的特征如下：

特色：不同步的Vector；
优点：查询有索引所以很快，增删要移动元素很慢，数组结构的通病；
缺点：因为线程不安全，效率高（其实觉得这么写挺搞笑的）。

public class ArrayList<E> 
	extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

Vector类就是个同步的，相关的特性如下：

特色：似乎没啥特色；
优点：查询有索引所以很快，增删要移动元素很慢，数组结构的通病；
缺点：因为线程安全，效率差（两个鬼才数组列表）。

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

9.2.3 散列集

这里简单说下P364页的那个命令行运行，因为我用的IDEA所以默认位置直接是
corejava10\corejava\v1ch09>
，并且Java的完整类名是“包名+类名”，所以书上写的这个命令行完全不能用，具体操作应该是：

在v1ch09/set里执行：javac SetTest.java
在v1ch09里执行：java set.SetTest < set/alice30.txt （这里我把txt文件放到了set文件下所以这么写）

HashSet类就是通过hashCode()的值来存数的，其不能存相同的值，相关的特性如下：

特色：没啥特色，数据结构的复制机器；
优点：哈希表的特点，无序所以查询快；
缺点：哈希表的缺点，无序所以排序要额外工作量，并且线程不安全，不可存重复值。

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

9.2.4 树集

TreeSet类的本质是红黑树（所以其存储类需要实现了Comparable接口），相关的特性如下：

特色：实现了Navigable接口，功能性增强；
优点：红黑树的特点，有序；
缺点：红黑树的缺点，有序所以效率低，并且线程不安全，不可存重复值。

public class TreeSet<E> 
	extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable

public interface NavigableSet<E> extends SortedSet<E>

public interface SortedSet<E> extends Set<E>

9.2.5 队列与双端队列

普通队列与双端队列均可以通过ArrayDeque与LinkedList实现，ArrayDeque相关的特性如下：

特色：没啥特色；
优点：未知；
缺点：未知。

public class ArrayDeque<E> 
	extends AbstractCollection<E>
	implements Deque<E>, Cloneable, Serializable

9.2.6 优先级队列

PriorityQueue中通过堆实现优先级排序（所以其存储类需要实现了Comparable接口），PriorityQueue相关的特性如下：

特色：没啥特色；
优点：未知；
缺点：未知。

public class PriorityQueue<E> 
	extends AbstractQueue<E>

9.3 映射

映射即所谓的map词典，用于存放键值对，C++中的键值对有专门的pair数据结构来表示，不过Java中似乎没有。

9.3.1 基本映射操作

两个通用的实现：HashMap和TreeMap，前者为散列表底层实现，与HashSet的优缺点相同；后者是红黑树底层实现，与TreeSet的优缺点相同。

public class HashMap<K,V> 
	extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable
    
public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

9.3.2 更新映射项

这里表现的意思是当key不存在时，调用get(key)会返回null，并出现一个NullPointerException异常。针对

不知道当前key是否已经在Map中存在的情况

，有以下三种补救方案：

counts.getOrDefault(key, 0);
counts.putIfAbsent(key, 0);
counts.merge(key, 1, Integer::sum);

9.3.3 映射视图

Java集合框架不认为映射本身是一个集合

（毕竟它连Collection接口都没有实现），不过可以得到映射的视图（view，即实现了Collection接口或子接口的对象），一共有三种视图，它们都在Map接口中声明：

键集 Set<K> KeySet()
值集合 Collection<V> values()
键值对集 Set<Map.Entry<K, V>> entrySet()

从视图的生成就可以看出端倪，这个东西就是对Map类型底层数据的部分或全部引用，

所以对视图的删除操作会直接导致底层Map数据的删除

。但是这也表征了

无法在视图上对Map类型底层数据进行数据的增加

，因为其只拥有对Map本身所有的这部分数据的读写能力，对于Map自身内存的控制是不存在的。

9.3.4 弱散列映射

这是一个特殊的映射Map，即WeakedHashMap，WeakedHashMap并没有继承 HashMap，这就意味着 WeakHashMap 必须自己重新实现一遍 HashMap 实现过的逻辑。这是因为 WeakedHashMap 中的引用是弱引用，所以有许多与 HasMap 不同的逻辑，需要再实现一遍。

public class WeakHashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>

Java中内存是通过GC自动管理的，GC会在程序运行过程中自动判断哪些对象是可以被回收的，并在合适的时机进行内存释放。GC判断某个对象是否可被回收的依据是，是否有

有效引用

指向该对象。如果没有有效引用指向该对象（基本意味着不存在访问该对象的方式），那么该对象就是可回收的（所以正常的集合都是在程序消亡的时候才会被回收）。这里的“有效引用”并不包括

弱引用

。也就是说，虽然弱引用可以用来访问对象，但进行垃圾回收时弱引用并不会被考虑在内，

仅有弱引用

指向的对象仍然会被GC回收（注意仅有，指的是WeakedHashMap内部的某个Key没有任何外部变量使用它，那么就是仅有WeakedHashMap自身的弱引用存在）。

9.3.5 链接散列集与映射

LinkedHashSet与LinkedHashMap两个类又是两个特殊的东西，用于记录元素项的访问顺序（LinkedHashSet由LinkedHashMap实现），其特色在于内部通过一个双向链表来存储元素的访问顺序，其中最先访问的元素在链表头，最后访问的元素在链表尾。这种对访问顺序的存储设计与实现操作系统中的“最近最少使用”原则直接适应，即可以根据内存大小与参数删除链表头的某些元素，这个过程甚至可以通过复写
removeEldestEntry(Map.Entry<K, V> eldest)
方法直接实现。

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
    
public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

9.3.6 枚举集与映射

EnumSet没有公共的构造器，但是可以使用EnumSet类中的各种静态工厂方法构造EnumSet类型的变量：

enum Weekday { MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY };
EnumSet<Weekday> always = EnumSet.allOf(Weekday.class):
EnumSet<Weekday> always = EnumSet.noneOf(Weekday.class):

public abstract class EnumSet<E extends Enum<E>> 
	extends AbstractSet<E>
    implements Cloneable, java.io.Serializable

EnumMap是一个以键类型为枚举类型的映射，它有自己的构造函数，不过在构造时必须在构造器中指定键的类型：

EnumMap<Weekday, Employee> personInCharge = new EnumMap<>(Weekday.class);

9.3.7 标识散列映射

IdentityHashMap和WeakedHashMap一样，都没有继承HashMap，所以其内部实现都重写了一遍。这个类的特色在于对于键的散列值并不是按照键本身的hashCode函数计算的，而是

直接通过最底层的System.identityHashCode方法来计算的，即通过内存地址计算散列码

，并且内部对键进行比较时，是使用经典的==符号，而不是equals方法。

（上面这种的方式保证了equals方法结果与散列码的互通性，在IdentityHashMap中，即使两个键的内容相同，它们由于内存地址的不同仍然被认为是两个不同的对象，从而实现所谓的“

相同Key值而不同Value值的存储

”）

public class IdentityHashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, java.io.Serializable, Cloneable

9.4 视图与包装器

视图说穿了就是

将集合类尤其是映射类转换为其他实现了Collection接口或Map接口的对象

，然后通过视图来对原映射类的底层数据进行操作，视图的默认权限是只能实现删除与查询操作，不能实现增补操作。所以视图并非是新建了一个对象，而是使用的原映射类的引用。

9.4.1 轻量级集合包装器

Collections.nCopies(n, anObject)
将返回一个实现了List接口的不可修改的对象，并给人一种包含n个anObject元素的错觉（也就是说这个视图引用的是n个anObject元素的一个对象）；

Collections.singleton(anObject)
返回一个实现了Set接口的视图对象，这个对象实现了一个不可修改的单元素集；

Collections.emptySet()
返回一个实现了Set接口的视图对象，这个对象里面没有元素；

9.4.2 子范围

建立视图并非需要完全获取全范围下的集合元素，也可以获取其中的部分范围即子范围。比如针对List类型的subList方法，针对SortedSet/SortedMap类型的subSet/Map、headSet/Map与tailSet/Map方法。

9.4.3 不可修改的视图

Collections中某些方法用于产生集合的不可修改视图，这些视图对现有集合增加了一个运行时检查。如果发现外界试图对集合进行修改，就抛出一个异常，同时这个不可修改集合仍处于未修改的状态。这些方法的名字都很接近，都是”unmodifiable”加上接口的名字从而实现的，比如：

Collections.unmodifiableCollection
Collections.unmodifiableList
...

特别注意，返回的集合都是接口形式，所以只能用接口中声明的方法。

9.4.4 同步视图

类库的设计者在设计集合类时，将其设置为不同步的，但是选择了通过视图机制来保证线程安全。比如Collections的静态方法synchronizedMap可以将任何一个映射表（如staff）转换成具有同步访问方法的Map（注意这里转换出来的是一个集合类，各项权限都是可以执行的）：
Map<String, Employee> syn_staff = Collections.synchronizedMap(staff);

9.4.5 受查视图

“受查”视图用来对泛型类型发生问题时提供调试支持，在Collections类中存在checkedList等近似的方法将一个List接口对象（如strings）转换为安全列表：
List<String> safeStrings = Collections.checkedList(strings, String.class);

9.4.6 关于可选操作的说明

可选操作在最开始的就讲过了，理论上实现接口就必须定义接口中的方法，这里的可选即表示集合API中某些可选操作，其表示了某些集合类在定义所实现的接口的某些方法时，并没有真正定义这个方法的含义，而是抛出UnsupportedOperationException异常。所以这种情况只有在调用了进行了可选操作的方法时，才会排除这个异常。

public void add(int index, E element) { throw new UnsupportedOperationException(); }

9.5 算法

这里的算法基本都是声明和定义在Collections类中，与C++的algorithm头文件有异曲同工之妙。

9.5.1 排序与混排

Collections类中的sort方法，以及List接口中的sort方法，都是传实现了List接口的集合，并可以传比较器的（书中的意思好像是集合类中排序算法用的归并排序）。

9.5.2 二分查找

Collections类中的binarySearch方法，传实现了List接口的集合，查找的元素，并可以传比较器（值得一提的是，如果传入的对象底层是数组实现，二分查找才有效果，否则采用双向链表底层实现则会将二分查找退化为线性查找）。

9.5.3 简单算法

鼓励尽量使用Collections类中的方法来实现操作，这里特别注意方法的形参往往是需要实现List接口或Collection接口的，其他类型的集合类，尤其是Map接口系列下的，使用时要注意格式的转换。

9.5.4 批操作

这里的意思是注意类似removeAll这样的方法，会对所传入的参数进行成批次的统一删除，或者其他操作。

9.5.5 集合与数组的转换

一般数组与集合的转换都是List接口与数组之间的转换，相关的代码如下：

数组转换为集合
String values[] = ...;
HashSet<Stirng> staff = new HashSet<>(Arrays.asList(values));

集合转换为数组（toArray方法返回的数组是一个Object[]数组，不能改变它的类型）
String values = staff.toArray(new String[0]);

9.5.6 编写自己的算法

书本的主旨就是建议不要在算法中写具体的类型，而是尽可能是使用集合的接口，比如ArrayList、HashSet类型等等都可以使用Collection接口来代替。

9.6 遗留的集合

即在集合框架创造之前的遗留集合们。

9.6.1 Hashtable

其作用与HashMap一样，通过底层数组+链表实现，但是无论key还是value都不能为null，实现同步的方式是修改数据时锁住整个类，可见效率低下。书本的建议是不用同步时使用HashMap，需要同步时使用ConcurrentHashMap。

9.6.2 枚举

遗留集合通过Enumeration接口对元素序列进行遍历，其内部有两个方法，分别是hasMoreElements和nextElement，与现在的Iterator接口中的hasNext方法和next方法十分类似。

9.6.3 属性映射

实现属性映射的平台被称为Properties，而属性映射是指键与值都是字符串；表可以保存到一个文件中，可以从文件中加载；使用一个默认的辅助表的映射结构。

9.6.4 栈

Stack类继承于Vector类，直接导致了这个类存在本不属于它的insert和remove方法。而现在LinkedList既是栈，又是堆，还是双向队列，相关的数据结构一般都会使用LinkedList来作为构造类型，而实际类型根据情况使用接口即可。

9.6.5 位集

BitSet类用于存放位序列，其将位集包装在了字节里，所以使用位集要比使用Boolean对象的ArrayList更加高效。如果需要高效地存储位序列（例如标志）就可以使用位集。

原文链接：https://blog.csdn.net/yzt629/article/details/106963295