Java中TreeSet与HashSet的对比

偏执的太偏执、 2022-07-19 05:59 204阅读 0赞

我们知道TreeSet与HashSet都实现了Set<E>，Set的特性就是不允许重复的元素。《thinking in Java》中说set必须定义equals方法确保对象的唯一性，但是经过测试貌似不是这样，不知道是不是java1.5以后版本改变后造成的。下面就从唯一性展开问题，先看例子：

先来看HashSet：

package testsortset;
 
 import java.util.HashSet;
 import java.util.TreeSet;
 
 public class TestHashSet {
 	public static void main(String[] args) {
 		HashSet setsB = new HashSet();
 		setsB.add(new B(1));
 		setsB.add(new B(2));
 		setsB.add(new B(3));
 		setsB.add(new B(3));
 		B b4 = new B(4);
 		B b4_ = new B(4);
 		setsB.add(b4);
 		setsB.add(b4_);
 		System.out.println(b4.equals(b4_));
 		
 		for (B b : setsB) {
 			System.out.println(b.i);
 		}
 	}
 }
 
 class B {
 	public int i;
 	
 	public B(int n) {
 		this.i = n;
 	}
 	
 //	@Override
 //	public boolean equals(Object obj) {
 //		return (obj instanceof B) && (this.i == ((B) obj).i);
 //	}
 //	
 //	@Override
 //	public int hashCode() {
 //		return i;
 //	}
 }

输出：

false  
3  
4  
1  
2  
3  
4  
第一个false，很好理解，因为我们没有覆盖equals方法，类B继承自Object的equals方法，比较的是类内存地址的hashcode。

这里我估计注释了equals和hashcode方法，确实，hashset中包含了重复的元素。接下来打开注释（先只打开equals方法）：

package testsortset;
 
 import java.util.HashSet;
 import java.util.TreeSet;
 
 public class TestHashSet {
 	public static void main(String[] args) {
 		HashSet setsB = new HashSet();
 		setsB.add(new B(1));
 		setsB.add(new B(2));
 		setsB.add(new B(3));
 		setsB.add(new B(3));
 		B b4 = new B(4);
 		B b4_ = new B(4);
 		setsB.add(b4);
 		setsB.add(b4_);
 		System.out.println(b4.equals(b4_));
 		
 		for (B b : setsB) {
 			System.out.println(b.i);
 		}
 	}
 }
 
 class B {
 	public int i;
 	
 	public B(int n) {
 		this.i = n;
 	}
 	
 	@Override
 	public boolean equals(Object obj) {
 		return (obj instanceof B) && (this.i == ((B) obj).i);
 	}
 	
 //	@Override
 //	public int hashCode() {
 //		return i;
 //	}
 }

输出：

true  
3  
4  
1  
2  
3  
4  
第一个true很好理解，因为我们覆盖了equals方法。但是为什么还是含有重复的元素呢？！为什么和书上说的不一样，确定唯一性由equals方法确定呢？先不着急，再打开hashcode方法的注释看看：

package testsortset;
 
 import java.util.HashSet;
 import java.util.TreeSet;
 
 public class TestHashSet {
 	public static void main(String[] args) {
 		HashSet setsB = new HashSet();
 		setsB.add(new B(1));
 		setsB.add(new B(2));
 		setsB.add(new B(3));
 		setsB.add(new B(3));
 		B b4 = new B(4);
 		B b4_ = new B(4);
 		setsB.add(b4);
 		setsB.add(b4_);
 		System.out.println(b4.equals(b4_));
 		
 		for (B b : setsB) {
 			System.out.println(b.i);
 		}
 	}
 }
 
 class B {
 	public int i;
 	
 	public B(int n) {
 		this.i = n;
 	}
 	
 	@Override
 	public boolean equals(Object obj) {
 		return (obj instanceof B) && (this.i == ((B) obj).i);
 	}
 	
 	@Override
 	public int hashCode() {
 		return i;
 	}
 }

输出：

true  
1  
2  
3  
4  
是的，现在你看到了你想要的结果。确定了唯一性。我们可以知道hashset确定唯一性由equals和hashcode两个方法同时确定。当然，另一种情况注释equals，留下hashcode的情况可以试一下也是一样的包含重复的元素，这里就不贴代码了。

为什么呢？

原因：我们知道hashset底层是由hashmap实现的，也就是说是否包含重复元素由hashmap确定，我们可以看一下hashmap的put方法：（hashmap 1.8的实现是数组+链表+红黑树）

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
 boolean evict) {
 Node<K,V>[] tab; Node<K,V> p; int n, i;
 if ((tab = table) == null || (n = tab.length) == 0)
 n = (tab = resize()).length;
 if ((p = tab[i = (n - 1) & hash]) == null)
 tab[i] = newNode(hash, key, value, null);
 else {
 Node<K,V> e; K k;
 if (p.hash == hash &&
 ((k = p.key) == key || (key != null && key.equals(k))))
 e = p;
 else if (p instanceof TreeNode)
 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
 else {
 for (int binCount = 0; ; ++binCount) {
 if ((e = p.next) == null) {
 p.next = newNode(hash, key, value, null);
 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
 treeifyBin(tab, hash);
 break;
 }
 if (e.hash == hash &&
 ((k = e.key) == key || (key != null && key.equals(k))))
 break;
 p = e;
 }
 }
 if (e != null) { // existing mapping for key
 V oldValue = e.value;
 if (!onlyIfAbsent || oldValue == null)
 e.value = value;
 afterNodeAccess(e);
 return oldValue;
 }
 }
 ++modCount;
 if (++size > threshold)
 resize();
 afterNodeInsertion(evict);
 return null;
 }

从源码可以看出，当hashmap在put一个元素时，确定该元素是否已经存在hashcode和equals两个方法确定的。

接下来看TreeSet：

package testsortset;
 
 import java.util.TreeSet;
 
 public class TestSortedSet {
 	public static void main(String[] args) {
 		TreeSet<A> sets = new TreeSet<A>();
 		sets.add(new A(1));
 		sets.add(new A(2));
 		sets.add(new A(3));
 		sets.add(new A(3));
 		A a4 = new A(4);
 		A a4_ = new A(4);
 		sets.add(a4);
 		sets.add(a4_);
 		System.out.println(a4.equals(a4_));
 		
 		for (A a : sets) {
 			System.out.println(a.i);
 		}
 	}
 }
 
 class A implements Comparable<A> {
 	public int i;
 
 	public A(int n) {
 		this.i = n;
 		//System.out.println(i);
 	}
 
 	@Override
 	public int compareTo(A o) {
 //		if (o.i > this.i) {
 //			return -1;
 //		} else if (o.i < this.i) {
 //			return 1;
 //		} else {
 //			return 0;
 //		}
 		return 0;
 	}
 
 	@Override
 	public boolean equals(Object obj) {
 //		return (obj instanceof A) && (this.i == ((A) obj).i);
 		return false;
 	}
 	
 }

输出：

false  
1

第一个false很好理解，equals不管怎样都返回false。为什么只有一个元素呢？不是由equals方法确定吗？应该每个元素都不相等，应该是多个元素的啊。我们改一改（我们知道sortedSet中的元素要实现comparable接口或者使用comparator）：

package testsortset;
 
 import java.util.TreeSet;
 
 public class TestSortedSet {
 	public static void main(String[] args) {
 		TreeSet<A> sets = new TreeSet<A>();
 		sets.add(new A(1));
 		sets.add(new A(2));
 		sets.add(new A(3));
 		sets.add(new A(3));
 		A a4 = new A(4);
 		A a4_ = new A(4);
 		sets.add(a4);
 		sets.add(a4_);
 		System.out.println(a4.equals(a4_));
 		
 		for (A a : sets) {
 			System.out.println(a.i);
 		}
 	}
 }
 
 class A implements Comparable<A> {
 	public int i;
 
 	public A(int n) {
 		this.i = n;
 	}
 
 	@Override
 	public int compareTo(A o) {
 		if (o.i > this.i) {
 			return -1;
 		} else if (o.i < this.i) {
 			return 1;
 		} else {
 			return 0;
 		}
 	}
 
 	@Override
 	public boolean equals(Object obj) {
 		return (obj instanceof A) && (this.i == ((A) obj).i);
 	}
 	
 }

输出：

true  
1  
2  
3  
4

发现这才是你预期的效果，是的。猜想，是不是由compareTo方法来确定是否唯一的？我们再做一个测试：

package testsortset;
 
 import java.util.TreeSet;
 
 public class TestSortedSet {
 	public static void main(String[] args) {
 		TreeSet<A> sets = new TreeSet<A>();
 		sets.add(new A(1));
 		sets.add(new A(2));
 		sets.add(new A(3));
 		sets.add(new A(3));
 		A a4 = new A(4);
 		A a4_ = new A(4);
 		sets.add(a4);
 		sets.add(a4_);
 		System.out.println(a4.equals(a4_));
 		
 		for (A a : sets) {
 			System.out.println(a.i);
 		}
 	}
 }
 
 class A implements Comparable<A> {
 	public int i;
 
 	public A(int n) {
 		this.i = n;
 	}
 
 	@Override
 	public int compareTo(A o) {
 		if (o.i > this.i) {
 			return -1;
 		} else if (o.i < this.i) {
 			return 1;
 		} else {
 			return 0;
 		}
 	}
 
 	@Override
 	public boolean equals(Object obj) {
 //		return (obj instanceof A) && (this.i == ((A) obj).i);
 		return true;
 	}
 	
 }

输出：

true  
1  
2  
3  
4

第一个true很好理解，后边的元素不是一个就说明跟equals没有关系，而是跟compareTo方法有关系，也就是说treeset的唯一性由compareTo方法确定。为什么（treeset的底层由treeMap实现）？那么看看treeMap的put方法：

public V put(K key, V value) {
 Entry<K,V> t = root;
 if (t == null) {//有无根节点
 compare(key, key); // type (and possibly null) check
 
 root = new Entry<>(key, value, null);
 size = 1;
 modCount++;
 return null;
 }
 int cmp;
 Entry<K,V> parent;
 // split comparator and comparable paths
 Comparator<? super K> cpr = comparator;
 if (cpr != null) {//是否有comparator
 do {
 parent = t;
 cmp = cpr.compare(key, t.key);//根据comparator比较的结果确定插入树中的左子树，右子树还是设值
 if (cmp < 0)
 t = t.left;
 else if (cmp > 0)
 t = t.right;
 else
 return t.setValue(value);
 } while (t != null);
 }
 else {
 if (key == null)
 throw new NullPointerException();
 @SuppressWarnings("unchecked")
 Comparable<? super K> k = (Comparable<? super K>) key;
 do {
 parent = t;
 cmp = k.compareTo(t.key);根据compareTo比较的结果确定插入树中的左子树，右子树还是设值
 if (cmp < 0)
 t = t.left;
 else if (cmp > 0)
 t = t.right;
 else
 return t.setValue(value);
 } while (t != null);
 }
 Entry<K,V> e = new Entry<>(key, value, parent);
 if (cmp < 0)
 parent.left = e;
 else
 parent.right = e;
 fixAfterInsertion(e);
 size++;
 modCount++;
 return null;
 }

从源码中我们可以知道，确定TreeSet唯一性的是Comparable或者Comparator，跟equals方法没有关系。

总结：set集合具有唯一元素的特性，而不同具体的set的集合有差别。

存入HashSet的元素必须定义hashcode和equals方法，共同确定唯一性。并且它是没有顺序的。

存入TreeSet的元素必须实现接口Comparable或者传入比较实现Comparator，equals根据具体情况覆盖，跟唯一性没有关系。由于TreeSet有红黑树实现，所以是有序的。