《Java核心技术》阅读笔记（二）- 泛型、集合
泛型程序设计
Generic programming意味着代码可以被很多不同类型的对象所重用
提供类型参数（type parameters）解决了继承程序设计中的强制转换的安全性、可读性问题
基本概念
类
泛型类（generic class）：具有一个或多个类型变量的类。
定义：public class Pair
类型变量指定方法的返回类型以及域和局部变量的类型
- E 集合的元素类型
- K、V 表的关键字与值的类型
- T/U/S 任意类型
用具体类型替换类型变量可以实例化泛型类型，泛型类可看作普通类的工厂
方法
定义：public static T getMiddle(T… a)
调用：ArrayAlg.getMiddle（可省略<类型参数>，编译器会自行推断，有时会提示错误）
类型限定
类或方法对类型变量加以约束
表示T是绑定类型的子类型
一个类型变量或通配符可以有多个类型限定：
T extends Comparable & Serializable
（限定中至多有一个类）
原理
类型擦除
对于虚拟机，编译器提供相应的原始类型（删去类型参数后的名字），erased perameter type，替换为限定类型（无限定类型的变量用Object，多个限定的用首个，应将标签接口放到限定后面）
翻译泛型方法
方法擦除带来的问题（子类继承泛型方法的父类）：
- 类型擦除与多态发生冲突
解决：编译器合成桥方法（方法中调用子类新参数类型方法） - 返回类型更加严格的问题
解决：编译器合成桥方法（虚拟机，用参数类型和返回类型来确定一个方法，编译器产生仅有返回类型不同的两个方法的字节码，虚拟机能够正确处理）
示例：DateInterval extends Pair ，覆盖setSecond，getSecond方法
使用：javac命令编译DateInterval类，然后执行javap -private DateInterval命令反编译，可看到编译器合成的桥方法。
注：桥方法的其他应用——覆盖方法时可以指定更严格的返回类型。
翻译泛型表达式
方法调用与存取泛型域时，编译器插入强制类型转换。
调用遗留代码可能产生警告，可用注解@SuppressWarnings(“unchecked”)使其消失
小结
- 虚拟机中没有泛型，只有普通的类和方法。
- 所有的类型参数都用它们的限定类型替换。
- 桥方法被合成来保持多态。
- 为保持类型安全性，必要时插人强制类型转换。
使用限制
大部分是由类型擦除引起
- 不能用基本类型实例化类型参数
- 运行时类型查询只适用于原始类型
- 不能创建参数化类型的数组（声明变量是合法的）
类型擦除，可能会将不相关的不同类型参数的实例添加到同一个数组中，引起内部逻辑错误； - varargs警告
参数个数可变的方法传入泛型类型的实例。规则放松，但会警告，需要添加@SafeVarargs或者@SuppressWarnings - 不能实例化类型变量
解决方法：static Pair makePair(Supplier constr) 或者 Class.newInstance() - 不能构造泛型数组
- 若数组仅仅作为类的私有实例域，可以声明为Object[]，获取元素时进行强制转换;
- 用户提供一个数组构造器表达式
public static <T extends Comparable〉T[] minmax(IntFunction constr, T… a){T口 mm = constr.apply(2);}
String[]::new
或使用方式：Array.newInstance
应用：ArrayList.toArray
- 泛型类的静态上下文中类型变量无效
- 不能抛出或捕获泛型类实例
- 可以消除对受查异常的检查
- 注意擦除后的冲突
- 注意方法命名
- “要想支持擦除的转换， 就需要强行限制一个类或类型变量不能同时成为两个接口类型的子类，而这两个接口是同一接口的不同参数化”
继承规则
- 无论S与T有什么联系，通常，Pai
与Pair没有什么联系。 - 可以将参数化类型转换为原始类型
- 泛型类可以扩展或实现其他泛型类
通配符类型
概念
使用泛型时，允许参数类型变化的泛型称为通配符类型
public static void printBuddies(Pair p)
不允许将Pair传递给这个方法，但修改形参为
Pair<? extends Employee> 后允许
按限定分类
-
子类型限定
Pair<? extends Employee>类型的变量不允许调用其setFirst方法，编译器拒绝传递任何特定的类型
用来区分安全的访问器方法和不安全的更改器方法。 -
超类型限定subtype bound
可以为方法提供参数，但不能使用返回值 -
无限定通配符
不需要实际的类型
通配符捕获
通配符捕获只有在有许多限制的情况下才是合法的
反射和泛型
泛型Class类
它允许ClaSS方法的返回类型更加具有针对性
T newInstanceO
T cast(Object obj)
T getEnumConstants()
Class<? super T> getSuperclass()
Constructors getConstructor(C1ass… parameterTypes)
Constructors getDeclaredConstructor(Class… parameterTypes)
虚拟机中信息
TypeVariable：类型变量
WildcardType：通配符限定
ParameterizedType：泛型类或接口类型（如 Comparable<? super T>）
GenericArrayTYpe：泛型数组类型
集合
集合框架
基本结构
Iterable
Iterator：hasNext、next、remove、forEachRemaining
Collection：add、iterator、泛型实用方法
AbstractCollection：提供了部分方法的默认实现
List接口：定义了多个用于随机访问的方法
ListIterator：定义了一个在迭代器前面添加元素的方法
RandomAccess：标签接口，标识集合实现类是否支持高效的随机访问方式
Set接口：等同于Collection，但并不是所有集都是集合，方便程序员编写只接受集的方法。
SortedSet、SortedMap：定义了可以得到集合子集视图的方法。（9.4）
NavigableSet、NavigableMap：用于搜索和遍历有序集和映射的方法，TreeSet、TreeMap实现
具体集合
-
链表
数组和数组列表的重大缺陷：中间位置插入或删除元素会付出很大代价（使用链表的唯一理由）
所有链表实际上是双向链接的doubly linked，ListIterator接口定义了反向操作的方法- 添加元素
依赖位置的add方法由迭代器负责，对自然有序的集合使用迭代器添加元素才有意义，所有add方法被定义在了ListIterator
可向前或向后插入元素，插入位置个数为n+1个 - 遍历
反向遍历：hasPrevious、previous
不要使用随机访问方法遍历链表，效率极低 - 删除
可向前或向后删除
- 添加元素
-
数组列表
-
散列集
装填因子（load factor）决定何时对散列表进行再散列。表中超过75%的位置已经填入元素，表会用双倍桶数自动再散列
HashSet：基于散列表的集
JavaSE8中，桶满时会从链表编程平衡二叉树 -
树集
TreeSet是一个有序集合（Sorted Collection）排序使用树结构完成（当前实现使用的是红黑树），实现了NavigableSet。
不需要对集中元素排序时，优先使用散列集。 -
队列
检索规则：先进先出
实现方式：循环数组、链表
ArrayDeque：有界集合容量有限
LinkedList：*集合 -
优先级队列（priority queue）
按任意顺序插入，按排序顺序检索，调用remove方法，总会获得当前队列中优先级最小的元素。
迭代方式处理元素，不需要进行排序
使用结构：堆（heap）
使用示例：任务调度
映射
-
普通实现类
HashMap
TreeMap -
操作
put – 返回用这个键参数存储的上一个值
更新映射
counts.put(word, counts.getOrDefault(word, 0)+ 1);
或
counts.putlfAbsent(word, 0);
counts.put(word, counts.get(word)+ 1); // Now we know that get will succeed
或
counts.merge(word, 1, Integer::sum); -
映射视图
keySet、values、entrySet
可删除元素，不能调用add增加元素 -
专用映射
- WeakHashMap：当对键的唯一引用来自散列条目时， 这一数据结构将与垃圾回收器协同工作一起删除键/值对。
- LinkedHashSet 和 LinkedHashMap：
① 条目插入表中时，会并入双向链表，记住插入项的顺序。
② 链接散列映射可用访问顺序，对映射条目进行迭代。每次调用get或put, 受到影响的条目将从当前的位置删除，并放到条目链表的尾部，LinkedHashMap<K, V>(initialCapacity, loadFactor, true)
③ 可覆盖removeEldestEntry方法实现基于访问顺序的“最近最少使用”原则实现高速缓存 - EnumSet、EnumMap：键为枚举类型，可用静态方法构造集
- IdentityHashMap：System.identityHashCode计算键，对象比较时使用==
视图与包装器
-
轻量级集合包装器
Arrays.asList()
Collection.nCopies(100, ”xx“)
Collection.singleton() /singletonList /singletonMap -
子范围
可应用任何操作 -
不可修改
Collections.unmodifiableCollection / xxxList / xxxSet …… -
同步
-
受查视图
添加元素时，检测是否符合定义时的泛型类型
算法
- 排序
- 二分查找
- 简单算法
min、max、…… - 批操作
addAll、retainAll、…… - 数组转换
遗留集合
- Hashtable
- 枚举Enumeration
- 属性映射Properties
- 栈Stack
- 位集BitSet
小结
本文整理了Java核心技术中泛型及集合相关的内容，Java中泛型的实现是编译器的功能，将定义泛型的地方进行类型擦除，使用泛型的地方插入了强制类型转换，避免了类定义数量过多的问题，增强了Java语言的安全性；集合框架提供了丰富的接口及实现类，方面功能开发，同时体现了泛型的具体应用。