关于SET元素不重复的实现

set的实现类HashSet/TreeSet的底层实现是通过HashMap/TreeMap来实现的。Set的实现类在创建对象的时候都，在构造方法里面都是创建了一个Map的实现类来实现的。而Map中的元素是“键-值”对，其中“键”必须是唯一的。Set就是利用“键”唯一这个特性来实现元素不重复的。它把Set中的元素作为Map的键，从而保持了元素的唯一性。

public class TestTreeSet {
	public static void main(String [] args){
		Set set = new TreeSet();
		set.add(new Element1("aa"));
		set.add(new Element1("bb"));
		set.add(new Element1("aa"));
	}
}
class Element1{
	String s ;
	public Element1(String s){
		this.s = s;
	}
	@Override
	public String toString(){
		return s;
	}
	@Override  //这里重写了equals方法，但是实际是没有作用的。
	public boolean equals(Object obj) {
		return s.equals(((Element1)obj).s);
	}
}
// 报错：java.lang.ClassCastException: com.lovo.TestTreeSet$SetElement cannot be cast to java.lang.Comparable
//at java.util.TreeMap.put(TreeMap.java:542)
//at java.util.TreeSet.add(TreeSet.java:238)
//at com.lovo.TestTreeSet.main(TestTreeSet.java:10)
public class TestTreeSet2 {
	public static void main(String[] args) {
		Set set = new TreeSet();
		set.add(new Element2("ss"));
		set.add(new Element2("qq"));
		set.add(new Element2("ss"));
		System.out.println(set);
	}
}
class Element2 implements Comparable{
	   String s; 
	   public Element2(String s){ 
	    this.s =  s; 
	   } 
	   public String toString(){ 
	    return s; 
	   } 
	   public int compareTo(Object o){ 
	    return s.compareTo(((Element2)o).s); 
	   } 
	   public boolean equals(Object obj) { 
	    return s.equals(((Element2)obj).s); 
	   }
	}
/**
*运行结果：[qq, ss]  --达到我们想要的结果。
*TestTreeSet和TestTreeSet2唯一区别就是Element2实现了Comparable接口。进入TreeMap.java:542其实可以看到TreeSet在添加
*元素的时候是使用了TreeMap的put方法。而put方法的实现是通过实现接口Comparable中的CompareTo方法来实现的。所以TreeSet在添加元素
*的时候是把元素cast to Comparable,再来使用compareTo进行比较。
*综合：TreeSet是使用了CompareTo来实现集合中元素不重复。
*/
public class TestTreeSet3 {
	public static void main(String[] args) {
		Set set = new TreeSet();
		set.add(new Element3("ss"));
		set.add(new Element3("qq"));
		set.add(new Element3("ss"));
		System.out.println(set);
	}
}
class Element3 implements Comparable{
	   String s; 
	   public Element3(String s){ 
	    this.s =  s; 
	   } 
	   public String toString(){ 
	    return s; 
	   } 
	   public int compareTo(Object o){ 
	    return -1; 
	   } 
	   public boolean equals(Object obj) { 
	    return s.equals(((Element2)obj).s); 
	   }
	}
/**
*运行结果：[ss, qq, ss]  --没有实现元素不重复。
*原因：重写了compareTo方法返回值是-1，把所有的元素都作为不同的元素处理。
*/
public class TestHashSet1 {
	public static void main(String[] args) {
		Set set = new HashSet();
		set.add(new Element4("kkk"));
		set.add(new Element4("jjj"));
		set.add(new Element4("kkk"));
		System.out.println(set);
	}
}
class Element4{
	String s;
	public Element4(String s) {
		super();
		this.s = s;
	}
	@Override
	public boolean equals(Object obj) {
		return s.equals(((Element4)obj).s);
	}
	@Override
	public String toString() {
		// TODO Auto-generated method stub
		return s;
	}
}
/**
 * 运行结果：[jjj, kkk, kkk]  --重写了equals没有达到元素不重复的要求
 */
public class TestHashSet2 {
	public static void main(String [] args){
		Set set = new HashSet();
		set.add(new Element5("kkk"));
		set.add(new Element5("jjj"));
		set.add(new Element5("kkk"));
		System.out.println(set);
	}
}
class Element5{
	String s;
	public Element5(String s) {
		super();
		this.s = s;
	}
	@Override
	public int hashCode() {
		// TODO Auto-generated method stub
		return s.hashCode();
	}
	@Override
	public String toString() {
		// TODO Auto-generated method stub
		return s;
	}
	@Override
	public boolean equals(Object obj) {
		return s.equals(((Element5)obj).s);
	}
}
/**
 * 运行结果：[jjj, kkk]--达到了元素不重复的要求
 * 值得注意的是：在类Element5中重写了hashCode方法和equals方法，这两个方法都是不可缺的
 * 缺了其中一个就不能达到元素不重复的效果了。
 * 看看源码的方法：
 *     public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }
    其中的有这样的条件：e.hash == hash && ((k = e.key) == key || key.equals(k))可以看出，如果这个条件成立的话，
    那么就是说明元素的重复的，就不会添加元素了。而这个条件所需要的恰好是hashCode方法和equals方法。所以说HashSet实现
    元素不重复是使用了：hashCode方法和equals方法。
 */

呵呵，分析的比较粗糙，大家参考哈就是了哈。其实有一个CopyOnWriteArraySet，这个类是AbstractSet的子类。它在实现元素不重复的时候就是用的是List遍历的，采用了equals来实现元素不重复，大家有机会可以看看了。