Why HashMap does not guarantee that the order of the map will remain constant over time

Question

I was reading about difference between Hashmap and Hashtable here: http://javarevisited.blogspot.sg/2010/10/difference-between-hashmap-and.html

Can anyone throw some light on why it says following?

"5. HashMap does not guarantee that the order of the map will remain constant over time."

Could the order change during re-hashing, that is why?

It would be also nice if you could point me to resource or list of collections who exhibit such behavior of not guaranteeing order to be remain constant.

AFIK, ArrayList gives such gurantee (let me know if I am wrong)

EDIT: 'Order of map' = maybe order in which keys or values are entered.

Answer 1

A HashMap has no order - at any time. It is actually not used for that purpose. The order may change even when not rehashing.

If you need the order to remain constant, use a LinkedHashMap

Answer 2

The point of a hashing strategy is to place objects in a pseudo random manner. It does this so that most of the time, only one key/element will be hashed to a given bucket. This allows an O(1) lookup time. When a HashMap or Hashtable grows, the number of buckets changes and the keys/elements are placed in another pseudo random manner.

The simplest solution to this is to use LinkedHashMap. This will keep order of addition or optionally order of last access. I prefer to use this collection because it makes debugging easier as I can predict where an object is likely to be and sometimes the order an object was added can be useful information.

BTW If you are interested in how many orders a small number of keys can have Order of elements in a hash collection