Must a hash table be implemented using an array? Will an alternative data structure achieve the same efficiency? If yes, why? If no, what condition must the data structure satisfy to ensure the same efficiency as provided by arrays?
1 Answer
Must a hash table be implemented using an array?
No. You could implement the HashTable interface with other datastructures besided the arrray. E.g. a Red-Black tree (java's TreeMap).
This offers O(logN) access time.
But Hash Table is expected to have O(1) access time (at best case - no collisions).
This can be achieved only via an array which offers the possibility of random access in constant time.
what condition must the data structure satisfy to ensure the same efficiency as provided by arrays?
Must have a comparable performance (less than O(N)) with an array. A treemap has O(logN) worst access time for all operations
3 Comments
I'd argue that a hash table is a quite different beast from a comparision-based mapping. These differences are not just in theory and under the hood, they pertain to the requirements on the keys: A hash table requires a hash function and equality, while the other requires a total order.
Cratylus
@delnan:It depends on how you interpret the OP.My point of view is that a
HashTable is an implementation/extention of a Dictionary data structure. It provides the interface of a Dictionary. The abstract data structure can have various implementations e.g. a HashTable backed by an array or a TreeMap backed by a tree.If taken a definition as strict as you propose then yes, a HashTable which implies a hash function can only be backed by an array
psyko666
thank you for answering, and sorry for the late reply, i always forget to check back on stackoverflow, thank you again