Go Premium for a chance to win a PS4. Enter to Win

x
?
Solved

implement hash table using only arrays (in JAVA)

Posted on 2014-02-06
4
Medium Priority
?
1,936 Views
Last Modified: 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?

Thanks,
Kyle
0
Comment
Question by:Kyle Hamilton
  • 2
  • 2
4 Comments
 
LVL 28

Expert Comment

by:dpearson
ID: 39840760
If you're allowed to use an array of arrays, then yes it seems perfectly doable:

Use any hash function and mod to the length of the first array (analogous to the buckets in a regular hashmap).

Then add the item being hashed into the array stored in that bucket.  For a trivial implementation you just copy the old array into the new, larger array.  For a smarter implementation you need to track how much of the array is in use, append until it's full and then copy to a new array that's twice the size.

Searching is just: hash value to locate bucket and then search the list of values in that bucket to see if any match.

Removing is basically the same as adding - either copying the old array into the smaller array or packing the items down into an existing array.

The follow up in an interview would no doubt be to determine the computation complexity (big O notation) for these operations.  Also be ready to talk about the tradeoffs around the size of the initial array for storing the hashes.

You can also talk about the trade-off between allocating more space initially vs doing more copying for the arrays within the map.

Will there be even faster implementations for this?  Sure, they'll exist.  But if you bring those up in an interview, a smart interviewer will know that you've just prepped for the question ahead of time...and tend to ignore the answer :)

Hope that helps,

Doug
0
 
LVL 25

Author Comment

by:Kyle Hamilton
ID: 39840779
Thanks Doug,

It does help :)

Any thoughts on open-addressing?

K.
0
 
LVL 28

Accepted Solution

by:
dpearson earned 2000 total points
ID: 39840825
I'd never heard of open-addressing until you mentioned it.  The joys of living in a world where we no longer implement these low level data structures any more :)  If we were all still writing C++ I'd probably be up on it!

Reading up on it a bit it certainly seems relevant to this sort of implementation.  I can't really comment intelligently on the specifics as they're new to me, but if you're looking at this from an interview perspective I think the key would be whether you could explain the different algorithms and their pros and cons (since they seem to form a pretty clear spectrum).  There's never a "right" answer in this sort of situation, just A is better for situation X, B for Y.

If it was me doing the interview what I'd really want to hear is that you'd measure first and then try different approaches and re-measure (if you're down at this level of implementation detail and looking for the last few cycles of performance).  Since the performance will vary a lot with the specific data set and load factor in the hash table, it would be pretty hard to pre-select the correct algorithm.  Better to implement several and get to know your profiler more intimately.

Doug
0
 
LVL 25

Author Closing Comment

by:Kyle Hamilton
ID: 39840892
I guess no amount of theory is going to change the fact that it's "Better to implement several..."

Thank you :)
0

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used by…
Article by: evilrix
Looking for a way to avoid searching through large data sets for data that doesn't exist? A Bloom Filter might be what you need. This data structure is a probabilistic filter that allows you to avoid unnecessary searches when you know the data defin…
This tutorial covers a practical example of lazy loading technique and early loading technique in a Singleton Design Pattern.
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.
Suggested Courses

971 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question