关于SET元素不反复的实现
关于SET元素不重复的实现
set的实现类HashSet/TreeSet的底层实现是通过HashMap/TreeMap来实现的。Set的实现类在创建对象的时候都,在构造方法里面都是创建了一个Map的实现类来实现的。而Map中的元素是“键-值”对,其中“键”必须是唯一的。Set就是利用“键”唯一这个特性来实现元素不重复的。它把Set中的元素作为Map的键,从而保持了元素的唯一性。
呵呵,分析的比较粗糙,大家参考哈就是了哈。其实有一个CopyOnWriteArraySet,这个类是AbstractSet的子类。它在实现元素不重复的时候就是用的是List遍历的,采用了equals来实现元素不重复,大家有机会可以看看了。
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来实现元素不重复,大家有机会可以看看了。