SCJP笔记_章七_泛型与集合

第七章 泛型与集合

 

 

7.1 重写hashCode()和equals()方法

考试目标6.2 区分hashCode()和equals()方法的正确设计和错误设计，并解释 == 和equals()方法的不同。

 

toString()方法

刚没有重写toString方法时，显示该对象哈希码的无符号十六进制表示。如：

TestObject@a47e0.

 

7.1.1 重写equals()方法

 

使用==来判断两个引用变量是否引用了同一个对象。

使用equals()来判断两个对象在意义上是否等价。

 

不重写equals()意味着什么?

如果不重写equals()，则对象将不会是有用的哈希键。

如果不重写equals()，则不同的对象不能认为是等价的。

总之，如果不重写，则equals()只使用==运算符进行比较。

public class TestEquals {

	public static void main(String[] args) {
		TestEquals t1 = new TestEquals();
		TestEquals t2 = new TestEquals();
		System.out.println(t1.toString());
		System.out.println(t2.toString());
		System.out.println(t1==t2);
		System.out.println(t1.equals(t2));
	}

}
//result:
//testGenerics.TestEquals@35ce36
//testGenerics.TestEquals@757aef
//false
//false

 

 

实现equals()方法

public class TestEquals2 {

	private int id;	
	
	public int getId() {
		return id;
	}
	public void setId(int id) {
		this.id = id;
	}

	public boolean equals(Object o){
		if ((o instanceof TestEquals2)&&(this.id==((TestEquals2) o).getId())) {
			return true;			
		}else{
			return false;
		}
	}
	
	public static void main(String[] args) {
		TestEquals2 t1 = new TestEquals2();
		t1.setId(1);
		TestEquals2 t2 = new TestEquals2();
		t2.setId(1);
		TestEquals2 t3 = new TestEquals2();
		t3.setId(2);
		System.out.println(t1.toString());
		System.out.println(t2.toString());
		System.out.println(t1==t2);
		System.out.println(t1.equals(t2));
		System.out.println(t1.equals(t3));
	}
}
//result:
//testGenerics.TestEquals2@35ce36
//testGenerics.TestEquals2@757aef
//false
//true
//false

 

 

equals()契约

• 自反的 对于任何引用值x,x.equals(x)都应该返回true。
• 对称的 对于任何引用值x和y，当且仅当y.equals(x)返回true时，x.equals(y)才返回true。
• 传递的 对于任何引用值x,y,z，如果x.equals(y)返回true时，并且y.equals(z)返回true。
• 一致的 对于任何引用值x和y，如果在该对象上的相等性比较中所使用的信息没有做修改，则对x.equals(y)的多次调用要一致地返回true或者false。
• 对于变元为null的都应返回false

  

7.1.2 重写hashCode()方法

 

理解哈希码

一个类的许多对象，根据同一算法生成的值分类（分桶），当查找时，先由hashCode()算出值，确定在哪个哈希桶里。

不同的对象可能有相同的哈希值；重写过equals方法的相同对象，应该有一样的哈希值。

 

实现hashCode()方法

说白了就是怎样的hashCode算法，都返回一个默认值，比如1932，这样的做法是“合法的”，但是并不合适。这就相当于把所有的对象都放在了一个桶中，并没有达到分类、管理对象的目的。

“适当的”方法是将如id等，能代表对象唯一性等的属性加入到hashCode的算法中，尽可能的将各个桶平衡。

 

hashCode()契约

• 在Java应用程序的同一个执行期间，如果没有修改对象的equals()比较内使用的任何信息，则无论什么时候在相同的对象上多次调用hashCode()方法时，它必须一致地返回同一个整数。
• 如果equals()方法两个对象是相等的，则在这两个对象的任意一个上调用hashCode()方法，必须产生相同的整数结果。
• 如果根据equals()方法两个对象是不相等的，则在这两个对象的任意一个上调用hashCode()方法，并不要求产生不同的整数结果。然而程序员应该知道，为不相等的对象产生不同的整数结果可能提高哈希表的性能。

 

7.2 集合

 

考试目标6.1 给定一个设计场景，判断应该使用哪些集合类和/或接口来恰当地实现该设计，包括使用Comparable接口。

 

7.2.1 用集合做什么

• 将对象添加到集合。
• 从集合中删除对象。
• 找出一个对象（或一组对象）是否位于集合内。
• 从集合中检索对象（不删除它）。
• 迭代遍历集合，逐个查看每个元素（对象）。

集合框架的重点接口和类

 

• collection      表示概念上的集合。
• Collection     表示java.util.Collection接口，Set、List和Queue扩展自它。Map并不扩展自它。
• Collections   表示java.util.Collections类，它拥有大量的静态实用工具方法，用于集合。

集合的4种基本形式：

List 事物列表（实现List的类）

Set 具有唯一性的事物（实现Set的类）

Map 具有唯一ID的事物（实现Map的类）

Queue 按照被处理的顺序排列的事物

 

ordered（有序的，有秩序的，有先来后到的）

表示该集合能够按照特定的顺序（而不是随机的顺序）迭代遍历这个集合。

 

sorted（已排序，有顺序的，有顺序规则的）

表示集合中的顺序是根据某个或某些规则确定的。

  

 

7.2.2 List接口

List关心的是索引。

 

ArrayList

可以将它理解成一个可增长的数组。

它不是同步的。

它提供快速迭代和快速随机访问的能力。

 

Vector

它就是个同步的ArrayList，线程安全。

 

LinkedList

迭代比ArrayList慢，但适合用来快速插入和删除。

 

 

7.2.3 Set接口

Set关心唯一性，它不允许重复

 

HashSet

HashSet 是一种 unsorted、unordered 的 Set 。它使用被插入对象的哈希码，因此，hashCode()实现越有效，将得到的访问性能就越好。、

速度访问，保证没有重复，不提供任何顺序。

 

LinkedHashSet

是HashSet的ordered版本，按照插入顺序迭代

 

TreeSet

是sorted的，按照元素的自然顺序进行升序排列。或者构造一个带构造函数的TreeSet，它让你通过使用Comparable或Comparator为集合提供自己的规则。

 

7.2.4 Map接口

Map关心唯一的标识符

 

HashMap

最快速地更新键/值对。允许一个null键和多个null值。

 

Hashtable

HashMap的同步版本，不允许null键或null值。

 

LinkedHashMap

迭代更快，按照插入顺序或者最后访问的顺序迭代。允许一个null键和多个null值。

 

TreeMap

一种排序映射。

 

7.2.5 Queue接口

 

PriortyQueue

按照元素的优先级排序的“待执行任务”的列表。

 

 

类	Map	Set	List	ordered	sorted
HashMap	x			否	否
Hashtable	x			否	否
TreeMap	x			sorted	按照自然顺序或自定义比较规则
LinkedHashMap	x			按照插入顺序或最后的访问顺序	否
HashSet		x		否	否
TreeSet		x		sorted	按照自然顺序或自定义比较规则
LinkedHashSet		x		按照插入顺序	否
ArrayList			x	按照索引	否
Vector			x	按照索引	否
LinkedList			x	按照索引	否
PriorityQueue				sorted	按照“要执行的任务”的顺序

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

7.3 使用集合框架

 

考试目标6.3 编写使用NavigableSet和NavigableMap接口的代码。

考试目标6.5 利用java.util包中的功能编写代码，通过排序、执行折半查找或将数组转换成列表操作列表。利用java.util包中的功能编写代码，通过排序、执行折半查找或将数组转换成列表来操作数组。利用java.util.Comparator和java.lang.Comparable接口来影响列表或数组的排序。此外，还要认识基本包装器类和java.lang.String在排序时的“自然顺序”的影响。

 

7.3.1 ArrayList基础

与数组相比，ArrayList建立时不用指定长度，可以动态增长，提供更加强大的插入和查找机制。

 

7.3.2 用集合进行自动装箱

Java5中，可以将集合中的基本类型自动装箱为包装类型。

 

7.3.3 排序集合与数组

 

排序集合

import java.util.ArrayList;
import java.util.Collections;

public class TestSort1 {
	public static void main(String[] args) {
		ArrayList<String> stuff = new ArrayList<String>();
		stuff.add("Denver");
		stuff.add("Boulder");
		stuff.add("Vail");
		stuff.add("Aspen");
		stuff.add("Telluride");
		System.out.println("unsorted " + stuff);
		Collections.sort(stuff);      //自然排序
		System.out.println("sorted   " + stuff);		
	}
}

unsorted [Denver, Boulder, Vail, Aspen, Telluride]
sorted   [Aspen, Boulder, Denver, Telluride, Vail]

 

Comparable接口

Comparable接口由Collections.sort()方法和java.util.Arrays.sort()方法用来分别排序List和对象数组。

要实现java.lang.Comparable，类必须实现一种方法compareTo()。下面是compareTo()的调用：

int x = thisObj.compareTo(anotherObj);

该方法返回如下int结果:

负数，如果thisObj < anotherObj

零，如果thisObj == anotherObj

正数，如果thisObj > anotherObj

总之，实现compareTo()就是制定对象排序的标准。

 

用Comparator排序

Collections.sort()还有一个重载：

public static <T> void sort(List<T> list,
                            Comparator<? super T> c)

 

Comparable接口和Comparator接口的比较

 

java.lang.Comparable	java.util.Comparator
int objOne.compareTo(objTwo)	int compare(objOne,objTwo)
返回： 负数，如果objOne < objTwo 零，   如果objOne==objTwo 正数，如果objOne > objTwo	相同
必须修改想排序其实例的类	构建一个类，它不同于想排序其实例的类
只可以创建一个排序序列	可以创建多个排序序列
在API中经常由如下方式实现： String、包装器类、Date、Calendar	意味着要实现成排序第三方类的实例

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

用Arrays类排序

Arrays.sort(arrayToSort)

Arrays.sort(arrayToSort,Comparator)

 

查找数组与集合

static int binarySearch(Object [] ar,Object key) 

方法返回两种结果，如果在数组ar中查到了key，则返回key的索引值；否则返回插入点。

插入点与索引值：

插入点：   -1         -2         -3         -4        -5      -(n+1)      -(n+2)

数组：         ar[0]     ar[1]     ar[2]    ar[3]   ...............ar[n]  

索引值：         0           1           2          3                       n

package testGenerics;

import java.util.Arrays;
import java.util.Comparator;

public class SearchObjArray {
	public static void main(String[] args) {
		String[] sa = {"one","two","three","four"};
		Arrays.sort(sa);		//#1
		for(String s:sa){
			System.out.print(s+" ");
		}
		System.out.println("\none = "+Arrays.binarySearch(sa, "one"));	//#2
		
		System.out.println("now reverse sort");
		ReSortComparator rs = new ReSortComparator();		//#3
		Arrays.sort(sa,rs);
		for(String s : sa){
			System.out.print(s + " ");
		}
		System.out.println("\none = "+Arrays.binarySearch(sa, "one"));	//#4
		System.out.println("one = "+Arrays.binarySearch(sa,"one",rs));	//#5
	}
	
	static class ReSortComparator implements Comparator<String>{	//#6
		public int compare(String a,String b){
			return b.compareTo(a);			//#7
		}
	}
}
//result:
//four one three two 
//one = 1
//now reverse sort
//two three one four 
//one = -1
//one = 2
/*
 * #1：按字母顺序（自然顺序）排序sa数组。
 * #2：查找元素“one”的位置，该位置为1.
 * #3：创建一个Comparator实例。下一行使用comparator重新排序数组。
 * #4：尝试查找数组。我们没有将用于排序数组的Comparator传递给binarySearch()方法，
 *     因此，获得一个不正确的（不明确的）答案。
 * #5：再次查找，将Comparator传递给binarySearch()。这次获得了正确答案2.
 * #6：定义Comparator，这里让它称为一个内部类是可行的。
 * #7：通过在调用compareTo()中变元的交换使用，得到反向的排序。
 */ 

 

 

在数组和List之间进行转换:

Arrays.asList()

List.toArray()

 

使用List

可以通过Iterator迭代器来遍历List，Iterator的两个方法：

boolean hasNext()

Object next()

  

7.3.4 导航（查找）TreeSet与TreeMap

TreeSet和TreeMap实现了 Java6 的新接口 java.util.NavigableSet 和 java.util.NavigableMap

现在有一个需求是我想查在一个Set里，比1600大一点的那个元素，下面是在Java5和Java6的不同实现

package testGenerics;

import java.util.TreeSet;

public class Ferry {

	public static void main(String[] args) {
		TreeSet<Integer> times = new TreeSet<Integer>();
		times.add(1205);
		times.add(1505);
		times.add(1545);
		times.add(1830);
		times.add(2010);
		times.add(2100);
		
		TreeSet<Integer> subset = new TreeSet<Integer>();
		subset = (TreeSet<Integer>) times.headSet(1600);
		System.out.println("J5 - last before 4pm is:"+subset.last());
		
		TreeSet<Integer> sub2 = new TreeSet<Integer>();
		sub2 = (TreeSet<Integer>) times.tailSet(2000);
		System.out.println("J5 - first after 8pm is:"+sub2.first());
		
		System.out.println("J6 - last before 4pm is:"+times.lower(1600));
		System.out.println("J6 - first after 8pm is:"+times.higher(2000));
	}

}
//result:
//J5 - last before 4pm is:1545
//J5 - first after 8pm is:2010
//J6 - last before 4pm is:1545
//J6 - first after 8pm is:2010

 

7.3.5 其他导航方法

轮询polling

 

TreeSet

 

E	ceiling(E e)           返回此 set 中大于等于给定元素的最小元素；如果不存在这样的元素，则返回 null。

 

E	higher(E e)           返回此 set 中严格大于给定元素的最小元素；如果不存在这样的元素，则返回 null。

 

E	floor(E e)           返回此 set 中小于等于给定元素的最大元素；如果不存在这样的元素，则返回 null。

 

E	lower(E e)           返回此 set 中严格小于给定元素的最大元素；如果不存在这样的元素，则返回 null。

E	pollFirst()           获取并移除第一个（最低）元素；如果此 set 为空，则返回 null。

 

E	pollLast()           获取并移除最后一个（最高）元素；如果此 set 为空，则返回 null。

 

TreeMap

 

K	ceilingKey(K key)           返回大于等于给定键的最小键；如果不存在这样的键，则返回 null。

 

K	higherKey(K key)           返回严格大于给定键的最小键；如果不存在这样的键，则返回 null。

 

K	floorKey(K key)           返回小于等于给定键的最大键；如果不存在这样的键，则返回 null。

 

K	lastKey()           返回映射中当前最后一个（最高）键。

 

TreeMap还可以返回键值对：

TreeMap的firstEntry()方法返回一个与此映射中的最小键关联的键-值映射关系；如果映射为空，则返回 null。

TreeMap的lastEntry()方法返回与此映射中的最大键关联的键-值映射关系；如果映射为空，则返回 null。

 

降序

TreeSet

 

NavigableSet<E>

descendingSet()           返回此 set 中所包含元素的逆序视图。

TreeMap

 

NavigableMap<K,V>

descendingMap()           返回此映射中所包含映射关系的逆序视图。

 

7.3.6 后备集合

下面以Set为例，比如headSet()，在Map中有相应的方法headMap()

 

NavigableSet<E>

headSet(E toElement, boolean inclusive)           返回此 set 的部分视图，其元素小于（或等于，如果 inclusive 为 true）toElement。

 

NavigableSet<E>

tailSet(E fromElement, boolean inclusive)           返回此 set 的部分视图，其元素大于（或等于，如果 inclusive 为 true）fromElement。

 

NavigableSet<E>

subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)           返回此 set 的部分视图，其元素范围从 fromElement 到 toElement。

 

使用PriortyQueue类

 

E	poll()           获取并移除此队列的头，如果此队列为空，则返回 null。

E	peek()           获取但不移除此队列的头；如果此队列为空，则返回 null。

 

boolean

offer(E e)           将指定的元素插入此优先级队列。

 

Arrays和Collections中的方法概述

java.util.Arrays中的主要方法：

 

static <T> List<T>

asList(T... a)           返回一个受指定数组支持的固定大小的列表。

 

static int

binarySearch(Object[] a, Object key)           使用二分搜索法来搜索指定数组，以获得指定对象。

 

static <T> int

binarySearch(T[] a, T key, Comparator<? super T> c)           使用二分搜索法来搜索指定数组，以获得指定对象。

 

static boolean

equals(Object[] a, Object[] a2)           如果两个指定的 Objects 数组彼此相等，则返回 true。

 

static void

sort(Object[] a)           根据元素的自然顺序对指定对象数组按升序进行排序。

 

static <T> void

sort(T[] a, Comparator<? super T> c)           根据指定比较器产生的顺序对指定对象数组进行排序。

 

static String

toString(Object[] a)           返回指定数组内容的字符串表示形式。

 

java.util.Collections中的主要方法：

 

static <T> int	binarySearch(List<? extends Comparable<? super T>> list, T key)           使用二分搜索法搜索指定列表，以获得指定对象。
static <T> int	binarySearch(List<? extends T> list, T key, Comparator<? super T> c)           使用二分搜索法搜索指定列表，以获得指定对象。

 

static void	reverse(List<?> list)           反转指定列表中元素的顺序。
static <T> Comparator<T>	reverseOrder()           返回一个比较器，它强行逆转实现了 Comparable 接口的对象 collection 的自然顺序。
static <T> Comparator<T>	reverseOrder(Comparator<T> cmp)           返回一个比较器，它强行逆转指定比较器的顺序。

 

static <T extends Comparable<? super T>> void	sort(List<T> list)           根据元素的自然顺序 对指定列表按升序进行排序。
static <T> void	sort(List<T> list, Comparator<? super T> c)           根据指定比较器产生的顺序对指定列表进行排序。

 

 

List、Set、Map和Queue的方法概述

 

主要接口方法	List	Set	Map	描述
boolean add(element) boolean add(index,element)	X X	X		添加一个元素。对于List，可以在 索引点有选择地添加元素
boolean contains(object) boolean containsKey(object key) boolean containsValue(object value)	X	X	X X	在集合中查找一个对象（或者有选 择地在Map中查找一个键），将结 果作为boolean返回
object get(index) object get(key)	X		X	通过索引或键从集合获得一个对象
int indexOf(object)	X			获得对象在List中的位置
Iterator iterator()	X	X		获得List或Set的迭代器
Set keySet()			X	返回包含Map的键的Set
put(key,value)			X	添加一个键/值对到Map
remove(index) remove(object) remove(key)	X X	X	X	通过索引、元素的值或键删除元素
int size()	X	X	X	返回集合中元素的数量
Object[] toArray() T[] toArray(T[])	X	X		返回包含集合元素的数组

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

7.4 泛型类型

 

考试目标6.3 编写代码，使用Collections API的泛型版本，特别是Set、List和Map接口以及实现类的泛型版本。了解非泛型的Collection API的限制以及如何重构代码来使用泛型版本。

考试目标6.4 编写代码，正确使用类/接口声明、实例变量、方法变元以及返回类型中的类型参数。编写泛型方法或使用通配符类型的方法，并理解这两种方法间的相似及不同之处。编写使用NavigableSet和NavigableMap接口的代码。

 

处理集合的遗留方式

使用泛型如下声明一个List：

List<String> myList = new ArrayList<String>();

使用了泛型后，myList里的所有元素都必须是String类型的；如果我们不使用泛型，虽然你可以往这个myList里插入各种类型的元素，但是你要自己保证代码的安全性。读出的时候要强制转型，并且要保证确实能够转型。

 

7.4.1 泛型与遗留代码

把非泛型代码升级成泛型代码：

在集合类的关键字后面加<类型>。

 

7.4.2 混合泛型和非泛型集合

可以将泛型集合传递到带有非泛型集合的方法，但结果可能非常糟糕。编译器不能阻止方法将错误的类型插入到以前是类型安全的集合。

如果编译器能够认识到，非类型安全的代码可能会危害原来声明为类型安全的东西，就会给出一个编译器警告。例如，如果将一个List<String>传递到声明为

void foo(List aList){aList.add(anInteger);} 的方法，则会得到一个警告，因为add()有可能是“不安全的”。

“编译不带错误”与“编译不带警告”是不同的。编译时的警告不被认为是一个编译错误或失败。

泛型类型信息在运行时不存在——它只用于编译时安全。混合泛型与遗留代码所得到的编译后代码，在运行时可能抛出异常。

 

7.4.3 多态与泛型

规则：变量声明的类型必须匹配传递给实际对象的类型。如果声明了List<Foo> foo，那么赋予foo引用的必须是泛型类型<Foo>，而不是<Foo>的一个子类型，也不是它的一个超类型。

 

7.4.4 泛型方法

前面介绍了一个规则，但如果我现在需要声明泛型为XX的子类型时，该怎么声明才能让所有子类型泛型都使用父类型泛型呢？

通配符语法允许泛型方法，接受方法变元所声明的类型的子类型（或超类型）：

void addD(List<? extends Dog> list){}

通配符关键字extends用于表示“扩展”或“实现”。因此，在<? extends Dog>中，Dog可以是一个类，也可以是一个接口。

 

当使用通配符时，List<? extends Dog>表示可以访问集合但不能修改它。

当使用通配符时，List<?>表示任何泛型类型都可以赋给引用，但只能访问，不能修改。 

 

7.4.5 泛型声明

泛型的声明约定用T代表类型，E代表元素：具体使用的时候只要记住集合用E，非集合用T就好了。

 

创建自己的泛型类

创建泛型方法