Set是如何实现没有重复元素
2009-12-18 21:11:05 来源:WEB开发网 闂傚倸鍊搁崐鎼佸磹閹间礁纾归柟闂寸绾惧綊鏌熼梻瀵割槮缁炬儳缍婇弻鐔兼⒒鐎靛壊妲紒鐐劤缂嶅﹪寮婚悢鍏尖拻閻庨潧澹婂Σ顔剧磼閻愵剙鍔ょ紓宥咃躬瀵鎮㈤崗灏栨嫽闁诲酣娼ф竟濠偽i鍓х<闁绘劦鍓欓崝銈囩磽瀹ュ拑韬€殿喖顭烽幃銏ゅ礂鐏忔牗瀚介梺璇查叄濞佳勭珶婵犲伣锝夘敊閸撗咃紲闂佽鍨庨崘锝嗗瘱闂備胶顢婂▍鏇㈠箲閸ヮ剙鐏抽柡鍐ㄧ墕缁€鍐┿亜韫囧海顦﹀ù婊堢畺閺屻劌鈹戦崱娆忓毈缂備降鍔庣划顖炲Φ閸曨垰绠抽悗锝庝簽娴犻箖姊洪棃娑欐悙閻庢矮鍗抽悰顕€宕堕澶嬫櫖濠殿噯绲剧€笛囧箲閸ヮ剙钃熼柣鏂挎憸閻熷綊鏌涢…鎴濇灈妞ゎ剙鐗嗛—鍐Χ鎼粹€茬凹缂備緡鍠楅幐鎼佹偩閻戣棄纭€闁绘劕绉靛Λ鍐春閳ь剚銇勯幒鎴濐伀鐎规挷绀侀埞鎴︽偐閹绘帩浼€缂佹儳褰炵划娆撳蓟濞戞矮娌柟瑙勫姇椤ユ繈姊洪柅鐐茶嫰婢т即鏌熼搹顐e磳闁挎繄鍋涢埞鎴犫偓锝庘偓顓涙櫊閺屽秵娼幏灞藉帯闂佹眹鍊曢幊鎰閹惧瓨濯撮柛鎾村絻閸撳崬顪冮妶鍡楃仸闁荤啿鏅涢悾鐑藉Ψ瑜夐崑鎾绘晲鎼粹剝鐏嶉梺缁樻尰濞叉﹢濡甸崟顖氱疀闂傚牊绋愮花鑲╃磽娴h棄鐓愭慨妯稿妿濡叉劙骞樼拠鑼槰闂佸啿鎼崐濠毸囬弶搴撴斀妞ゆ梻銆嬪銉︺亜椤撶偛妲婚柣锝囧厴楠炴帡骞嬮弮鈧悗濠氭⒑鐟欏嫭鍎楅柛妯衡偓鐔插徍濠电姷鏁告慨鐑藉极閸涘﹥鍙忔い鎾卞灩绾惧鏌熼崜褏甯涢柍閿嬪灦閵囧嫰骞掗崱妞惧缂傚倷绀侀ˇ閬嶅极婵犳氨宓侀柛鈩冪⊕閸婄兘鏌涘┑鍡楊伀妞ゆ梹鍔曢埞鎴︽倻閸モ晝校闂佸憡鎸婚悷锔界┍婵犲洦鍤冮柍鍝勫暟閿涙粓姊鸿ぐ鎺戜喊闁告瑥楠搁埢鎾斥堪閸喓鍘搁柣蹇曞仧绾爼宕戦幘璇茬疀濞达絽鎲¢崐顖炴⒑绾懎浜归悶娑栧劦閸┾偓妞ゆ帒鍟惃娲煛娴e湱澧柍瑙勫灴閹瑩寮堕幋鐘辨闂備礁婀辨灙闁硅姤绮庨崚鎺楀籍閸喎浠虹紓浣割儓椤曟娊鏁冮崒娑氬幈闂佸搫娲㈤崝宀勬倶閻樼粯鐓曢柟鑸妼娴滄儳鈹戦敍鍕杭闁稿﹥鐗犲畷婵嬫晝閳ь剟鈥﹂崸妤€鐒垫い鎺嶈兌缁犲墽鈧厜鍋撳┑鐘辩窔閸嬫鈹戦纭烽練婵炲拑绲垮Σ鎰板箳閹冲磭鍠撻幏鐘绘嚑閼稿灚姣愰梻鍌氬€烽懗鑸电仚濠电偛顕崗妯侯嚕椤愩倖瀚氱€瑰壊鍠栧▓銊︾節閻㈤潧校缁炬澘绉瑰鏌ュ箵閹烘繄鍞甸柣鐘烘鐏忋劌顔忛妷褉鍋撶憴鍕碍婵☆偅绻傞~蹇涙惞閸︻厾锛滃┑鈽嗗灠閹碱偊锝炲鍥╃=濞达綁顥撻崝宥夋煙缁嬪灝鏆遍柣锝囧厴楠炲鏁冮埀顒傜不婵犳碍鍋i柛銉戝啰楠囬悗瑙勬尭缁夋挳鈥旈崘顔嘉ч柛鈩兠棄宥囩磽娴e壊鍎愰柛銊ュ缁顓兼径瀣偓閿嬨亜閹哄秶顦︾€殿喖鐏濋埞鎴﹀煡閸℃浠梺鍛婎焼閸曨収娲告俊銈忕到閸燁垶宕愰崹顐e弿婵☆垳鍘ф禍楣冩倵濮樼偓瀚�

核心提示:Set和数学中的集合是同一个概念,就是没有重复元素的集合,Set是如何实现没有重复元素, 这篇文章主要论述了Set是如何实现"没有重复元素"(no duplicate elements)的,以及阐述了什么是“重复”(duplicate),那么可以使用TreeSet来构造类的实体, C、如果想使用判
Set和数学中的集合是同一个概念,就是没有重复元素的集合。
这篇文章主要论述了Set是如何实现"没有重复元素"(no duplicate elements)的,以及阐述了什么是“重复”(duplicate),是相同的地址空间?是equals的返回值为true?是compareTo的返回值为0 ?还是有相同的hashCode?本文还给出了在什么情况下使用什么样的Set的建议。
注:本文不涉及范型。
1、树形结构:
public interface Set<E> extends Collection<E>{}
public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E>{}
public class CopyOnWriteArraySet<E>extends AbstractSet<E>implements Serializable{}
public abstract class EnumSet<E extends Enum<E>>extends AbstractSet<E>implements Cloneable, Serializable{}
public class HashSet<E>extends AbstractSet<E>implements Set<E>, Cloneable, Serializable{}
public final class JobStateReasonsextends HashSet<JobStateReason>implements PRintJobAttribute{}
public class LinkedHashSet<E>extends HashSet<E>implements Set<E>, Cloneable, Serializable{}
public class TreeSet<E>extends AbstractSet<E>implements SortedSet<E>, Cloneable, Serializable{}
可以看出,可以实例化的类为:CopyOnWriteArraySet,HashSet,LinkedHashSet,TreeSet。
2、Set是如何实现元素唯一性的
javadoc中对Set的描述第一段如下:“A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1
and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.”
这段话是对是错,请看下面分析。
要进行下面的论述,我们先了解一下Map。Map中的元素是“键-值”对,其中“键”必须是唯一的。TreeSet和HashSet就是利用这个特性实现“no duplicate elements”。它把set中的元素作为Map中的“键”,从而保持元素的唯一性。这些键在Map中又是如何区分的呢?不同的Map有不同的做法,而且区别很大。
下面我们分别就TreeSet、HashSet和CopyOnWriteArraySet进行论述:
2.1、TreeSet部分:
以下以TreeSet为例进行分析。
请看TreeSet的部分实体:
public class TreeSet<E> extends AbstractSet<E>
implements SortedSet<E>, Cloneable, java.io.Serializable
{
// The backing Map
private transient SortedMap<E,Object> m;
// The keySet view of the backing Map
private transient Set<E> keySet;
// Dummy value to associate with an Object in the backing Map
//这是每个键所指的对像
private static final Object PRESENT = new Object();
//constructor
private TreeSet(SortedMap<E,Object> m) {
this.m = m;
keySet = m.keySet();
}
public TreeSet() {
this(new TreeMap<E,Object>());
}
//以下省略..........
}
可以看到TreeSet使用了SortedMap作为其Map保存“键-值”对,而这个SortedMap的真正实体是TreeMap。
请看示例程序1:
import java.util.*;
public class SetTest1 {
public static void main(String[] args){
Set set = new TreeSet();
set.add(new SetElement1("aa"));
set.add(new SetElement1("bb"));
}
static class SetElement1{
String s;
public SetElement1(String s){
this.s = s;
}
public String toString(){
return s;
}
public boolean equals(Object obj) {
return s.equals(((SetElement1)obj).s);
}
}
}
该程序能够正常编译,但是运行时会抛出异常java.lang.ClassCastException。为什么?
请看示例程序2:
import java.util.*;
public class SetTest2 {
public static void main(String[] args){
Set set = new TreeSet();
set.add(new SetElement2("aa"));
set.add(new SetElement2("aa"));
set.add(new SetElement2("bb"));
System.out.println(set);
}
static class SetElement2 implements Comparable{
String s;
public SetElement2(String s){
this.s = s;
}
public String toString(){
return s;
}
public int compareTo(Object o){
return s.compareTo(((SetElement2)o).s);
}
public boolean equals(Object obj) {
return s.equals(((SetElement2)obj).s);
}
}
}
运行结果:
[aa, bb]
这正是我们所期望的结果。那“示例程序1”和“示例程序2”有什么区别?
是因为SetElement2实现了Comparable接口,而SetElement1没有。SetElement2实现Comparable接口有什么用呢?因为在TreeSet的add方法中需要比较两个 元素的“值”。请看TreeMap中的compare方法:
private int compare(K k1, K k2) {
return (comparator==null ? ((Comparable</*-*/K>)k1).compareTo(k2)
: comparator.compare((K)k1, (K)k2));
}
可见这个方法先把要比较的元素down cast成Comparable类型。这里就可以解释“示例程序1”中为什么会抛出异常java.lang.ClassCastException,因SetElement1没有实现Comparable接口,当然就不能down cast成Comparable。可见,要用TreeSet来做为你的Set,那么Set中所装的元素都必须实现了Comparable接口。
说到这里,你是不是想到了TreeSet中是采用Comparable接口中的compareTo方法来判断元素是否相同(duplicate),而不是采用其他类似equals之类的东东来判断。
请看示例程序3:
import java.util.Set;
import java.util.*;
public class SetTest3 {
public static void main(String[] args){
Set set = new HashSet();
set.add(new SetElement3("aa"));
set.add(new SetElement3("aa"));
set.add(new SetElement3("bb"));
System.out.println(set);
}
static class SetElement3 implements Comparable{
String s;
public SetElement3(String s){
this.s = s;
}
public String toString(){
return s;
}
public int compareTo(Object o){
//return s.compareTo(((SetElement3)o).s);
return -1;
}
public boolean equals(Object obj) {
return s.equals(((SetElement3)obj).s);
}
}
}
运行结果:
[bb, aa, aa]
看到没有,有两个“aa”!!这是因为compareTo返回值始终是"-1",也就是说“把任何元素都看成不同”。
综上所述,你是否对javadoc中对Set功能的描述有了怀疑?!
2.2、HashSet部分:
以下以HashSet为例进行分析。
从Hashset类的主体部分:
public class HashSet<E> extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
static final long serialVersionUID = -5024744406713321676L;
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
//这是每个键所指的对像
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<E,Object>();
}
public boolean add(E o) {
return map.put(o, PRESENT)==null;
}
//以下省略..........
}
public HashSet() {
map = new HashMap<E,Object>();
}
可以看到HashSet使用了HashMap作为其Map保存“键-值”对。
请看示例程序4:
import java.util.*;
public class SetTest4 {
public static void main(String[] args){
Set set = new HashSet();
set.add(new SetElement4("aa"));
set.add(new SetElement4("aa"));
set.add(new SetElement4("bb"));
System.out.println(set);
}
static class SetElement4{
String s;
public SetElement4(String s){
this.s = s;
}
public String toString(){
return s;
}
public boolean equals(Object obj) {
return s.equals(((SetElement4)obj).s);
}
}
}
运行结果:
[bb, aa, aa]
没有“示例程序1”中的java.lang.ClassCastException,但是运行结果似乎不对,因为有两个“aa”。
请看示例程序5:
import java.util.*;
public class SetTest5 {
public static void main(String[] args){
Set set = new HashSet();
set.add(new SetElement5("aa"));
set.add(new SetElement5("aa"));
set.add(new SetElement5("bb"));
System.out.println(set);
}
static class SetElement5{
String s;
public SetElement5(String s){
this.s = s;
}
public String toString(){
return s;
}
public boolean equals(Object obj) {
return s.equals(((SetElement5)obj).s);
}
public int hashCode() {
//return super.hashCode();
return s.hashCode();
}
}
}
运行结果:
[bb, aa]
这就对了。“示例程序4”和“示例程序5”有什么区别?是SetElement5重写了hashCode方法。
可见HashSet中是采用了比较元素hashCode的方法来判断元素是否相同(duplicate),而不是采用其他类似equals之类的东东来判断。
说了这么多,那java类库中到底有没有根据equals来判断元素是否相同(duplicate)的Set呢?请看下文。
2.2、CopyOnWriteArraySet部分:
类CopyOnWriteArraySet是java.util.concurrent包中的一个类,所以它是线程安全的。
CopyOnWriteArraySet是使用CopyOnWriteArrayList作为其盛放元素的容器。当往CopyOnWriteArrayList添加新元素,它都要遍历整个List,并且用equals来 比较两个元素是否相同。
请看示例程序6:
import java.util.*;
import java.util.concurrent.*;
public class SetTest6 {
public static void main(String[] args){
Set set = new CopyOnWriteArraySet();
set.add(new SetElement6("aa"));
set.add(new SetElement6("aa"));
set.add(new SetElement6("bb"));
System.out.println(set);
}
static class SetElement6{
String s;
public SetElement6(String s){
this.s = s;
}
public String toString(){
return s;
}
public boolean equals(Object obj) {
return s.equals(((SetElement6)obj).s);
}
}
}
运行结果:
[aa, bb]
好了,一切搞定!!
3、总结:
Javadoc中的一些描述可能是不准确的,大家要当心了!
Set中实现元素互异的各种方法差异很大,大致可以分为三种:使用equals,使用hashCode,使用compareTo。但是我还没有发现采用“判断地址空间是否相同”来判断元素是否相同的类,当然我们可以用现有的三种方法来实现“判断地址空间是否相同”。
综上所述,我们可以总结出使用Set的三种不同的情形:(以下假设元素类为Element)
A、如果想使用Element的equals方法来判断元素是否相同,那么可以使用CopyOnWriteArraySet来构造类的实体。
B、如果Element实现了Comparable接口,而且想使用compareTo方法来判断元素是否相同,那么可以使用TreeSet来构造类的实体。
C、如果想使用判断hashCode是否相同的方法来判断元素是否相同,那么可以使用HashSet来构造类的实体
发表于 @ 2009年12月17日 17:
本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/pss360/archive/2009/12/17/5026516.aspx
[]
更多精彩
赞助商链接