为什么HashMap有时会按自然顺序打印输出

Question

我正在学习Java中的HashMap，发现HashMap是无序且未排序的。因此，当使用System.out.println(HM)打印时，键值对会以任意顺序显示。例如，下面的代码：

HashMap<Integer,String> HM = new HashMap<>();
HM.put(16,"hello16");
HM.put(6, "hello6");
HM.put(1, "hello1");

打印出来的是{16=hello16, 1=hello1, 6=hello6}，看起来是键的随机顺序。但是当我将 HM.put(16,"hello16"); 替换为 HM.put(15,"hello15"); 时，它会按照键的自然顺序打印映射结果，这一点令人惊讶并且不太可能偶然发生：

{1=hello1, 6=hello6, 15=hello15}

我问了一个朋友，他说这与HashMap的初始容量（=16）有关，但他不能清楚地解释。有人能用这个特定的例子解释一下输出的差异吗？

- arjun gulyani

---

这种情况发生的原因并不重要，因为你不应该依赖它。在Java 9中，Set#of和Map#of的插入顺序是随机的，正是出于这个原因。 - Jacob G.

所以我们应该随机获取键的映射。不，HashMap不保证随机顺序。它对顺序将会是什么样子没有任何承诺。 - user2357112

今天它可能按照内部桶的顺序排序。下一个版本，它可能像Go一样随机排序。在别人的机器上，它可能像新的Python字典实现一样按插入顺序排序。 - user2357112

“似乎不太可能是偶然的”：你有1/6的机会让3个值自然排序，但你已经尝试了一次并没有成功。 - chrylis -cautiouslyoptimistic-

Answer 1

Integer的hashCode值即为其本身的值。您的HashMap有16个桶，这意味着分配给该值的桶是key % 16，它是从0到15的数字。

如果您的键在0到15的范围内，则桶号码就是键。只有在使用大于15或小于0的键时，才会变得混乱。

打印HashMap时，条目按照桶的顺序出现。也就是说，在桶0中的键先被打印，如果存在的话；然后是桶1中的键，依此类推。对于所有键都介于0和15之间的HashMap，这与键的顺序完全相同。

- Dawood ibn Kareem

---

一个程序员不应该依赖于那个顺序或者桶的大小。这是一个内部实现细节，可能会随着时间（从版本到版本）而改变。 - tobain

@tobain 你说得完全正确。但问题是，为什么会在OP的当前代码中发生这种情况。 - Dawood ibn Kareem

Answer 2

该代码打印出{16=hello16, 1=hello1, 6=hello6}，这是键的随机顺序。

顺序可能看起来任意，但它是确定性的。顺序基于三个因素：

• 键的哈希码的值，
• 哈希表中的桶数，以及
• 插入键的顺序（用于决定具有相同哈希键的项的顺序）

枚举哈希表条目通过哈希桶进行。由于哈希桶的数量低于可能哈希码的范围，哈希码的值间接转换为哈希桶的索引。Java implementation在哈希键上应用了一个补充哈希函数，然后使用位运算符&来获取实际索引：

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);
}
...
static int indexFor(int h, int length) {
    return h & (length-1);
}

您可以从indexFor代码中看到，期望length是2的幂次方（这就是为什么他们可以使用& (length-1)而不是% length表达式）。在您的情况下，这很重要，因为整数的哈希码匹配相应整数的值。假设有16个桶的容量，16将转换为零号桶，而15将转换为15号桶（桶从零开始编号）。

这就是为什么您示例中的15值会从前面移动到后面的原因。

- Sergey Kalinichenko

Answer 3

HashMap 使用键的哈希码将映射条目抛入桶的索引数组中。检索顺序是更或多或少随意的。作为长度相同但仅在最后一个字符不同的字符串，通常具有等于 X + 最后一个字符的哈希码，因此它们之间存在一种顺序。

另一个实现 Map 接口的类 TreeMap 是一个SortedMap，并按键的顺序保留条目。

还有另一种 Map 实现是 LinkedHashMap，其中顺序是按照将条目放入映射中的顺序。

- Joop Eggen