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?
-
What do you mean "for everything?" Hashing cannot be applied to every data structure.– user2134086Commented Nov 24, 2013 at 2:06
-
1We 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 LicksCommented 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 LicksCommented Nov 24, 2013 at 2:08
-
@Jeremy Bentham "For everything" means using hashing/hash tables to solve all problems.– DonaldCommented Nov 24, 2013 at 2:10
-
Are there any problems associated with hashing that limits its applications?– DonaldCommented Nov 24, 2013 at 2:12
6 Answers
Hash tables, on average, do have excellent time complexity for insertion, retrieval, and deletion. BUT:
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.
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.)
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.
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.
-
1If 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.– xskxzrCommented Aug 19, 2021 at 5:54
-
@xskxzr That's a good point. Feel free to edit it into my answer if you wish.– Alex DCommented Aug 19, 2021 at 8:50
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.
HashTable
is not answer for all. If your hash function does not distribute your key well thanhashMap
may turn into alinkedList
in worst case for which the insertion, deletion, search will takeO(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 youHashMap
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 byBtree
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.
- Hash Tables are not sorted (map)
- Hash Tables are not best for head/tail insert (link list/deque)
- Hash Tables have overhead to support searching (vector/array)
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.
-
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 GCommented Dec 8, 2023 at 12:22
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’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