Say I have a family of hash functions that are weakly universal, i.e. the probability of two non-identical keys $xneq 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_hleft[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/mleq 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?