If hash table is an array of linked-list elements and hash code is index of the element in the array then why hash table does not maintain the order of insertion ??
-
2Because it hashes instead. Hashing doesn't preserve ordering.– user207421Commented Apr 15, 2014 at 3:47
-
2en.wikipedia.org/wiki/Hash_table– Anthony AcciolyCommented Apr 15, 2014 at 3:47
-
BTW, iterating while predicable order is the main use case of LinkedHashMap– Anthony AcciolyCommented Apr 15, 2014 at 3:49
-
1See this question: [Previously on SO][1] [1]: stackoverflow.com/questions/730620/how-does-a-hash-table-work– Jarrod CabalzarCommented Apr 15, 2014 at 3:50
-
Because order of insertion has nothing to do with hashing.– Brian RoachCommented Apr 15, 2014 at 4:03
2 Answers
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.