iamjq 2014-09-17 18:33
浏览 440
已采纳

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]

  • 写回答

3条回答 默认 最新

  • ll89308839 2014-09-18 14:12
    关注

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

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题?

悬赏问题

  • ¥15 mysql , 用自己创建的本地主机和用户名 登录不上
  • ¥15 关于#web项目#的问题,请各位专家解答!
  • ¥15 vmtools环境不正常
  • ¥15 请问如何在Ubuntu系统中安装使用microsoft R open?
  • ¥15 jupyter notebook
  • ¥30 informer时间序列预测
  • ¥20 SSR引物多态性分析
  • ¥15 大漠插件在Win11易语言注册调用和免注册灵异事件,VS上注册调用完全没问题
  • ¥15 Addressable缓存机制做热更新的问题
  • ¥15 微信开发者工具vant组件