35

In computer science, it is said that the insert, delete and searching operations for hash tables have a complexity of O(1), which is the best. So, I was wondering, why do we need to use other data structures since hashing operations are so fast? Why can't we just simply use hashing/hash tables for everything?

7
  • What do you mean "for everything?" Hashing cannot be applied to every data structure.
    – user2134086
    Commented Nov 24, 2013 at 2:06
  • 1
    We do. It's known as cache. But if you want to go further there have been various proposals for "content addressable memory". (But hashing, in the general case, is not nearly as fast as you may think.)
    – Hot Licks
    Commented Nov 24, 2013 at 2:06
  • 2
    (Actually, hash tables have a complexity of O(log N), but the N is based on the maximum possible table size, vs it's current size.)
    – Hot Licks
    Commented Nov 24, 2013 at 2:08
  • @Jeremy Bentham "For everything" means using hashing/hash tables to solve all problems.
    – Donald
    Commented Nov 24, 2013 at 2:10
  • Are there any problems associated with hashing that limits its applications?
    – Donald
    Commented Nov 24, 2013 at 2:12

6 Answers 6

41

Hash tables, on average, do have excellent time complexity for insertion, retrieval, and deletion. BUT:

  1. Big-O complexity isn't everything. The constant factor is also very important. You could use hashtables in place of arrays, with the array indexes as hash keys. In either case, the time complexity of retrieving an item is O(1). But the constant factor is way higher for the hash table as opposed to the array.

  2. Memory consumption may be much higher. This is certainly true if you use hash tables to replace arrays. (Of course, if the array is sparse, then the hash table may take less memory.)

  3. There are some operations which are not efficiently supported by hash tables, such as iterating over all the elements whose keys are within a certain range, finding the element with the largest key or smallest key, and so on.

  4. The O(1) complexity is on average. For some extreme cases (for example, all data fall into the same bucket), it would be inefficient.

All of that aside, you do still have a good point. Hashtables have an extraordinarily broad range of suitable use cases. That's why they are the primary built-in data structure in some scripting languages, like Lua.

3
  • 1
    If you need things to be sorted, you will want to use a tree instead of a hash table. Commented May 8, 2015 at 7:39
  • ... and 4. The O(n) complexity is on average. For some extreme cases (for example, all data fall into the same bucket), its time complexity would be low.
    – xskxzr
    Commented Aug 19, 2021 at 5:54
  • @xskxzr That's a good point. Feel free to edit it into my answer if you wish.
    – Alex D
    Commented Aug 19, 2021 at 8:50
8

You may use Hash to search the element, but you cannot use it to do the things like find the largest number quickly, you should use the data strutcture for the specified problem. Hash cannot solve all the problem.

6
  • HashTable is not answer for all. If your hash function does not distribute your key well than hashMap may turn into a linkedList in worst case for which the insertion, deletion, search will take O(N) in worst case.

  • HashMap has significant memory footprint so there are some use cases where you memory is too precious than time complexity then you HashMap may not be the best choice.

  • HashMap is not an answer for range queries or prefix queries. So that is why most of the database vendor do implement indexing by Btree rather than only by hashing for range or prefix queries.

  • HashTable in general exhibit poor locality of reference that is, the data to be accessed is distributed seemingly at random in memory.

  • For certain string processing applications, such as spellchecking, hash tables may be less efficient than tries, finite automata, or Judy arrays. Also, if each key is represented by a small enough number of bits, then, instead of a hash table, one may use the key directly as the index into an array of values. Note that there are no collisions in this case.

2
  1. Hash Tables are not sorted (map)
  2. Hash Tables are not best for head/tail insert (link list/deque)
  3. Hash Tables have overhead to support searching (vector/array)
2

The potential security issues of hash tables on the web should also be pointed out. If someone knows the hash function, that person may perform a denial-of-service attack by creating lots of items with the same hashcode.

1
  • This is a non-issue and collisions cant be exploited if a random seed based hash function is employed, e.x. the Lua language
    – Jack G
    Commented Dec 8, 2023 at 12:22
-1

I don't get it, enum/symbol-keys not wasteful enough? ;) What about just using the raw string pointer as key? I must have overlooked some obvious advantage in hashing... but now thinking about it, it makes less and less sense.

It's all just local representation anyway, right? I mean, I could share the data everywhere... API's, IPC or RPC - but not sure how helpful those hashed keys are unless the full string is embedded too.

Meaning you just spent a lot of time hashing strings back and forth for your own amusement.

I'll just leave this here...

1
  • I’m not even joking, can you that voted me down tell me what I’m missing? If you share the hashmap to other libs or by external linkage then you would need to embed the full string anyway, so.. Why not use normal (or fat) pointers, hashing seems unneccecary (in most cases) Commented Feb 27, 2022 at 22:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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