如何避免在放入Java HashMap时重新排序项目

Question

我正在创建一个新的 Map 并将字符串推入其中（没什么大不了的）- 但我注意到随着 Map 的增长，字符串正在被重新排序。是否有可能停止这种重新排序，使 Map 中的项目保留它们被插入时的顺序？

Map<String,String> x = new HashMap<String, String>();
x.put("a","b");
x.put("a","c");
x.put("a","d");

x.put("1","2");
x.put("1","3");
x.put("1","4");

//this shows them out of order sadly...
for (Map.Entry<String, String> entry : x.entrySet()) {
    System.out.println("IN THIS ORDER ... " + entry.getValue());
}

- Toran Billups

---

如果它没有排序，那么它就不可能是一个哈希映射。 - tdammers

我的意思是，哈希映射存储算法按照它们的哈希值对条目进行排序，以允许O(log n)的哈希查找（或者说，排序发生在哈希映射存储其条目的方式的副作用中）。按哈希排序不是随机模式，尽管由于哈希值的任意性可能看起来像随机的。 - tdammers

@tdammers 在这里可能打错了——哈希表平均查找时间复杂度为 O(1)；而红黑树则是 O(log n) 的。 - Ray Toal

@Ray Toal：收到，尽管目前的论点还有待完善。 - tdammers

@tdammers 是的，你的观点绝对正确。我只是在吹毛求疵。 - Ray Toal

Answer 1

如果你关心顺序，可以使用一个SortedMap。实际实现该接口的类（至少对于大多数情况）是一个TreeMap。另外，LinkedHashMap也可以保持它的顺序，同时仍然利用基于哈希表的容器。

- dlev

---

请注意，在搜索类的JavaDoc时添加“7”通常会导致链接直接指向最新文档。 - Andrew Thompson

Answer 2

你可以使用 LinkedHashMap 来保持它。

- ssedano

Answer 3

在Java中，HashMap不是有序的http://download.oracle.com/javase/1,5.0/docs/api/java/util/HashMap.html。如果您想要可预测的迭代顺序，请使用LinkedHashMap：http://download.oracle.com/javase/1.4.2/docs/api/java/util/LinkedHashMap.html。

这里有一个关于它们之间区别的讨论：LinkedHashMap的实现与HashMap有何不同？

- bittersweetryan

---

请注意，在搜索类的JavaDoc时添加“7”通常会导致链接直接指向最新文档。 - Andrew Thompson

Answer 4

之前的答案都是正确的，你应该使用一个维护顺序的 Map 实现。LinkedHashMap和SortedMap都可以做到这一点。

然而，需要注意的是，并非所有集合都能保持顺序，如果顺序很重要，你就需要选择适当的实现方式。普通的 HashMap 不会维护顺序，也不会声称这样做，也不能被设置为这样做。

- John B