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

Question

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

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

Answer 1

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

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.LinkedHashMap uses insertion-order.

This implementation differs from HashMap in 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).

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

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

Answer 2

First of all: HashMap specifically doesn't provide a stable and/or defined ordering. So anything you observe is simply an implementation detail and you must not depend on it in any way.

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

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

When an item is added to the map, it is assigned to a buckets based on a value derived of its hashCode and 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).

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

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.