Java知识梳理之泛型、集合和映射表（五）
部分代码的Github地址为：https://github.com/hzka/JavaBook02/tree/master/chap19
（一）基础概念
1.泛型类的动机与优点：
之前有学到过泛型类ArrayList与泛型接口Comparable。Java有提供ArrayList用于存储泛型类型的数据。可以保存字符串类型对象、数字类型对象。这两种类型可以称之为具体类型。<T>被称之为形式泛型类型，可以用实际具体类型进行替换。
2.ArrayList类：
譬如创建一个字符串线性表： ArrayList<String> arrayList = new ArrayList<>();以后只能添加String类型字符串，若添加其他，就会产生错误。而且注意：泛型类型必须是引用类型。Int->Integer,double->Double等。当然编译器对于基本数据类型也会实现自动打包、解包。譬如：第二三行自动打包，第五行拆包。
ArrayList<Double> list = new ArrayList<>();
list.add(5.0);
list.add(3.3);
Double doubleObject = list.get(0);
double d = list.get(1);3.定义泛型类和接口：
将元素类型通用化为泛型，新命名栈类GenericStack。可使用接口或者类定义泛型，当使用类创建对象，必须声明具体类型。E或者T应该是Object的子类。
import java.util.ArrayList;
public class GenriStack <E>{
private ArrayList<E> list = new ArrayList<>();
//构造函数应当这么写。
public GenriStack(){
}
public int getSize(){
return list.size();
}
public E peek(){
return list.get(getSize()-1);
}
public E pop(){
E o = list.get(getSize()-1);
list.remove(getSize()-1);
return o;
}
public void push(E o){
list.add(o);
}
public boolean isEmpty(){
return list.isEmpty();
}
} 泛型可以提高软件的可靠性和可读性，因为某些错误可能是在编译时才能被检测到。泛型可能会有多个参数，可以用,隔开。
4.泛型方法：
可以定义泛型接口（Comparable）和泛型类（GenriStack），也可以使用泛型类型来定义泛型方法。必须定义泛型类型为静态方法。必须要将泛型类型置于返回类型之前。
import java.util.ArrayList;
public class Main {
public static void main(String[] args) {
Integer[] integers = {1,2,3,4,5};
String[] strings = {"London","Paris","Berlin"};
Main.print(integers);
Main.print(strings);
}
public static <E> void print(E[] lists){
for(int i = 0;i<lists.length;i++){
System.out.print(lists[i]+" ");
}
System.out.println();
}
} 受限泛型：将泛型指定为另外一种类型的子类型。譬如：受限的泛型类<E extends GeometricObject>将E指定为GeometricObject的泛型子类型。
5.原始类型和向后兼容
可以使用泛型类而无需指定具体类型。譬如可以使用原始类型GenriStack stack_01 = new GenriStack<>();替代GenriStack<String> stack_01 = new GenriStack<>();可以向后兼容：但这两种代码风格后者更优。
前者不同类型比较可能会出现运行时错误，后者则是编译错误。
6.通配泛型类型：
通配泛型类型有三种形式：通用通配符 ?、受限通配浮 ? extends T和下限通配符 ? super T。其中T是泛型类型。这个T表示派生自Object类的任何类，比如String,Integer,Double等等。这里要注意的是，T一定是派生于Object类的。为方便起见，大家可以在这里把T当成String,即String在类中怎么用，那T在类中就可以怎么用！所以下面的：定义变量，作为返回值，作为参数传入的定义就很容易理解了。
（1）？是非受限通配，可以表示任一类型。（2）? extends T表示是T或者T的子类型；
（3）? super T指的是表示T或者T的一个父类型。
public class Main {
public static void main(String[] args) {
GenriStack <String> stack1 = new GenriStack<>();
GenriStack<Object> stack2 = new GenriStack<>();
stack2.push("Java");
stack2.push(2);
stack1.push("Sun");
add(stack1,stack2);
}
private static <T> void add(GenriStack<T> stack1, GenriStack<? super T> stack2) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
}
A、B表示类或者接口，而E表示泛型类型参数。
7.消除泛型和对泛型的限制
7.1 泛型存在于编译时，一旦编译器确定该类型是安全的，则会将其转换为原始类型。此称之为泛型消除；当编译泛型类、接口和方法时，编译器使用Object类型来替代泛型类型；当一个泛型是受限的，编译器会使用该受限类型来替换他。
7.2 一些限制：
7.2.1 不能使用new E()创建对象：原因是：运行时泛型不可用。
7.2.2 不能使用new E[]来创建数组。
7.2.3在静态上下文中不允许类的参数是泛型参数。
7.2.4 异常类不能使泛型的。
（二）实战：
1.对一个对象数组进行排序：
完成功能：反省方法对一个Comparable对象数组进行排序，这些对象是Comparable接口的实例，它们使用ComparaTo方法进行比较。程序对整数数组、字符数组、String数组和double数组进行排序。
代码思路：程序中的sort可对任何类型的数组进行排序，但前提是这些对象也是Comparable接口的实例。泛型类型定义为<E extends Comparable<E>> 。两重含义：（1）E是Comparable的子类型；（2）它还指定了比较的元素是E类型的。双重循环排序。
public class Main {
public static void main(String[] args) {
System.out.println("Hello World!");
Integer[] integers = {2,4,3,9,7};
Double[] doubles = {3.4,1.3,-22.1};
Character[] characters = {'a','J','r'};
String [] strings = {"Tom","Susan","Kim"};
sort(integers);
sort(doubles);
sort(characters);
sort(strings);
printList(integers);
printList(doubles);
printList(characters);
printList(strings);
}
public static <E extends Comparable<E>> void sort(E[] list){
E currentMin;
int currentminIndex;
for(int i = 0;i<list.length-1;i++){
currentMin = list[i];
currentminIndex = i;
for(int j=i+1;j<list.length;j++){
//双重循环，假若前者大于后者，则记录当前的位置和数字。
if(currentMin.compareTo(list[j])>0){
currentMin = list[j];
currentminIndex = j;
}
}
//如果不等于，则交换。
if(currentminIndex !=i){
list[currentminIndex] = list[i];
list[i] = currentMin;
}
}
}
public static void printList(Object[] lists){
for(int i = 0;i<lists.length;i++){
System.out.print(lists[i]+" ");
}
System.out.println();
}
}2.泛型矩阵类
public abstract class GenericMartix<E extends Number> {
protected abstract E add(E o1, E o2);
protected abstract E multiply(E o1, E o2);
protected abstract E zero();
public E[][] addMatrix(E[][] matrix1, E[][] martrix2) {
if ((matrix1.length != martrix2.length) || (matrix1[0].length != martrix2[0].length)) {
throw new RuntimeException("The matrix do not have the same size");
}
E[][] result = (E[][]) new Number[matrix1.length][matrix1[0].length];
for (int i = 0; i < result.length; i++) {
for (int j = 0; j < result[0].length; j++) {
//调用的是add抽象方法。
result[i][j] = add(matrix1[i][j] ,martrix2[i][j]);
}
}
return result;
}
public E[][] multiplyMatrix(E[][] matrix1, E[][] martrix2) {
if (matrix1[0].length != martrix2.length) {
throw new RuntimeException("The matrix do not have compatible size");
}
E[][] result = (E[][]) new Number[matrix1.length][martrix2[0].length];
for (int i = 0; i < result.length; i++) {
for (int j = 0; j < result[0].length; j++) {
result[i][j] = zero();
//调用的是add抽象方法。
for(int k = 0;k< matrix1[0].length;k++){
result[i][j] = add(result[i][j],multiply(matrix1[i][k],martrix2[k][j]));
}
}
}
return result;
}
public static void printResult(Number[][] m1, Number[][] m2, Number[][] m3, char op) {
for(int i = 0;i<m1.length;i++){
for(int j = 0;j<m1[0].length;j++){
System.out.print(" "+m1[i][j]);
}
if(i == m1.length / 2){
System.out.print(" "+op+" ");
}else{
System.out.print(" ");
}
for(int j = 0 ;j<m2.length;j++){
System.out.print(" "+m2[i][j]);
}
if(i == m1.length / 2){
System.out.print(" = ");
}else{
System.out.print(" ");
}
for(int j = 0;j<m3.length;j++){
System.out.print(m3[i][j]+" ");
}
System.out.println();
}
}
}
public class Main {
public static void main(String[] args) {
Integer[][] m1 = new Integer[][]{{1, 2, 3}, {4, 5, 6}, {1, 1, 1}};
Integer[][] m2 = new Integer[][]{{1, 1, 1}, {2, 2, 2}, {0, 0, 0}};
IntegerMatrix integerMatrix = new IntegerMatrix();
System.out.println("\nm1+m2 is:");
GenericMartix.printResult(m1,m2,integerMatrix.addMatrix(m1,m2),'+');
System.out.println("\nm1*m2 is:");
GenericMartix.printResult(m1,m2,integerMatrix.multiplyMatrix(m1,m2),'*');
}
}（三）本章小结
（四）集合基础概念
部分代码的Github地址为：https://github.com/hzka/JavaBook02/tree/master/chap21
1.集合基础概念：
存储和处理无重复元素的高效数据结构，可以使用散列表HashSet、链式散列表LinkedHashSet和树形集TreeSet来创建集合。
2.HashSet:
2.1.可使用无参构造方法来创建空的散列集。也可以由一个现有的合集创建散列集。默认情况下是初始容量为16、负载系数为0.75。譬如：默认情况下，当尺寸达到16*0.75 = 12时，容量将会翻倍至32。高负载降低空间开销、但会增加查找时间。
2.2.HashSet主要用来存储互不相同的任何元素。回顾Object类的hasCode方法，若对象相同，则两个对象的散列码必须一样，但两个不等的对象也有可能具有相同的散列码，复写hasCode方法。Java API中的Integer、Character和String都有复写hasCode方法。
2.3.代码示例：散列集存储字符串，foreach进行遍历。P2101项目。
private static void TestingHashSet() {
Set<String> set = new HashSet<>();
set.add("London");
set.add("Paris");
set.add("New York");
set.add("San Francisco");
set.add("Beijing");
set.add("New York");
for(String s:set){
System.out.print(s.toUpperCase()+" ");
}
} 添加多次，一次存储。由于散列表中的元素是没有特定顺序的，因此我们使用LinkedHashSet来强加一个顺序。
2.4 应用Collection接口方法：
HashSet可遍历，可以使用一些API方法，看看HashSet继承自Collection有哪些方法。P2101项目，可以使用add添加元素，remove删除元素，addAll添加某集合，contains是否包含某元素，removeAll删除某集合，retainall保留和某集合共同的元素。
3.LinkedHashSet
链表实现了HashSet类，支持集合内元素排序，换言之，可以按照插入集合顺序进行提取，直接将2.3中第二行的HashSet换成LinkedHashSet来存储不重复的元素。HashSet要比LinkedHashSet更高效。
4.TreeSet
LinkedHashset保持了元素插入时的顺序，但若要强加一个不同的顺序（升序或降序），则需要使用Treeset。介绍了一堆API而已。lower(“P”)小于P的最大元素。啥时候用？当更新一个集合，不需要保持元素排序关系，就应该使用散列集，但需要一个排好序的集合时，Treeset了解下。
Set<String> set = new HashSet<>();
set.add("London");
set.add("Paris");
set.add("New York");
set.add("San Francisco");
set.add("Beijing");
set.add("New York");
TreeSet<String> treeSet = new TreeSet<>(set);
System.out.println("all tree set:" + treeSet);
System.out.println("first()" + treeSet.first());
System.out.println("first()" + treeSet.last());
//小于toElement的那一部分
System.out.println("headset?" + treeSet.headSet("New York"));
//大于等于fromElement的那一部分
System.out.println("tailset?" + treeSet.tailSet("New York"));
System.out.println(treeSet.lower("P"));
System.out.println(treeSet.higher("P"));
System.out.println(treeSet.floor("P"));
System.out.println(treeSet.ceiling("P"));
System.out.println("Delete first"+treeSet.pollFirst());
System.out.println("Delete first"+treeSet.pollLast());
System.out.println("all tree set:" + treeSet);5.比较集合和线性表的性能：
5.1.无重复元素排序方面，集合比线性表表现更高效；但线性表在通过索引访问元素方面非常有用。性能测试目标：测试一个元素是否在一个散列集、链式散列集、树形集、数组线性表以及链表中；（2）从上述中删除元素的执行时间。
5.2.示例代码：P2106代码
import java.util.*;
public class Main {
static final int N = 5000;
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < N; i++) {
list.add(i);
}
// 洗牌一样，随机打乱原来的顺序。
//HashSet
Collections.shuffle(list);
Collection<Integer> set1 = new HashSet<>(list);
System.out.println("HashSet查找时间"+getTestTime(set1)+" s");
System.out.println("HashSet删除时间"+getRemoveTime(set1)+" s");
//LinkedHashSet
Collection<Integer> set2 = new LinkedHashSet<>(list);
System.out.println("LinkedHashSet查找时间"+getTestTime(set2)+" s");
System.out.println("LinkedHashSet删除时间"+getRemoveTime(set2)+" s");
//TreeSet
Collection<Integer> set3 = new TreeSet<>(list);
System.out.println("TreeSet查找时间"+getTestTime(set3)+" s");
System.out.println("TreeSet删除时间"+getRemoveTime(set3)+" s");
//ArrayList
Collection<Integer> list1 = new ArrayList<>(list);
System.out.println("ArrayList查找时间"+getTestTime(list1)+" s");
System.out.println("ArrayList删除时间"+getRemoveTime(list1)+" s");
//LinkedList
Collection<Integer> list2 = new LinkedList<>(list);
System.out.println("LinkedList查找时间"+getTestTime(list2)+" s");
System.out.println("LinkedList删除时间"+getRemoveTime(list2)+" s");
}
private static long getTestTime(Collection<Integer> set) {
long starttime = System.currentTimeMillis();
for(int i = 0;i<N;i++){
set.contains((int)(Math.random()*2*N));//一半在里面，一半在外面
}
return System.currentTimeMillis() - starttime;
}
private static long getRemoveTime(Collection<Integer> set) {
long starttime = System.currentTimeMillis();
for(int i = 0;i<N;i++){
set.remove(i);
}
return System.currentTimeMillis() - starttime;
}
}
结论：测试元素是否在线性表或者集合里面，集合比线性表更高效。因此禁飞名单应当用集合实现。
6.单元素与不可变的合集和映射表。
（五）实战
1.对一个Java源文件中的关键字进行计数。
注意：（1）Java中的关键字和保留字共53个；（2）Arrays.asList()将数组转为线性表。代码如下：
import java.io.File;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class Main {
public static void main(String[] args) throws Exception {
Scanner input = new Scanner(System.in);
System.out.println("Enter a Java Source file:");
String filename = input.nextLine();
File file = new File(filename);
if (file.exists()) {
System.out.println(countKeywords(file));
} else {
System.out.println("File " + filename + " not exists");
}
}
private static int countKeywords(File file) throws Exception {
String[] keywords = {"abstract", "assert", "boolean", "break", "byte", "case", "catch", "char", "class", "const",
"continue", "default", "do", "double", "else", "enum", "extends", "for", "final", "finally", "float", "goto", "if",
"implements", "import", "instanceof", "int", "interface", "long", "native", "new", "package", "private", "protected",
"public", "return", "short", "static", "strictfp", "super", "switch", "synchronized", "this", "throw", "throws",
"transient", "try", "void", "volatile", "while", "true", "false", "null"};
System.out.println(keywords.length);
Set<String> keywordset = new HashSet<>(Arrays.asList(keywords));
int count = 0;
Scanner input = new Scanner(file);
while (input.hasNext()) {
String word = input.next();
if (keywordset.contains(word)) {
System.out.print(" " + word);
count++;
}
}
System.out.println();
return count;
}
}（六）映射表
1.映射表基础概念：
映射表是一种按照键值对存储元素的容易，通过键来获取、删除、更新键值对。映射表中不应该有重复的键。每个键都有一个对应的值。
映射表主要有以下三种：散列映射表HashMap、链式散列映射表LinkedHashMap以及树形映射表TreeMap，都定义于Map接口中。
2.Map接口：
Map接口提供查询（containskey、containsValue、isEmpty和size）、更新（clear、put、putAll和remove）和获取合集的值和合集的键的方法。HashMap、LinkedHashMap以及TreeMap是三个具体的实现。HashMap定位、插入、删除高效；LinkedHashMap支持映射表中条目的排序。分为插入顺序和访问顺序两种。TreeMap在遍历排好顺序的键时很高效。
（七）实战
1.创建三个映射表，建立学生与年龄之间的映射关系。姓名为键、年龄为值。P2108项目。
由结果可知，HashMap条目顺序随机，TreeMap按键升序，LinkedHashMap则是按照最后一次被访问的时间从早到晚排序的。
public class Main {
public static void main(String[] args) {
Map<String,Integer> hashMap = new HashMap<>();
hashMap.put("Smith",30);
hashMap.put("Anderson",31);
hashMap.put("Lewis",29);
hashMap.put("cook",29);
System.out.println("HashMap:"+hashMap);
Map<String,Integer> treeMap = new TreeMap<>(hashMap);//在这调用了putall方法。
System.out.println("TreeMap:"+treeMap);
Map<String,Integer> linkedHashMap = new LinkedHashMap<>(16,0.75f,true);
linkedHashMap.put("Smith",30);
linkedHashMap.put("Anderson",31);
linkedHashMap.put("Lewis",29);
linkedHashMap.put("cook",29);
System.out.println(linkedHashMap.get("Lewis"));
System.out.println(linkedHashMap);
}
2.单词出现的次数：统计一个文本中单词出现的次数，按照字母顺序显示这些单词和它们对应出现的次数。P2109项目。
注意：Map.Entry是Map声明的一个内部接口，此接口为泛型，定义为Entry<K,V>。它表示Map中的一个实体（一个key-value对）。接口中有getKey(),getValue方法。你是否已经对每次从Map中取得关键字然后再取得相应的值感觉厌倦？使用Map.Entry类，你可以得到在同一时间得到所有的信息。
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
String text = "Good morning. Have a good class. Have a good visit. Have fun!";
//TreeMap按键升序
Map<String, Integer> map = new TreeMap<>();
String[] words = text.split("[ \n\t\r.,;:!?(){}]");
for (int i = 0; i < words.length; i++) {
String key = words[i].toLowerCase();
if (key.length() > 0) {
if (!map.containsKey(words[i])) {
map.put(key, 1);
} else {
int value = map.get(key);
value++;
map.put(key, value);
}
}
}
//程序获取集合中映射表的条目。
Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
for (Map.Entry<String, Integer> entry : entrySet) {
System.out.println(entry.getKey() + "\t" + entry.getValue());
}
}
}（八）总结：