当Set使用自己创建的类型时,存储的顺序如何维护,在不同的Set实现中会有不同,而且它们对于在特定的Set中放置的元素类型也有不同的要求:
Set(interface) | 存入Set的每个元素都必须是唯一的,因为Set不保存重复元素。加入Set的元素必须定义equals()方法以确保对象的唯一性。Set和Collection具有完全一样的接口,但Set不保证元素的顺序。 |
HashSet* | 为快速查找而设计的Set。存入HashSet的元素必须定义hashCode()方法。 |
TreeSet | 一种可维护元素顺序的Set,底层为树结构。使用它可以从Set中提取有序的序列。元素必须实现Comparable接口。 |
LinkedHashSet | 具有HashSet的查询速度,而且内部使用链表维护元素的顺序(插入的顺序),于是在使用迭代器遍历Set时,结果会按元素插入的顺序显示。元素也必须定义hashCode()方法。 |
在HashSet打*号,表示如果没有其他的限制,这就应该是默认的选择,因为它的速度很快。
你必须为散列存储和树形存储都定义一个equals()方法,但是hashCode()只有在这个类将会被放入HashSet或者LinkedHashSet中才是必须的。但是对于良好的变成风格而言,你应该在覆盖equals()方法的同时覆盖hashCode()方法。下面的示例演示了为了成功的使用特定的Set实现类而必须定义的方法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
import
java.util.HashSet;
import
java.util.LinkedHashSet;
import
java.util.Set;
import
java.util.TreeSet;
class
SetType {
int
i;
public
SetType (
int
n) { i = n; }
public
boolean
equals(Object obj) {
return
obj
instanceof
SetType && (i == ((SetType)obj).i);
}
public
String toString() {
return
Integer.toString(i); }
}
//能正常被HashSet,LinkedHashSet使用的类型
class
HashSetType
extends
SetType {
public
HashSetType(
int
n) {
super
(n); }
public
int
hashCode() {
return
i; }
}
//能正常被TreeSet使用的类型
class
TreeSetType
extends
SetType
implements
Comparable<TreeSetType>{
public
TreeSetType(
int
n) {
super
(n); }
public
int
compareTo(TreeSetType o) {
return
(o.i < i ? -
1
: (o.i > i ?
1
:
0
));
//降序排列
}
}
public
class
TypesForSets {
static
<T> Set<T> fill(Set<T> set, Class<T> clazz) {
try
{
for
(
int
i =
0
; i <
10
; i++) {
set.add(clazz.getConstructor(
int
.
class
).newInstance(i));
}
}
catch
(Exception e) {
throw
new
RuntimeException(e);
}
return
set;
}
static
<T>
void
test(Set<T> set, Class<T> clazz) {
fill(set, clazz);
fill(set, clazz);
//尝试重复向Set中添加
fill(set, clazz);
System.out.println(set);
}
public
static
void
main(String[] args) {
//正确的装法
System.out.println(
"---------Correct----------"
);
test(
new
HashSet<HashSetType>(), HashSetType.
class
);
test(
new
LinkedHashSet<HashSetType>(), HashSetType.
class
);
test(
new
TreeSet<TreeSetType>(), TreeSetType.
class
);
//错误的装法
System.out.println(
"---------Wrong----------"
);
test(
new
HashSet<SetType>(), SetType.
class
);
test(
new
HashSet<TreeSetType>(), TreeSetType.
class
);
test(
new
LinkedHashSet<SetType>(), SetType.
class
);
test(
new
LinkedHashSet<TreeSetType>(), TreeSetType.
class
);
try
{
test(
new
TreeSet<SetType>(), SetType.
class
);
}
catch
(Exception e) {
System.out.println(e.getMessage());
}
try
{
test(
new
TreeSet<SetType>(), SetType.
class
);
}
catch
(Exception e) {
System.out.println(e.getMessage());
}
}
}
|
执行结果(样例):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
---------Correct----------
[
0
,
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
,
9
]
[
0
,
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
,
9
]
[
9
,
8
,
7
,
6
,
5
,
4
,
3
,
2
,
1
,
0
]
---------Wrong----------
[
1
,
1
,
5
,
0
,
7
,
3
,
4
,
6
,
5
,
9
,
8
,
0
,
7
,
5
,
9
,
6
,
8
,
2
,
4
,
1
,
7
,
4
,
3
,
6
,
8
,
2
,
2
,
0
,
9
,
3
]
[
3
,
5
,
1
,
8
,
5
,
4
,
1
,
0
,
9
,
3
,
0
,
8
,
5
,
7
,
6
,
9
,
7
,
3
,
4
,
0
,
7
,
6
,
2
,
1
,
2
,
8
,
6
,
9
,
4
,
2
]
[
0
,
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
,
9
,
0
,
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
,
9
,
0
,
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
,
9
]
[
0
,
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
,
9
,
0
,
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
,
9
,
0
,
1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
,
9
]
java.lang.ClassCastException:
SetType cannot be cast to java.lang.Comparable
java.lang.ClassCastException:
SetType cannot be cast to java.lang.Comparable
|
为了证明哪些方法是对于某种特殊的Set是必须的,同时也为了避免代码重复,我们创建了三个类型。基类SetType只存储了一个int,并且通过toString()方法产生它的值。因为所有在Set中存储的类型都必须具有equals()方法,因此在基类中也有该方法。
HashSetType继承自SetType,并添加了hashCode()方法,该方法对于放入Set的散列实现中的对象来说是必需的。
TreeType实现了Comparable接口,如果一个对象被用于任何种类的排序容器中,例如TreeSet,那么它必须实现这个接口。注意:在compareTo()方法中,我没有使用简洁明了的形式return o.i-i,因为这是一个常见的编程错误,它只有在i和i2都是无符号的int(如果Java确实有unsigned关键字的话)才能正常工作。对于有符号的int,它就会出错,因为int不够大,不足以表现两个有符号的int的差。例如o.i是很大的正数而且i是很小的负数时,i-j就会溢出并返回负值,这就不对了。
你通常希望compareTo()产生与equals()一致的自然顺序。如果equals()对于某个特定的比较返回true,那么compareTo()对于该比较就应该返回0,反之亦然。
在TypesForSets中,fill()和test()方法都是用泛型定义的,这是为了避免代码重复。为了验证某个Set的行为,test()会在被测Set上调用三次,尝试着在其中添加重复对象。fill()方法接受任意类型的Set,以及对应类型的Class对象,它使用Class对象来发现构造器并构造对象后添加到Set中。
从输出可以看到,HashSet以某种顺序保存所有的元素(这结果是我用 jdk1.7.0_79 跑出来的,而书中描述是用的jdk1.5,因此不知道是不是这里存在的差异。我这里使用HashSet的元素的结果是有序的,但书中顺序是乱的),LinkedHashSet按照元素插入的顺序保存元素,而TreeSet则按照排序(按照compareTo()定义的顺序,这里是降序)保存元素。
如果我们尝试着将没有恰当地支持必须操作的类型用于这些方法的Set,那么就会有麻烦了。对于没有重新定义hashCode()方法的SetType或TreeType,如果将它们放置到任何散列表中都会产生重复值,这样就违反了Set的基本约定。这相当烦人,因为这种情况甚至不会有运行时错误。