7

I've been trying to find some concrete (laymen; non super-academic) definitions for the various types of hash data structures, specifically hash tables, hash lists and hash maps. Online searches provide many useful links to all of these, but never give clear definitions of when it is appropriate to use each over the others.

(1) From a practical standpoint, what's the difference between these 3?

(2) How do their operations' run times differ? Are there clear instances when one should be used or avoided over the other types of hashes?

(3) How do each of these relate back to the Map ADT? Are they all just different implementations of it, or different beasts altogether?

Thanks for any insight here!

IAmYourFaja
  • 55,468
  • 181
  • 466
  • 756
  • 1
    Given what's available on Wikipedia, I'm not sure why this is being voted up - it fails the "shows research effort" test. – Ed Staub Sep 19 '11 at 17:24
  • Because its a good question that contributes to the well-roundedness of the SO community, Ed Staub! – IAmYourFaja Sep 19 '11 at 17:37
  • Complementing the answer of Oka from a Java point of view: http://stackoverflow.com/questions/40471/java-hashmap-vs-hashtable –  Sep 19 '11 at 17:39
  • 1
    Given that a Google search on these terms would immediately reach relevant information of equal or better comprehensibility, I don't see the point of trying to make SO content be more "well-rounded" in this sense. I'd much rather see SO focus on "going where they ain't" - info that's either not elsewhere or not easily searchable elsewhere or otherwise just harder to use elsewhere. When you start putting up content purely to steer hits here - to be "well-rounded", it's starting down a slippery slope toward content farming. (I'm assuming you're the SE employee Mara - yes?) – Ed Staub Sep 19 '11 at 17:53
  • That hurts my feelings Ed Staub. Now my migraines are starting to come back. And the voices.....the voices. – IAmYourFaja Sep 19 '11 at 18:09
  • I've no idea whether you're serious or not. If so, look - I'm just asking you to apply the same filter to what you put up that you'd expect any user to. If it's really trivial - a top-of-the-page Google hit, in this case - to find the answer elsewhere, don't. – Ed Staub Sep 19 '11 at 18:16
  • Not serious, I guess ;-) – Ed Staub Sep 19 '11 at 18:22

1 Answers1

2

There's an abstract data structure that contains mapping between keys and values. It has several different names, including Map, Dictionary, Table, Association Table, and more.

The most basic operations that should be supported by this data-structure are adding, removing and retrieving a value, given its associated key. There are variations and additions around this basic concept - for instance, some structures support iterating over all the key-value pairs, some structures support multiple values per key, etc. There's also a difference in time and space complexity between the various implementations.

Of the multiple implementations available for this data structure, some of the most popular ones utilize hash functions for fast access times. Those implementations are sometimes called by the name Hash Table or Hash Map, you can read more about them in Wikipedia. The performance also varies between hash table implementations, with some reaching amortized O(1) insertion and access complexity (for the price of a lot of space used).

A hash list, on the other hand, is a different thing, and is more about the usage of a data structure, than its actual structures. A hash list is usually just a regular list of hash values, nothing special about it. It's used when verifying the integrity of a large piece of data - in that case it allows various data chunks to be verified independently, allowing for fixing or retrieving of just the bad chunks. This is as opposed to using a single hash value to hash the entire piece of data, in which case a failure means all the data has to be fixed or retrieved again.

Oak
  • 26,231
  • 8
  • 93
  • 152