Java如何在HashMap或HashTable中排序项目？

Question

我在想当我们向Map（HashMap或Hashtable）添加条目时，Java是如何对它们进行排序的。键是按照哈希码、内存引用还是分配顺序排序的呢？

这是因为我注意到Map中相同的键值对并不总是以相同的顺序排列。

- Eyad Salah

Answer 1

java.util.HashMap是无序的，你不能也不应该假设除此之外的任何内容。

这个类不保证映射表的顺序；特别地，它不保证顺序会随时间保持不变。

java.util.LinkedHashMap使用插入顺序。

相对于HashMap，这个实现保留了一个双向链表，用以在所有条目中进行迭代。这个链表定义了迭代顺序，通常是按照键被插入到映射表的顺序（插入顺序）。

java.util.TreeMap是一个SortedMap，使用自然排序或自定义键排序。

这个映射表根据其键的自然排序或创建时提供的Comparator进行排序，具体取决于使用哪个构造函数。

- polygenelubricants

---

为什么HashMap每次都遵循相同的可预测序列呢？ - Pop Stack

@pop stack HashMap不保证顺序。有关详细信息，请参阅https://dev59.com/Z3I95IYBdhLWcg3wzRXv上的Stephen C的答案，了解可能如何以及为什么会发生变化。 - Charity Leschinski

这种类型的答案非常好！制作一份速查表来列出Java中所有Map、List、Set之间的区别将是很棒的！ - Cyril N.

@popstack 对于相同的数据，它遵循相同的顺序，因为顺序不是随机的。它是由相同算法处理的相同数据，所以它们在相同的顺序中并不令人惊讶。不要混淆无序和随机放置！ - Zack

Answer 2

首先：HashMap 特别是 没有 提供稳定和/或定义的排序。所以你观察到的任何东西都只是一些实现细节，你 绝不能 以任何方式依赖它。

由于了解看似随机排序的原因有时很有用，以下是基本思想：

HashMap 有许多 bucket（实现为数组）来存储条目。

将项添加到映射中时，它根据其 hashCode 的值和 HashMap 的桶大小分配到一个桶中。(注意，桶可能已经被占用，这称为冲突。虽然可以优雅地正确处理，但我会忽略该处理过程，因为它不影响概念)。

条目的感知顺序（例如通过迭代 Map 返回的顺序）取决于那些桶中的条目的顺序。

每当大小重新哈希（因为 map 超过其满度阈值），那么桶的数量会更改，这意味着每个元素的位置可能会更改，因为桶的位置也是根据桶的数量推导出来的。

- Joachim Sauer

Answer 3

HashMap 不排序。如果需要按键值排序的地图，请改用 TreeMap。

从 TreeMap 的 JavaDocs 中可以看到：

基于红黑树实现的 SortedMap 接口，此类保证地图将按升序键排序，根据键类的自然顺序（参见 Comparable）或在创建时提供的比较器进行排序，具体取决于使用哪个构造函数。

从 HashMap 的文档中可以看到：

此类不保证映射的顺序；特别是，它不能保证顺序随时间保持不变。

- Behrang

---

我从未说过我想要它们排序。我只是在想Java是否可以做到。 - Eyad Salah

Answer 4

Map不是一个有序的数据结构 - 你不应该依赖于HashMap中的条目以某种顺序出现。一些Map实现，如LinkedHashMap和TreeMap确保了一定的顺序，但HashMap没有。

如果你真的想知道内部发生了什么，请查看HashMap的源代码 - 你可以在JDK安装目录下找到src.zip。

HashMap有许多“桶”，用于存储其条目。一个条目存储在哪个桶中取决于条目键的哈希码。在HashMap中看到条目的顺序取决于键的哈希码。但是不要编写依赖于HashMap中的条目以某种顺序出现的程序 - 实现在Java的将来版本中可能会更改，然后你的程序将无法工作。

- Jesper

Answer 5

哈希表的元素没有明确定义的顺序

- Robar

Answer 6

哈希表中没有定义的顺序。键根据哈希码放入一个槽中，但即使如此，这也不是一种简单的哈希码排序。

- Marcelo Cantos

Answer 7

HashMap使用键的一部分生成唯一的哈希值来存储值。这个哈希值映射到它将要存储的地址。这就是它如何确保O(1)的访问。

另一方面，LinkedHashmap保留了您添加到映射中的顺序。

- Vaishak Suresh

---

HashMap 无法保证 O(1)。它尽力而为，但在最坏情况下，时间复杂度是 O(n)，其中 n 是条目数（即使这很不可能发生（或者你的 hashCode 方法实现得非常糟糕））。 - Hardcoded

虽然它并不总是提供恒定时间的性能，但更多时候它确实会尝试这样做。http://java.sun.com/j2se/1.4.2/docs/api/java/util/HashMap.html - Vaishak Suresh