implement hash table using only arrays (in JAVA)
Posted on 2014-02-06
(This is a potential interview question and I'm not looking for code, just some ideas.)
The only way I've implemented a hash table is using an array of LinkedLists - the lists being buckets for handling collisions.
At the moment the only way I can think of to implement one using Chaining with only arrays would be to basically do the same thing but use arrays for buckets duplicating the arrays and doubling the array sizes as necessary. I don't know if this is stupid - probably, since I can't see any benefit to that over LinkedLists or even just ArrayLists.
Or, what about open-addressing: Linear Probing? Quadratic Probing?
What are the tradeoffs?
Are there other less know techniques?