[Solved] Why a hashtable does not maintain order of insertion? [duplicate]

Question

To be brief, a hash table (dictionary) does not maintain a total order of insertions because it doesn’t need to. The abstract data type supports ammortized O(1) insertions, deletions, and searches, but does not support enumeration, and does not impose any order on the elements in the key set.

HashTable implements a dictionary, and total order of insertions is not retained because insertions with different hash values map to different chains. In the case of a dictionary implementation using chaining, keys with colliding hashes are stored in a linked list (as stated in the question), and are indeed maintained in order of insertion. There exist many other (faster) implementations of dictionaries that do not have this property. Please see the thees lecture notes for a discussion of open addressing (a dictionary implementation pattern that does not retain insertion order of colliding elements). Open addressing with double hashing, in particular, does not impose any order on the elements stored in the key set.

Accepted Answer

To be brief, a hash table (dictionary) does not maintain a total order of insertions because it doesn’t need to. The abstract data type supports ammortized O(1) insertions, deletions, and searches, but does not support enumeration, and does not impose any order on the elements in the key set.

HashTable implements a dictionary, and total order of insertions is not retained because insertions with different hash values map to different chains. In the case of a dictionary implementation using chaining, keys with colliding hashes are stored in a linked list (as stated in the question), and are indeed maintained in order of insertion. There exist many other (faster) implementations of dictionaries that do not have this property. Please see the thees lecture notes for a discussion of open addressing (a dictionary implementation pattern that does not retain insertion order of colliding elements). Open addressing with double hashing, in particular, does not impose any order on the elements stored in the key set.