Bounds on probe lengths and number of rehashes with universal hashing

Question

Say I have a family of hash functions that are weakly universal, i.e. the probability of two non-identical keys $x\neq y$ are mapped to the same hash-value is bounded by $k/m$ when I have $m$ bins and $k$ is some constant (I am mainly interested in $k=1$ and $k=2$):

$$\Pr_h\left[h(x)=h(y)\right] \leq \frac{k}{m} $$

I have $n$ keys mapped to $m$ bin and I keep a constant bound on the load factor $n/m\leq \alpha$.

With this setup, I am interested in putting a bound on how many collisions I allow in any bin, $K$, and rehashing whenever I have to insert a key in a bin that already holds $K$ elements. For a given bound on the load factor, $\alpha$, and a given bound on the maximum elements in any bin, $K$, I am interested in knowing the probability of picking a hash function that puts less than $K$ elements in each bin.

This is a setup I am interested in for teaching purposes, and I am aware that there are smarter solutions to hash tables, but I would like to handle this setup before moving on to them. In my lecture notes, I have already described rehashing and just want to take this to a probabilistic analysis place, so I want to know the expected number of rehashes needed in this setup.

I would actually also love to know if I could put a bound on the probe length in open addressing hashing and rehash when I reach that, but I guess this is a much harder question.

I guess that if I can fix the probability of hitting any given bin more than $K$ times at a constant $p$, I have a strategy for sampling my way out of the problem, where I expect to rehash $1/p$ times if the number of keys, $n$, and the number of bins, $m$, are fixed. But if I add keys one at a time, resize when $n/m>\alpha$, and rehash when I exceed the bound $K$ in any bin, do I have any guarantee that I will not have to rehash for every new element added after number $K+1$? I mean, my rehash could put $K$ elements in the largest bin and the next key could then trigger a rehash. An advisory, of course, cannot pick the keys so this happens, if I sample random functions, but do I have any probabilistic bounds that guarantee that I can rehash to keep probe-lengths bounded by a constant and still not rehash so often that I break the amortised constant running time on the table operations?

Answer 1

This does not seem like a good example for teaching purposes, as there's no clean analysis or useful conclusions you can draw.

In particular, from only the assumption that you have a weakly universal hash function, you can't draw any useful conclusions about the probability of a having less than K items in the bucket. That would require some notion of K-wise independence. Weak universality is a weakened form of 2-wise independence, and if $K>2$, it gives you no information about K-wise independence. In particular, the hash function could be arbitrarily bad, and the probability could be arbitrarily high. You need stronger assumptions about the hash function to do any useful analysis.

Instead of assuming weak universality, if you want to get a clean analysis, I suggest you assume that the hash function is (or behaves like) a random function, chosen uniformly at random from the set of all possible functions with that signature. Then the calculations get easy, since each output of the hash function is uniformly random and independent of all other outputs.