Solved

implement hash table using only arrays (in JAVA)

Posted on 2014-02-06
4
1,792 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 26

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 26

Accepted Solution

by:
dpearson earned 500 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

Master Your Team's Linux and Cloud Stack!

The average business loses $13.5M per year to ineffective training (per 1,000 employees). Keep ahead of the competition and combine in-person quality with online cost and flexibility by training with Linux Academy.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
HSSFWorkbook cannot be resolved error 10 70
configure dependency in POM for new database 3 25
hibernate jars 4 30
Running JavaFX on JDeveloper 12C 1 32
The Fluent Interface Design Pattern You can use the Fluent Interface (http://en.wikipedia.org/wiki/Fluent_interface) design pattern to make your PHP code easier to read and maintain.  "Fluent Interface" is an object-oriented design pattern that r…
Introduction A frequently used term in Object-Oriented design is "SOLID" which is a mnemonic acronym that covers five principles of OO design.  These principles do not stand alone; there is interplay among them.  And they are not laws, merely princ…
Viewers learn about the “for” loop and how it works in Java. By comparing it to the while loop learned before, viewers can make the transition easily. You will learn about the formatting of the for loop as we write a program that prints even numbers…
Viewers will learn about the regular for loop in Java and how to use it. Definition: Break the for loop down into 3 parts: Syntax when using for loops: Example using a for loop:

777 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