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 ??
Asked
Active
Viewed 1,866 times
-7
-
2Because it hashes instead. Hashing doesn't preserve ordering. – user207421 Apr 15 '14 at 03:47
-
2http://en.wikipedia.org/wiki/Hash_table – Anthony Accioly Apr 15 '14 at 03:47
-
BTW, iterating while predicable order is the main use case of [LinkedHashMap](http://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html) – Anthony Accioly Apr 15 '14 at 03:49
-
1See this question: [Previously on SO][1] [1]: http://stackoverflow.com/questions/730620/how-does-a-hash-table-work – Jarrod Cabalzar Apr 15 '14 at 03:50
-
Because order of insertion has nothing to do with hashing. – Brian Roach Apr 15 '14 at 04:03
-
You answered your own question. With an array the index is a number that increments with each insertion. The index can therefore maintain insertion order. As you (almost) said, the index of a hash table is the hash of its key and so unrelated to insertion order and perfect for quick lookup. – Adamantish Feb 20 '18 at 00:18
2 Answers
1
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.
Ilia Lebedev
- 355
- 3
- 7
