4
$\begingroup$

I have a set of $n$ values,$v_i$ and want to insert them into a hash-table, $HT$, in a way that each bucket (or hash-table cell) has at most $d$ values. I set $k=\frac{n }{d}$, where $k$ is the number of buckets. Then, I use SHA hash function, $H$, to find the index a bucket in the hash-table and insert the values into the bucket:

$HT [H(v) \bmod k]=v_i$

The problem is that the indices do not look uniformly at random, for instance 3 different values may map into a cell whereas an index may not appear at all. And this can lead overflow.

Notice that I need a deterministic way as two different parties encode their values using hash table. Therefore, if the parties use the identical parameters for hash table, the same values should be in the same bucket (of different hash tables). Obviously different party may have different set values.

Question: What is the best way of preventing overflow in the above scenario?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ The fact that $H(\cdot)\bmod{k}$ over all the inputs does not yield exactly each index the same number of times is not surprising at all. If fact, it would be surprising if it yielded exactly each index the same number of times no matter what inputs you gave it. $\endgroup$
    – mikeazo
    Oct 19, 2015 at 19:42
  • $\begingroup$ If $k$ is not a power-of-2, the bias will be even more pronounced. Since you say you are getting overflow, is each hash-table cell a fixed-size array? Why not have each be a linked list? $\endgroup$
    – mikeazo
    Oct 19, 2015 at 19:42
  • $\begingroup$ @mikeazo Can I ask you why it matters that $k$ be a power of 2. $\endgroup$
    – user153465
    Oct 19, 2015 at 19:44
  • $\begingroup$ Say my hash function outputs 3 bits (0-7) (and is just input mod 8) and I want numbers between 0 and 4 (so mod 5). Here are the input/output mappings [(0,0), (1,1), (2,2), (3,3), (4,4), (5,0), (6,1), (7,2), (8,0), (9,1), (10,2), (11,3), (12,4), (13,0)...]. Notice that 0,1,2 happen more frequently than 3 and 4. $\endgroup$
    – mikeazo
    Oct 19, 2015 at 19:50
  • 1
    $\begingroup$ I can't understand what the question is. "What is the best way..." - best by what metric? "best" is subjective. What exactly are the requirements? Or what is the performance metric you are trying to optimize? What approaches have you considered and rejected, and why? Of course you cannot prevent overflow -- there will always be a possibility of overflow -- so what are you really trying to achieve? I encourage you edit the question to clarify. Overall the question seems unclear to me -- community votes? $\endgroup$
    – D.W. ♦
    Oct 19, 2015 at 20:53

1 Answer 1

Reset to default
7
$\begingroup$

SHA1 or SHA256, whichever you use, is for any practical purpose a random function. What you are observing is that random allocation is not as good as deterministic allocation. If you knew all the values in advance then you could indeed arrange that each cell would get exactly the same number of hits. Unfortunately, when you throw $n$ balls into $k$ bins, the number of balls landing into each bin isn't $n/k$ but rather has roughly Poisson distribution with mean $n/k$ (assuming $n/k$ is "small"). Thus you expect there to be a few bins which do get quite a few balls more than their share, and vice versa. A good hash table should be able to handle that – there are several approaches that you are probably aware of.

A similar situation happens when you throw $n$ balls into two bins. Rather than each bin getting exactly $n/2$ balls, the number of balls in each bin has roughly normal distribution with mean $n/2$ and standard deviation $\sqrt{n}/2$. Thus you expect one bin to contain roughly $\sqrt{n}$ more balls than the other.

Another similar situation concerns throwing $n$ balls into $n$ bins. Rather than an even allocation, you expect the maximum cell to contain roughly $\log n/\log\log n$ balls. However, if any given ball is given two options, and you put it in the lighter bin, then the maximum cell contains only roughly $\log\log n$ balls in expectation. This is one way of coping with your problem.

Improve this answer
$\endgroup$
5
  • $\begingroup$ This answer is is exactly right. The expected distribution of chain lengths is given by the Poisson distribution, and what you're seeing is what you'd expect. If this isn't good enough, then one hash function is not enough. You may want to look into techniques which use multiple hash functions, such as cuckoo hashing. Note that in your scenario, you probably don't actually need to use more than one hash function, because there is plenty of hash material that you haven't used ($H(v) / k$). $\endgroup$
    – Pseudonym ♦
    Oct 19, 2015 at 23:32
  • $\begingroup$ @Yuval Filmus first off thank you for the answer. For two bin case, you said "Thus you expect one bin to contain roughly....". I'm wondering if there is any way to estimate how many more balls a bin may get when the number of bins are $k$? $\endgroup$
    – user153465
    Oct 20, 2015 at 9:03
  • $\begingroup$ @Pseudonym I think I "cannot " use cuckoo hashing because for two parties each having a set, if they individually construct their own hash table, a value in common in both sets may not reside in the same index of the hash table. $\endgroup$
    – user153465
    Oct 20, 2015 at 9:09
  • $\begingroup$ @user153465 It is definitely possible, though the exact answer depends on the relative sizes of $n$ and $k$. As a first approximation, the maximal occupancy is the solution $m$ to $\sum_{r \geq m} e^{-\lambda} \frac{\lambda^r}{r!} = \frac{1}{n}$, where $\lambda = n/k$. $\endgroup$
    – Yuval Filmus
    Oct 20, 2015 at 9:10
  • $\begingroup$ I'm still struggling with computing an upper bond on the number of elements in a bucket. In page 7 link below it is said if we throw n balls into k binds then with a high probability each bin contains at most $\frac{n}{k}+O(\sqrt[2]{\frac{n}{k}}+log k)$. What I do not understand is what O() is supposed to do here. $\endgroup$
    – user153465
    Nov 3, 2015 at 14:17

Your Answer

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

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