Java 如何对 HashMap 或 HashTable 中的项目进行排序？

How does Java order items in a HashMap or a HashTable?

提问by Eyad Salah

I was wondering how Java orders items in the Map(HashMapor Hashtable) when they are added. Are the keys ordered by the hashcode, memory reference or by allocation precedence...?

我想知道 Java 是如何在Map(HashMap或Hashtable) 中添加项目的。键是按哈希码、内存引用还是按分配优先级排序的...？

It's because I've noticed same pairs in the Mapare not always in the same order

这是因为我注意到相同的对Map并不总是以相同的顺序

采纳答案by polygenelubricants

java.util.HashMapis unordered; you can't and shouldn't assume anything beyond that.

java.util.HashMap是无序的；你不能也不应该假设除此之外的任何事情。

This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

此类不保证地图的顺序；特别是，它不保证订单会随着时间的推移保持不变。

java.util.LinkedHashMapuses insertion-order.

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

This implementation differs from HashMapin that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).

此实现的不同之处HashMap在于它维护一个贯穿其所有条目的双向链表。这个链表定义了迭代顺序，这通常是键被插入到映射中的顺序（插入顺序）。

java.util.TreeMap, a SortedMap, uses either natural or custom ordering of the keys.

java.util.TreeMap, a SortedMap, 使用键的自然或自定义排序。

The map is sorted according to the natural ordering of its keys, or by a Comparatorprovided at map creation time, depending on which constructor is used.

地图根据其键的自然顺序进行排序，或者根据Comparator地图创建时提供的顺序进行排序，具体取决于使用的构造函数。

回答by Behrang Saeedzadeh

HashMapdoes not sort at all. For a map that sorts by key values you should use TreeMapinstead.

HashMap根本不排序。对于按键值排序的地图，您应该TreeMap改用。

From the JavaDocs for TreeMap:

来自 JavaDocs 的TreeMap：

Red-Black tree based implementation of the SortedMap interface. This class guarantees that the map will be in ascending key order, sorted according to the natural order for the key's class (see Comparable), or by the comparator provided at creation time, depending on which constructor is used.

SortedMap 接口的基于红黑树的实现。此类保证映射将按键升序排列，根据键的类的自然顺序（请参阅 Comparable）排序，或按创建时提供的比较器排序，具体取决于使用的构造函数。

From the documentation of HashMap:

从文档HashMap：

This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

此类不保证地图的顺序；特别是，它不保证订单会随着时间的推移保持不变。

回答by Jesper

A Mapis not an ordered data structure - you should not rely on entries in a HashMapbeing in a certain order. Some Mapimplementations such as LinkedHashMapand TreeMapdo guarantee a certain order, but HashMapdoes not.

AMap不是有序的数据结构 - 您不应该依赖HashMap某个顺序中的条目。一些Map实现，例如LinkedHashMap和TreeMap确实保证了某个顺序，但HashMap不保证。

If you really want to know what happens internally, lookup the source code of HashMap- you can find it in src.zipwhich should be in your JDK installation directory.

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

A HashMaphas a number of "buckets" in which it stores its entries. Which bucket an entry is stored in is determined by the hash code of the key of the entry. The order in which you see the entries in the HashMapdepends on the hash codes of the keys. But don't write programs that rely on entries being in a certain order in a HashMap- the implementation might change in a future version of Java and your program then would not work anymore.

AHashMap有许多“存储桶”，用于存储其条目。条目存储在哪个桶中，由条目的键的哈希码决定。您在 中看到条目的顺序HashMap取决于键的哈希码。但是不要编写依赖于 a 中特定顺序的条目的程序HashMap- 实现可能会在 Java 的未来版本中发生变化，然后您的程序将不再工作。

回答by Marcelo Cantos

There is no defined ordering in a hash table. Keys are placed into a slot, based on the hash code, but even that isn't a trivial order-by-hash-code.

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

回答by Robar

hashmap has a not defined order of the elements

hashmap 没有定义元素的顺序

回答by Joachim Sauer

First of all: HashMapspecifically doesn'tprovide a stable and/or defined ordering. So anything you observe is simply an implementation detail and you must notdepend on it in any way.

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

Since it is sometimes useful to know the reason for the seemingly random ordering, here's the basic idea:

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

A HashMaphas number of buckets (implemented as an array) in which to store entries.

AHashMap具有用于存储条目的多个桶（实现为数组）。

When an item is added to the map, it is assigned to a buckets based on a value derived of its hashCodeand the bucket size of the HashMap. (Note that it's possible that the bucket is already occupied, which is called a collision. That's handled gracefully and correctly, but I'll ignore that handling for the description because it doesn't change the concept).

当一个项目被添加到地图时，它会根据其派生的值hashCode和HashMap. （请注意，桶可能已经被占用，这被称为碰撞。处理得体和正确，但我将忽略描述中的处理，因为它不会改变概念）。

The perceived ordering of the entires (such as returned by iterating over the Map) depends on the order of the entries in those buckets.

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

Whenever the size is rehashed (because the map exceeded its fullness threshold), then the number of buckets changes, which means that the position of each element might change, since the bucket position is derived from the number of buckets as well.

每当大小重新散列时（因为地图超过了其满度阈值），桶的数量就会发生变化，这意味着每个元素的位置可能会发生变化，因为桶的位置也是从桶的数量中得出的。

回答by Vaishak Suresh

HashMap stores the values using the unique hash-value generated using a part of the key. This hash-value maps to the address where it is going to be stored. This is how it ensures an access O(1).

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

LinkedHashmap on the other hand preserves the order in which you added to the map.

另一方面，LinkedHashmap 保留您添加到地图的顺序。