java - 尽管 HashMap 是一个无序集合，但为什么它会自动对字符类型键进行排序？

Question

我创建了一个小代码示例来演示 HashMap 和 TreeMap 的区别。

public class HashMapSimpleValueAutosort {

    private static final char[] alphabet = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};

    public static void main(String[] args) {

        Map<Character, Integer> map = new HashMap<>();

        inverseAbc(map, "HashMap");

        map = new TreeMap<>();

        inverseAbc(map, "TreeMap");
    }

    private static void inverseAbc(Map<Character, Integer> map, String desc ) {

        System.out.println(desc);

        for (int i=25; i>=0; --i) {
            map.put(alphabet[i], 26 - i);
        }
        System.out.println(map);
    }

}

它的作用是使用 HashMap 和 TreeMap 方法将映射内的字母按相反顺序指定为键，并将它们在字母表中的位置指定为相应的值。

尽管键是按相反顺序插入的，但 HashMap toString() 却按升序输出它们，就像 TreeMap 一样。

所以这里出现的问题是:

HashMap 的 toString() 方法在返回映射的字符串表示之前是否在内部对键进行排序？

编辑:

这似乎是基于 JDK 或 IDE 的症状，并且不仅仅限于 toString()。

public class HashMapSimpleValueAutosort {

    private static final char[] alphabet = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};

    public static void main(String[] args) {

        Map<Character, Integer> map = new HashMap<>();

        printEntries(map, "HashMap");

        map = new TreeMap<>();

        printEntries(map, "TreeMap");
    }


    private static void printEntries(Map<Character, Integer> map, String desc) {

        System.out.println(desc);

        for (int i=25; i>=0; --i) {
            map.put(alphabet[i], 26 - i);
        }

        System.out.print("{ ");
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            System.out.printf("%c=%d,", entry.getKey(), entry.getValue());
        }
        System.out.println(" }");
    }

}

在上面的示例中，我将键值对打印为条目。

Answer 1

这是 HashMap 实现的一个奇怪的结果。

HashMap 必须决定将条目放置在哪个哈希桶中。它根据 key 对象的 hashCode() 来决定。现在，hashCode() 可以是任何整数。所以它首先对哈希码执行此操作:

(h = key.hashCode()) ^ (h >>> 16)

现在，在本例中您的 key 属于 Character 类型。 Character 的 hashCode 是字符本身的值。 Java char 是 16 位宽。因此向右移动 16 位将得到零。将其与零进行异或即可得到原始值 - char 值!

您选择的值是连续的。这意味着它们将恰好存储在哈希表桶中索引为 i、i+1、i+2...

这也恰好是 toString 所基于的条目集迭代器遍历该表的顺序:它连续地遍历该表。因此，只要不发生冲突，对于恰好连续的 Character 键，您就会看到结果“已排序”。