2
$\begingroup$

I want to split my data into $n$ approximately equal parts. Which simple hash functions will ensure that the number of $x$ with $h(x)\equiv i\pmod{n}$ is approximately equal for each $i$?

$\endgroup$
8
  • $\begingroup$ Every decent hash function will do. $\endgroup$ Apr 18 '16 at 10:23
  • $\begingroup$ What kind of data? Why do you want/need to use hashing? Are you aware that hashing usually deterministic, that is has nothing to do with pseudo-randomness? $\endgroup$
    – Raphael
    Apr 18 '16 at 10:24
  • $\begingroup$ @YuvalFilmus The distribution of the data factors in here. $\endgroup$
    – Raphael
    Apr 18 '16 at 10:24
  • $\begingroup$ @Raphael Presumably all data points are distinct. A $k$-wise independent hash, for large enough $k$, should suffice (assuming you're allowed to choose the hash function randomly). $\endgroup$ Apr 18 '16 at 10:25
  • 2
    $\begingroup$ @Raphael No, in the model in which you choose the hash function randomly from a $k$-wise independent family, the input distribution doesn't come into play, as long as you're only worried about distinct inputs. $\endgroup$ Apr 18 '16 at 10:27
2
$\begingroup$

I do not think there is such a hash function unless the number of input points is much larger than $n$, or much smaller than $n$, or your hash function is constructed based on your data.

If your input data has the same size as the number of buckets, then with high probability, one of your buckets will have $0$ elements in it and one will have $\Theta(\log n/\log \log n)$.

According to "Balls into Bins - A Simple and Tight Analysis", something similar happens even when the number of items is as small as $n/\log^c n$, for any $c$.

If you see all of your data ahead of time, you can pick a hash function $g$, use it to make a open-addressed hash table, then let $h(x)$ be defined as the location of $x$ in the hash table you made with $g$, but storing this hash table requires $\Theta(n)$ space and it does not work to hash values that it hasn't seen before.

$\endgroup$
2
$\begingroup$

Assuming the number of data points is much larger than the number of buckets:

The theory answer: any universal hash function will suffice to ensure that the parts are roughly similar in size (on average, in expectation, over the random choice of hash function).

The pragmatic answer: any hash function that provides roughly equidistributed outputs is likely to suffice. Thus, any hash function that doesn't suck will normally be fine in most cases (e.g., as long as the inputs aren't adversarially chosen and as long as the hash function doesn't have serious problems).

$\endgroup$
5
  • $\begingroup$ I don't think this is correct: "approximately equal for each i" to me means that there can't be one very heavy bucket, which we know there will be with high probability when the number of input values is the same as the number of buckets, even with a very good hash function. $\endgroup$
    – jbapple
    Apr 19 '16 at 1:41
  • $\begingroup$ @jbapple, yes, that's right, my answer assumes the number of data points is much larger than the number of buckets. I've edited it to make that assumption explicit. I personally doubt that the question would even come up if that isn't the case... but since the question doesn't specify, it's good to be explicit. Thanks for highlighting that! $\endgroup$
    – D.W.
    Apr 19 '16 at 4:46
  • $\begingroup$ How large is much larger? The only bound I know is a lower one: there are some inputs and some universal families for which putting $n$ items in $n$ buckets by picking a member of the family at random still produces a bucket with $\Theta(1)$ probability, so the number of items must be $\Omega(n \sqrt{n})$. Is that many sufficient? $\endgroup$
    – jbapple
    Apr 19 '16 at 14:16
  • $\begingroup$ @jbapple, good question! I don't know. Maybe a good question to ask separately? I'm inclined to guess that with $m$ buckets, $n=\Omega(m \log^2 m)$ should suffice to ensure that no bucket has more than a constant times the expected value, since there's a $\Omega(\lg m)$ gap between the mean and std dev (of items in a single bucket). I'm not sure what you meant about universal families: if the function is 1-universal, then the expectation (of the number of items in a given bucket) is the same as for a truly random function; if it is 2-universal, then the expectation and variance are the same. $\endgroup$
    – D.W.
    Apr 19 '16 at 16:39
  • $\begingroup$ "Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence", by Mathias Bæk Tejs Knudsen and Morten Stöckel shows "a $k$-independent family of functions that imply [heaviest loaded bin] size $\Omega(n^{1/k})$". They also cite Alon et alia's "Is Linear Hashing Good?" from STOC '97. $\endgroup$
    – jbapple
    Apr 20 '16 at 0:43

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.