TreeSet 的 contains 问题

[code="java"]import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

public class TreeSetTest {

public void testCompare(){
    Map<String,String> m1 = new HashMap<String,String>();
    m1.put("AC029", "SE.mg");

    Map<String,String> m2 = new HashMap<String,String>();
    m2.put("OS05M", "USD");

    Map<String,String> m3 = new HashMap<String,String>();
    m3.put("OS01W", "Stratic Energy Corp");
    m3.put("OS001", "SE");
    m3.put("LS01Z", "EX$$$$XTSX");
    m3.put("OS06Y", "0P00005RTY");
    m3.put("AA0B5", "0C00000KDB");
    m3.put("ST735", "IG000DA093");

    Map<String,String> m4 = new HashMap<String,String>();
    m4.put("OS01W", "Spectra Energy Corp");
    m4.put("OS05K", "847560109");

    Map<String,String> m5 = new HashMap<String,String>();
    m5.put("OS01W","Spectra Energy Corp");
    m5.put("OS05K","847560109");
    m5.put("OS05J","US8475601097");
    m5.put("AA0B5","0C00000MIG");
    m5.put("IT152","309");
    m5.put("AA0F4","3");
    m5.put("ST735","IG000DA096");
    m5.put("OS05M","USD");

    Map<String,String> m6 = new HashMap<String,String>();
    m6.put("OS01W","Spectra Energy Corp");
    m6.put("OS05K","847560109");
    m6.put("LS01Z","EX$$$$XNYS");
    m6.put("OS00I","0P00007KRO");
    m6.put("AC020","SPECTRA ENERGY Corp");
    m6.put("AA0B5","0C00000MIG");
    m6.put("ST735","IG000DA096");

    Map<String,String> m7 = new HashMap<String,String>();
    m7.put("OS01W","Spectra Energy Corp");
    m7.put("OS05K","847560109");
    m7.put("AC020","SPECTRA ENERGY Corp");
    m7.put("AA0B5","0C00000MIG");
    m7.put("ST735","IG000DA096");

    Map<String,String> m8 = new HashMap<String,String>();
    m8.put("OS01W","Spectra Energy Corp");
    m8.put("OS05K","847560109");
    m8.put("LS01Z","EX$$$$XNYS");
    m8.put("AA0B5","0C00000MIG");
    m8.put("ST735","IG000DA096");
    m8.put("OS05M","USD");

    Set<Map<String,String>> set = new TreeSet<Map<String,String>>(new HashCompare());
    set.add(m1);
    set.add(m2);
    set.add(m3);
    set.add(m4);
    set.add(m5);
    set.add(m6);
    set.add(m7);
    set.add(m8);

    System.out.println(set.contains(m3));
}

class HashCompare implements Comparator{

    public int compare(Object o1, Object o2) {
        return o1.hashCode() - o2.hashCode();
    }
}

public static void main(String[] args) {
    TreeSetTest ts = new TreeSetTest();
    ts.testCompare();
}

}[/code]

0
iamjq
iamjq 在所有的 HashMap 中任意改1个key或者value的值都可以打印 true.
接近 5 年之前 回复

3个回答

首先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可以为负数,那么大小的判断就会有误,从而二叉树那里除了问题。修改一下代码即可
[code="java"]
class HashCompare implements Comparator{

    @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;
    }  
} 

[/code]

0
javaStudyeye
javaStudyeye 如果存储结构是treeMap, 那么, 左右孩子的判断只是 大于0 小于 0 等于 0 , 就算是之外, 应该也没关系的。
接近 5 年之前 回复
iamjq
iamjq 任何改动就可以找到 m3 了。 应该是正如 kidding87 同学说的,二叉树的算法问题。因为我那个 comparator 返回的值有的是在 [-1,0,1] 之外的。
接近 5 年之前 回复
javaStudyeye
javaStudyeye 为什么 楼主的源代码中, 再次添加m3 是可以的呢? 难道treeMap在put数据的时候,同时改变了,hashcode么?
接近 5 年之前 回复
ll89308839
ll89308839 还有把treeset换为hashset就非常明显能看出来这个问题了
接近 5 年之前 回复

[code="java"]

按照楼主自定义的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 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 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 getEntryUsingComparator(Object key) {
K k = (K) key;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
Entry 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;
}
[/code]

0

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

0
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!