People who code: we want your input. Take the Survey
3

Cryptographic hashes I don't think anything is known unconditionally. We can analyze this question using a random oracle assumption. MD5, SHA1, SHA256, etc., have a Merkle-Damgaard structure: they split the input $x$ up into blocks $x_1,\dots,x_n$, then compute $$h_i = F(x_i,h_{i-1})$$ where $h_0$ is a constant and $h_n$ is used as the output of the hash ...


2

I believe the best known bound is in Woelfel's "Efficient strongly universal and optimally universal hashing", Theorem 5, which presents a set with $M = N + \lfloor (N - P)/2 \rfloor - 1$, where $P$ is the number of bits in the codomain.


2

Let $m = 1 + \log \ell$. Identify a hash function $h \colon \{0, 1\}^k \to \{0, 1\}^m$ with its $n$-bit truth table $h \in \{0, 1\}^n$ where $n = m \cdot 2^k$. Our hash family $\mathcal{H} \subseteq \{0, 1\}^n$ consists of an $\varepsilon$-biased set for a suitable $\varepsilon = \ell^{-\Theta(k)}$. Explicit constructions of such a hash family are known with ...


1

Today you should probably use Tabulation hashing for Linear Probing. In The Power of Simple Tabulation Hashing by Mihai Pătrașcu and Mikkel Thorup, this is shown to have at least the same guarantees as 5 independent hashing. Later work shows that it gives you better concentration (worst case bounds) as well. Tabulation hashing is also a lot faster than even ...


Only top voted, non community-wiki answers of a minimum length are eligible