问一个treemap的原理

Question

在向一个 treemap<int, string> put一个元素的时候
他里面的运算逻辑 是不是类似于 b-tree,  2分比较法方式去一步步的找新元素应该放在的 index?还是通过其他方式一次性就定位了index?再问个题外话.要按这么理解的话 那其他任意的只要是用了 b-tree 方式或与之类似方式所实现的 hash集合都是有序的集合呀?
比如 hashmap<int,int> 就应该以int的值的大小为key,  进行大小排序
hashmap<string,int> 就应该以string的char的asscii值进行大小排序.
果然不出我所料 我测试了一下的确是这样: HashMap<Integer, String> testHashSort = new HashMap<Integer, String>();
testHashSort.put(1, "1");
testHashSort.put(3, "3");
testHashSort.put(5, "5");
testHashSort.put(7, "7");
testHashSort.put(2, "2");
testHashSort.put(4, "4");
testHashSort.put(6, "6");
Collection<String> ss = testHashSort.values();
for (String s : ss) {
System.out.println("--->" + s);
}
但是很奇怪,如果把Integer换成String的话结果却与我预期不符,没有能达到 asscii值的那个顺序有知道的请尽量回答和讨论吧.

Answer 1

去看hashmap 里面的源代码，里面有这样的一段 static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }他里面的index是根据hash算法计算出来的，所以Integer和String会不一样。

Answer 2

好问题，不过貌似String型的key也是可以有哈希值的

Answer 3

试了一下，貌似HashMap中的哈希算法大致与输入是成正比例的，所以才会有这种现象，不过也仅仅只是大致可以试下
testHashSort1.put(7, "7");
testHashSort1.put(200001, "200001");
testHashSort1.put(200000, "200000");
testHashSort1.put(4, "4");结果：
--->4
--->7
--->200001
--->200000