TreeSet 的 contains 问题

Question

[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]

Answer 1

首先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]