6
$\begingroup$

One way to deal with the problem of collisions for a hash table is to have a linked list for each bucket. But then the lookup time is no longer constant. Why not use a hash set instead of a linked list? The lookup time would then be constant. For example, in C++ the hash table could be defined as:

unordered_map<int, unordered_set<int>> m;
$\endgroup$
8
$\begingroup$

An hash set is an hash table. Using an hash set to handle collisions in an hash table is equivalent to using a bigger hash table, with an hashing function which is a combination of the hashing functions of both level.

In other words, you'd probably be better with a bigger initial table (for instance there is no risk of resonance between the two hash functions which could lead to an higher collision rate than expected at the second level).

$\endgroup$
  • $\begingroup$ Wouldn't it be more complicated to use a bigger hash table? Using an inner hash set might be equivalent, but I can do it using only one line of code in C++ $\endgroup$ – programmer Dec 29 '15 at 15:56
  • 1
    $\begingroup$ I've abstained to comment on the C++ code you showed, it probably does not do what you think it does: std::unordered_{map,set} are hash tables, with collision resolution built in, and they resize the table automatically. You can set up the initial size (or bucket count) in the constructor, and at any time with the rehash member. $\endgroup$ – AProgrammer Dec 29 '15 at 16:36
  • $\begingroup$ Many thanks. Where can you learn more about std::unordered_{map,set}? I don't actually know how they're implemented. Is there a source code for them? $\endgroup$ – programmer Dec 30 '15 at 12:44
  • $\begingroup$ @programmer, In order of increasing complexity: there are sites like cppreference and books which gives user level reference, there is the standard which has drafts available on the web (search for "iso sc22 wg21" and "CD" or "Committee Draft"), there are at least two implementations available as well (gnu's libstdc++ and llvm's libc++) but looking at these could be more confusing than helpful. $\endgroup$ – AProgrammer Dec 30 '15 at 13:35
7
$\begingroup$

But then the lookup time is no longer constant

Not worst-case constant -- which it never is for (basic) hashtables -- but it is still average-case constant, provided the usual assumptions on input distribution and hashing function.

Why not use a hash set instead of a linked list?

And how do you implement that one? You have created a circular definition.

The lookup time would then be constant.

Nope, see above.

Your major confusion seems to be about what people mean when they say that hashtables have constant lookup time. Read here on how this is true and false.

$\endgroup$
  • 1
    $\begingroup$ @programmer Yes, but that's an unlikely event. Anyway, unqualified statements about running time in CS always mean worst-case performance. Hence, the statement "hashtables have [WC] constant lookup" is wrong. Both "hashtables have AC constant lookup" and "hashtables have BC constant lookup" are true, though. I recommend you study some basics of algorithm analysis. $\endgroup$ – Raphael Dec 29 '15 at 12:14
  • 1
    $\begingroup$ In your C++ code, just use a HashSet implementation. From a CS perspective, that approach does not make sense for the reasons I state in my answer. $\endgroup$ – Raphael Dec 29 '15 at 12:19
  • 1
    $\begingroup$ It works in a programming context, sure. It may even outperform an implementation with linear lists (I doubt it). We are on a site about computer science, though, and then the answer is: you don't get to implement A using A. If you can't follow that, I'm not sure this is the right site for you (yet). $\endgroup$ – Raphael Dec 29 '15 at 12:24
  • 4
    $\begingroup$ On the other hand, I have seen implementations that use some sort of balanced binary tree (AVL, red-black, etc.) instead of a linked list to handle collisions. This brings the worst-case down to O(log n) rather than O(n), though it does considerably increase the complexity, and is most likely to be only marginally beneficial unless you have a LOT of collisions - a situation which can be more easily avoided simply by using a larger hash table and/or a better hash function. $\endgroup$ – Darrel Hoffman Dec 29 '15 at 15:33
  • 1
    $\begingroup$ The tree-based approach has the benefit that it's resistant DoS attacks in which an attacker intentionally creates a lot of collisions, in the hope of turning an O(1) map into O(n) -- and thus a loop that's expected to take O(n) into O(n^2). For instance, a web server that throws query string params (?a=1&b=2&...) into a map can be attacked by creating a long query where all the parameters hash the same way, if you know the hashing algorithm. There are a few ways to defend against this; one is to have collisions resolve in a balanced tree (this is what Java 8 does, for instance). $\endgroup$ – yshavit Dec 30 '15 at 4:56
5
$\begingroup$

You absolutely can do this. You just have to be careful with how you set things up.

There's a type of hash table called a dynamic perfect hash table that, with some modifications, is essentially what you're describing. It works by having a two-layer hash structure, where collisions in the top level are resolved by building a hash table for the second level that is guaranteed to have no collisions.

In order to get this to work, you need to have access not just to a single hash function, but to a family of different hash functions. There's two reasons for this: first, you need to ensure that if you get a collision in the top-level hash table, you don't then get the same collisions in the second-level hash table. Second, the second-level hash table needs to not have any collisions in it (after all, we're trying to resolve collisions via a second round of hashing!), so the hash table works by choosing new hash functions until it finds one with no collision.

This system gives guaranteed O(1) lookups - you need to do at most two hashes - with expected O(1)-time insertions and deletions.

In practice, this isn't used much because you need to have a family of hash functions available and in most programming languages objects just have a single hash function available to them.

$\endgroup$
3
$\begingroup$

It would be pointless to use a HashSet. If a number of objects land in the same bucket it is because they hash to the same value (mod nBuckets but likely the same actual value). What hash value would you use for the inner hash-set? You are in danger of forcing the inner HashSet to also collide.

$\endgroup$
  • 1
    $\begingroup$ Conceptually, it's easy to use a different hashing function. Such variants actually exist. The implementation the OP proposes is naive, of course, and does not ensure this. $\endgroup$ – Raphael Dec 29 '15 at 14:23
  • $\begingroup$ I don't actually understand how the inner hash set is implemented in memory. I just found that the code works (maybe not very well, but it does work), and I am trying to understand why. $\endgroup$ – programmer Dec 29 '15 at 15:53
1
$\begingroup$

There are hierarchical hash maps as you describe. However, there are some caveats.

First is that a hash map is only guaranteed constant time if you can limit the cost of a collision to constant time. If there are no collisions, then using a linked-list as the next layer never comes up, because you never need to deal with collisions at all. If you want to use a hash map for collision resolution rather than a linked list, we have to consider the case where there are collisions, so we have to either find a way to control the collisions in this new map, or accept worse runtime bounds.

Linked lists are fast and easy to manipulate and traverse. They require no spatial locality, so it is easy to pool the spare nodes for many linked lists and draw from that pool as needed. Compare that to resolving collisions with hash maps which require contiguous blocks of memory to be sized and managed. It'd be virtually impossible to manage these collision resolution maps without writing a malloc like function, which is one of the more expensive operations you can put into a high-speed structure like hash mapping!

Also, what are you hashing with anyway? If there is too much of a relationship between the hashing and binning procedures for the outer hash map and the inner hash map, collisions that cause us to need a collision resolution procedure are likely to collide again in the second layer, or the third layer. You may find that what looks optimal actually becomes very suboptimal in realistic situations.

In all, it tends to be easier and faster to maintain data using a linked list or a probing technique, monitor the depth of the lists, and perhaps re-hash if they get too non-ideal. The savings in memory management complexity far outweigh the behavior of using hash maps for collision resolution.

$\endgroup$
  • $\begingroup$ "hash map is only guaranteed constant time if there are no collisions" - False. There are certain conditions under which a hash table is guaranteed constant time. That's not a necessary condition. $\endgroup$ – D.W. Dec 30 '15 at 0:41
  • $\begingroup$ @D.W. How can that be improved? Is there perhaps a more general statement about collisions that can be made? $\endgroup$ – Cort Ammon Dec 30 '15 at 4:45
  • $\begingroup$ I think it can be best improved by removing the sentence from your answer and then seeing what parts of the answer you can still justify (maybe all of the rest remains fine?). There are more general statements about conditions under which a hash map is constant-time: e.g., if you use a 2-universal hash function, then the average-case running time is constant, because the expected number of collisions with any particular item is constant (beware though that the total number of collisions is linear), but I don't see how that'd be relevant/useful to your answer. $\endgroup$ – D.W. Dec 30 '15 at 6:27
  • $\begingroup$ "limit the cost of a collision to constant time" - I feel bad for repeatedly critiquing your answer, but.... that sentence doesn't make any sense to me. I'm not entirely sure what the "cost of a collision" would mean precisely, but under one natural interpretation, the statement is not correct (if you mean how much each collision encountered increases the running time, then the statement is false: every hash table satisfies the condition, but does not have guaranteed constant time lookups). $\endgroup$ – D.W. Dec 30 '15 at 6:38
  • $\begingroup$ @D.W. I'm thinking of the amount of execution time required to look up a key which collides with other keys in the hash map which depends on the number of collisions with that particular key and the particular way the map deals with collisions. $\endgroup$ – Cort Ammon Dec 30 '15 at 6:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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