2
$\begingroup$

While there are many types of probing in hash tables, such as linear probing, quadratic probing, and more, I haven't encountered a so-called "hash-probing" (maybe this method which I describe below exits and I just don't know its name, and if that is the case I would love some references).

This is the concept:

When generating a hash table of size $m$, generate an assisting array of size $m$, for which every index will be given a different hash function from a universal (or almost universal) hash family.

When inserting/deleting an item from the hash table, we use probing, for which if the first index in the hash table is taken, calculate the second index to be checked using the second hash function from the array, and so on...

Each calculation will be $O(1)$ (by itself).

Now - the goal is to avoid problems such as clustering that occurs in linear probing which can cause the time complexity to increase when the load factor rises.

I'm pretty sure this method I suggested now is flawed, since I haven't encountered this method anywhere, but I couldn't formally point to the flaws of the method.

One idea I've come up with is that by using different hash functions we cannot guarantee that the second (nor the third, etc..) hash function for a given item $x$ will not result in the same value (i.e the same index in the hash table), but I'm not sure about this since for big hash tables (and therefore many hash functions), cannot we expect a low amount of collisions (for the same item by different functions)?

Would love some comments on the method and my last analysis (and/or references). Thanks.


EDIT:

Well, I've went on to try to implement it in order to make some tests on efficiency, but then I've noticed two extremely major flaws in this method:

  1. Unsuccessful search will always be $O(m)$, since you need to go all over the hahs function in the hash-array.

  2. Deletion - when we delete an item from the table, we can't "correct" the table, unless we rehash it, which will be $O(m)$ as well.

I don't think this method works, because of this two flaws, but if someone has an idea on how to avoid those (and not changing the method much, or suggesting cuckoo hashing) it will be interesting to read.

Thanks.

$\endgroup$
  • 1
    $\begingroup$ For a somewhat related approach, lookup Double Hashing. $\endgroup$ – Omar Jul 28 '17 at 8:27
  • $\begingroup$ You have discovered en.wikipedia.org/wiki/Cuckoo_hashing $\endgroup$ – adrianN Jul 28 '17 at 9:20
  • $\begingroup$ @adrianN Elaborate into an answer? $\endgroup$ – Yuval Filmus Jul 28 '17 at 9:42
  • $\begingroup$ This platform is ill-suited for reviews. Please ask a crisp question, and preferably updated the title with it. It's currently rather ... unhelpful. $\endgroup$ – Raphael Aug 1 '17 at 9:47
3
$\begingroup$

Your scheme is very similar to Cuckoo Hashing. In Cuckoo Hashing you have two (or, in variations, more) independent hash functions $h,g$. To insert an item $x$ you check at location $h(x)$. If that location is occupied, you suggest to check at $g(x)$. If we were to do it that way, we would have a problem in case $g(x)$ is also occupied and would have to fall back to another scheme, e.g. linear probing, with the associated problems. In Cuckoo hashing we employ a trick. If $h(x)$ is occupied by some item $y$, we store $x$ at that location anyway and try to store $y$ its alternate location (so either $g(y)$ or $h(y)$). If those locations are occupied as well, we repeat the process of kicking out the existing item and trying to place it at its alternate location.

You might wonder whether this process doesn't lead to loops and how long insertion can take. After all the sequence of kicking out and trying alternate spots doesn't seem to have a defined bound.

And indeed, if your hashtable is too full, the insertion can fail.

Consider the graph in which table positions are vertices and there is an edge between two vertices when we need to insert an item that maps to them. Usually this graph is called the cuckoo graph. We seek a matching of edges to vertices. By Hall’s theorem it exists if and only if there is no subgraph that has more edges than vertices.

We can use the first moment method to find a bound for the appearance of such subgraphs. Hence we have to calculate their expected number. There are many graphs with more edges than vertices, too many to tackle the expectation with our limited knowledge of probability theory. Luckily we can make a clever observation. If there are no subgraphs with more edges than vertices, there can’t be subgraphs with exactly one more edge than vertices.

There are only two types of these graphs, see the figure below. Both can be characterized by three numbers. Either the length of the three paths, or the size of the two cycles and the length of the connecting path. As all of these numbers must be smaller than $n$, there can be at most a cubic number of forbidden subgraphs. If we simplify the problem a little (actually we would have to use a random graph model where we fix the number of edges to the number items. For our purposes these two models are similar enough.) and consider the graph to be a $G_{n,p}$, a random graph on $n$ vertices where every edge is present with probability $p$, a fixed subgraph with $k$ edges is contained with probability $p^{-k}$. Hence the probability that a fixed forbidden graph appears is certainly smaller than $p^{-3}$.

These subgraphs are too dense

As we have at most $n^3$ forbidden subgraphs, the expected number is at most $n^3p^{-3}$. This value goes to zero for $p < 1/n$ and thus (modulo our simplified graph model) for graphs with less than $n/2$ edges. Therefore in such graphs no forbidden subgraphs occur with high probability and insertion can work in principle.

But how about our greedy algorithm, is it sufficient for inserting new elements? Let’s consider a directed version of the cuckoo graph. Every edge is directed towards the position where the element is moved to in case it gets kicked out of its current spot. Hence elements reside at the edges tails and every node has at most one outgoing edge. Inserting a new element corresponds to inserting a new edge and directing it. If both endpoints already have an outgoing edge, we select an arbitrary one and kick the element out of its position. This means we reverse the edge and check at the new position whether there is already an outgoing edge.

This process fails if we cross an edge for the third time. The first time we see it, we flip it and continue. If we see it again, there was a directed cycle somewhere further down the path, that made us return. Note that this cycle still exists, only it now has the opposite direction. If we see the edge a third time, there was also a directed cycle on the other side–the process loops forever between these cycles.

A directed cuckoo graph

But we’ve shown that these types of subgraphs don’t appear with high probability for hash tables with an occupancy of less than 0.5. So if you keep the occupancy low, insertion is very likely to succeed.

If you use more hash-functions the maximum occupancy goes up very quickly (see for example https://arxiv.org/pdf/0910.5147.pdf)

Using similar reasoning over the random graph model I described above you can show that insertion takes constant time in expectation.

$\endgroup$
  • $\begingroup$ Thanks for the detailed and elaborate answer! Actually, I'm familiar with the basics of cuckoo hashing (but not to the extent to the connection to graphs you pointed here), and the algorithm I proposed here is a bit different then the cuckoo-hashing method for the case that we don't kick out occupied indexes, but instead apply the next hash function in the "hash-function-array", similarly to linear probing. (for example - if an item is entered to the hash table, it will stay in the same spot until it is deleted or we rehash the table). Does the analysis still hold for the method I described? $\endgroup$ – Mickey Jul 28 '17 at 10:51

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.