hashing

Hashing

Computing the location of data instead of traversing a datastructure, without key comparisons.
With hashing, data is stored in an array-like structure called a hash table.
A hash function $h:K\to \{0,\dots ,N-1\}$ assigns a hash address (=index in the hash table) to each key $k\in K$, $0\le h(k)\le N-1$.
Since the number of possible keys is usually much larger than the number of hash addresses, multiple keys may map to the same address (a collision): $h$ is generally not injective.

$h$ often consists of two steps:
A hash code $c:K\to \mathbb{Z}$ maps each key to an integer, and
A compression function $d:\mathbb{Z}\to \{0,\dots ,N-1\}$ maps the integer to a valid hash address.

A good hash function is easy to calculate, distributes keys as evenly as possible over the hash addresses, and minimizes collisions.

$\alpha =n/N$ … load factor (stored items / hash table size)
$h(k)=h(k^{\prime })$ … $k,k^{\prime }$ are synonyms (collide)

Integer = 32-bit signed
For 64 bit long integers, a simple hash code function is:

int hashCode(long i) {
	return (int)((i >> 32) + (int)i);  // upper 32 + lower 32 bits
}

This works because the upper and lower bits of long integers are often not correlated.

For strings, a simple character sum would fail, things like “abc” and “cab” would collide.
Instead, we can treat characters as polynomial coefficients in some base $a$:

$$h_1(s)=\sum _{i=0}^{k-1}s[i]\cdot a^{k-1-i}$$

Or computed via horner’s method

$$h_1(s)=(((s[0]\cdot a+s[1])\cdot a+s[2])\cdots )\cdot a+s[k-1]$$

Horner’s method is more efficient, requiring only $k-1$ multiplications and $k$ additions.
With $a\in \{33,37,39,41\}$, there are only 6 collisions in the english dictionary (50k words).

To compress the hash code to a valid address, we can use the modulo operator:

$$h_2(h_1(s))=h_1(s)\mathrm{mod}N$$

Even $N$ are bad if the last bit encodes something (→ even/odd bias if there are many even/odd keys).
$N=2^p$ is even worse, as it only uses the lower $p$ bits of the hash code, losing information from the higher bits.
Empircally, the best choice for $N$ is a prime number.

Turan Sos Theorem

Let $\Psi$ be an irrational number. If you plance $n$ points

$$\{i\cdot \Psi \mathrm{mod}1\mid i=0,1,\dots ,n-1\}$$

in the interval $[0,1]$, the resulting $n+1$ intervals have at most three different lengths.
No matter how many points you place this way, you will never have more than 3 distinct gap sizes.

When you place the next point, it always lands inside one of the largest gaps, splitting it.

Of all numbers $0\le \Psi \le 1$, the most uniform distribution is achieved by choosing $\Psi =\frac{\sqrt{5}-1}{2}\approx 0.618$, the fractional part of the golden ratio.

This is very convenient for hashing: New keys automatically go to the emptiest regions.

Universal Hashing

Problem: For any fixed $h$, an adversary can construct key sets with arbitrarily many collisions.
Solution: Pick $h$ randomly from a family $H$ of hash functions.

$H$ is universal if for any $x\ne y\in K$:

$$\frac{|\{h\in H:h(x)=h(y)\}|}{|H|}\le \frac{1}{N}$$

The fraction says “what proportion of my hash functions cause a collision between $x$ and $y$“.
The universal property says that for any two distinct keys, at most $1/N$ of the hash functions cause a collision.
So the family is at least as good as random guessing.

Equivalently: ${\mathrm{Pr}}_H[h(x)=h(y)]\le 1/N$

---

https://claude.ai/chat/e6329d19-820e-4bb6-88f5-1a3f837faad8