TreeSet 的 contains 问题

0 0

采纳的答案

首先treeset的contains方法
使用的是Treemap的containskey的方法
实际使用的就是getEntryUsingComparator，基于comparator的二叉树遍历
通过你这里实现的compare来查找是否有与之对应的类

通过上面的信息，了解到最后一步其实找treeSet放置的元素的hashcode
回到HashMap的hashcode这里

HashMap的hashcode实现比较绕
hashcode = sum(entry.hashcode)//所有的entry的hashcode的和

entry.hashcode= key.hashcode^value.hashcode//key的hashcode和value的hashcode 异或操作

这里发现hashcode的值一定不会有问题，那么比较大小一定不会有问题

那为什么contains会找不到元素呢，其实因为因为楼主对treemap(TreeSet底层、红黑树)的结构不了解，遍历的时候因为值的大小问题遍历导致，这里不详细说明红黑树了，可以自行查看

其实本质是因为 hashcode可以为负数，那么大小的判断就会有误，从而二叉树那里除了问题。修改一下代码即可

class HashCompare implements Comparator<Map>{  

		@Override
		public int compare(Map o1, Map o2) {
			int h1 = o1.hashCode();
			int h2 = o2.hashCode();
			if(h1>h2){
				return 1;
			}else if(h1<h2){
				return -1;
			}
			return 0;
		}  
    }

2014年9月18日 14:12

kidding87
1566
1 1 19

4条评论

0 0

因HashCompare 参与构造树和查找树，所以按照kidding87 的做法是正确的。

2014年9月19日 11:58

JavaStudyEye
1
0 0 3

添加评论

0 0


按照楼主自定义的comparetor对比，画出来的树是：

      m1
    m2  m3
  m4
m5  m6
   m8 m7
   
可以看出是一个排序二叉树
其定义很简单：（1）非叶子节点至少一边的分支非NULL；（2）叶子节点左右分支都为NULL；（3）每一个节点记录一个数据，同时左分支的数据都小于右分支的数据。
对于这个问题： 数据只得是hashcode。



那么 contain是如何查找的呢？其实是：m7 ==> m4 ==》M5


结论：

1、一直m3的hashcode（m3: 2076073718），从二叉树结叶子结点 按照 自定义的 HashCompare 去查找， 分别按照 减法对比hashcode，
      最后找错了，路径，返回null，boolean是false。
2、HashCompare 非常重要，参与构造树，以及查找树。



一下是java源代码跟踪部分：

m1: 117608867
m2: 75431906
m3: 2076073718
m4: -1655436036
m5: -1981877973
m6: -1086123974
m7: -952394827
m8: -1639907518
			
Comparator<? super K> cpr = comparator;
if (cpr != null) {
    do {
        parent = t;
        cmp = cpr.compare(key, t.key);
        if (cmp < 0)
            t = t.left;
        else if (cmp > 0)
            t = t.right;
        else
            return t.setValue(value);
    } while (t != null);
}



调用包含的时候： 你可以在TreeSet中加一个断点看看，此处的m是TreeMap，所以
 public boolean contains(Object o) {
	return m.containsKey(o);
    }

调用treeMap中的containsKey方法
public boolean containsKey(Object key) {
  return getEntry(key) != null;
}

相应的getEntry方法。
 final Entry<K,V> getEntry(Object key) {
        // Offload comparator-based version for sake of performance
        if (comparator != null)
            return getEntryUsingComparator(key);
        if (key == null)
            throw new NullPointerException();
	Comparable<? super K> k = (Comparable<? super K>) key;
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = k.compareTo(p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
    }
    
因为：getEntry（）方法中：comparator 不为null，此处为 自定义的 HashCompare
if (comparator != null)
            return getEntryUsingComparator(key);
            
所以它又调用了 getEntryUsingComparator 方法，注意 此处的key其实是m3, 该方法里面的comparator还是HashCompare

final Entry<K,V> getEntryUsingComparator(Object key) {
	K k = (K) key;
        Comparator<? super K> cpr = comparator;
        if (cpr != null) {
            Entry<K,V> p = root;
            while (p != null) {
                int cmp = cpr.compare(k, p.key);
                if (cmp < 0)
                    p = p.left;
                else if (cmp > 0)
                    p = p.right;
                else
                    return p;
            }
        }
        return null;
    }

2014年9月19日 11:57

JavaStudyEye
1
0 0 3