Solved

implement hash table using only arrays (in JAVA)

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

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Introduction Many of the most common information processing tasks require sorting data sets.  For example, you may want to find the largest or smallest value in a collection.  Or you may want to order the data set in numeric or alphabetical order. …
Introduction This article explores the design of a cache system that can improve the performance of a web site or web application.  The assumption is that the web site has many more “read” operations than “write” operations (this is commonly the ca…
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…
Viewers will learn about arithmetic and Boolean expressions in Java and the logical operators used to create Boolean expressions. We will cover the symbols used for arithmetic expressions and define each logical operator and how to use them in Boole…

744 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

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now