2

I am wondering about the following question. To simulate an array via a hash table, one can simply set the keys of the hash table to be the indices of the array, and set the value of each key to be the value of the array at that index. In this way, it would seem that anything an array can do, a hash table can do, as well. This raises the question, is there any drawback, perhaps in terms of time or space complexity, to doing so? I'd love to hear your thoughts about this question.

  • 2
    You mean other than the fact that an array is simpler and you might not need the hashtable's lookup capabilities? That's all the cogitation you really need to make the right decision. – Robert Harvey May 8 '18 at 15:58
  • 1
    Enumerating the values in order of index comes to mind. – JeremyP May 8 '18 at 16:00
  • 6
    Yeah, the purpose of an array is to allow traversal in order. Your hash table has no concept of order, so you can't enumerate it, unless you plan on generating the keys incrementally. Further, you're asking it to do a key lookup for each iteration in your traversal loop, which is an unnecessary expense. In general it's a bad idea to use a knife blade as a screwdriver, or a wrench as a hammer. That's why carpenters carry around more than one tool. – Robert Harvey May 8 '18 at 16:03
  • 2
    wouldn't it be simpler to have one data structure instead of two? -- I already explained that. You have two data structures instead of one for the same reasons that a carpenter has both screwdrivers and hammers. – Robert Harvey May 8 '18 at 16:13
  • 3
    Ehm, well you do have to store all those hashes, don't you? Also, I declare your hypothetical metaphor invalid; your question is not about how sharp the knife is, but whether you need two knives. No self-respecting cook makes do with just a paring knife. – Robert Harvey May 8 '18 at 17:16
3

If there were no collisions, and we ignore the CPU cost of hashing the key, and we don't store any of the hash codes, the hashtable would consume the same amount of space.

However, in practice, we have collisions, so we need a system to deal with that, which requires more space. Most linked list collision handling hash tables use integer indices into arrays, instead of pointers, to reduce space and increase memory locality. You will need at least one more array then, for the pool of linked list structures. There are many collision handling algorithms, but they all require additional storage.

If the hashes are expensive to compute, and the keys do not store hashes themselves, you need extra memory to store hash codes.

Finally, you have to deal with poor distributions, and potentially poor hash functions, if you have no control over the hash functions. In .net hash functions tend to be particularly poor, and I imagine they are in Java as well, since the people writing the key structure typically have to write the hash function, and the internet abounds with poor advice in this area. Therefore you can look forward to poor distributions, which leads to large numbers of collisions, and additional space needed to reduce those collisions.

  • "If there were no collisions, and we ignore the CPU cost of hashing the key, and we don't store any of the hash codes, the hashtable would consume the same amount of space." - you'd also need to avoid empty buckets (i.e. the stored values have to be contiguously packed into the buckets), and hash tables usually store the key (for this scenario, the "logical" array index) which an array doesn't have to do - that would have to be avoided to keep memory consumption the same: i.e. the implementation would need to rely on having no collisions. – Tony Jun 30 '18 at 0:42
1

The first disadvantage is that you are storing more stuff in memory. Instead of just storing a bunch of objects, you're storing a bunch of objects and indices. This just wastes space, and may slow the program down (especially if the data gets too big for the processor cache).

The second disadvantage is that it makes it more complicated (and hence slower) to do the things that arrays are good at.

Iterating through arrays is trivial. You should already know the address of the first element. Finding the address of the next element just requires adding the size of one object to the address. That's just one "add" instruction.

Finding the nth element in an array is almost as trivial. Start with the address of the first element, and add (n times the size of one object). So one "multiply" and one "add".

  • Not quite. The instruction sets of most CPU's allow access of an array element in a faster manner than you describe. – Frank Hileman May 11 '18 at 16:40
-1

Some languages may require arrays to have a fixed size allocation while a hash may be unlimited, so a hash is more flexible there. Also, clearing a hash table may use much less CPU than resetting all elements in an array.

Not the answer you're looking for? Browse other questions tagged or ask your own question.