Summary of Hash Tables: Concepts, Operations, and Performance

Hash Tables: Concepts, Operations & Performance Explained

Summary Knowledge test Flashcards Podcast Mindmap

Introduction

Hash functions are mathematical mappings that convert inputs (keys) from a large universe into a smaller set of values (hash values). They are used widely in computer science, cryptography, networking, and data integrity. This material focuses on the theory and construction of hash functions (including universal and 2-universal families) and their application to authentication, with clear examples and proofs.

Definition: A hash function is a function $h\colon U \to {0,1,\dots,m-1}$ that maps each key in a universe $U$ to an integer in the range $0$ to $m-1$.

Key concepts and motivation

Hash functions compress or transform keys so they fit into limited-size structures or produce compact tags.
Randomized families of hash functions protect against adversarially chosen inputs by making collisions unlikely in expectation.

Definition (Universal Family): A finite family $\mathcal{H}$ of hash functions from $U$ to ${0,1,\dots,m-1}$ is universal if for every pair of distinct keys $k,l\in U$, the number of functions $h\in\mathcal{H}$ with $h(k)=h(l)$ is at most $|\mathcal{H}|/m$. Equivalently, choosing $h$ uniformly at random from $\mathcal{H}$ gives $\Pr[h(k)=h(l)]\le 1/m$.

Definition ($k$-Universal Family): A family $\mathcal{H}$ is $k$-universal if for every fixed sequence of $k$ distinct keys $x^{(1)},\dots,x^{(k)}$ and a uniformly random $h\in\mathcal{H}$, the tuple $\big(h(x^{(1)}),\dots,h(x^{(k)})\big)$ is uniformly distributed over the $m^k$ possible $k$-tuples.

2-universal implies universal

If a family is 2-universal then for any distinct $k,l$ the pair $\big(h(k),h(l)\big)$ is uniformly distributed over $m^2$ pairs, so the probability $h(k)=h(l)$ equals $m/m^2=1/m$. Thus 2-universal families satisfy the universal property.

Constructing universal and 2-universal families

We present constructions based on arithmetic modulo a prime $p$ with examples, highlighting strengths and weaknesses.

Linear family (not 2-universal)

Universe: $U={0,1,\dots,p-1}^n$ where $p$ is prime.
For each coefficient vector $a=(a_0,a_1,\dots,a_{n-1})\in U$ define $$h_a(x)=\sum_{j=0}^{n-1} a_j x_j \ \text{mod } p.$$
Reduce further if desired to range ${0,\dots,m-1}$ by taking mod $m$ after mod $p$.

Properties:

This family is universal: for distinct $x\neq y$, the equation $h_a(x)=h_a(y)$ becomes a nontrivial linear equation in the components of $a$, which has at most $p^{n-1}$ solutions among the $p^n$ possible $a$, giving collision probability $\le 1/p$ (and after reduction to $m\le p$ this implies $\le 1/m$ in appropriate constructions).
This family is not 2-universal: there exist nonzero input vectors $z$ with $z_j$ such that for every $a$ we have $h_a(z)=0$ (for example, choose $z=0$ or other structured $z$ when reduction or linear dependencies make all outputs identical). Concretely, if you use the linear form without adding an independent offset, some nonzero keys can always map to the same hash value across all $h_a$.

Example: If keys include the zero vector $0$, then for all $a$ we have $h_a(0)=0$, so multiple distinct keys cannot all share this property, but more generally linear dependencies can create fixed collisions.

Adding a random offset: making it 2-universal

Modify the family to include a constant offset $b\in\mathbb{Z}_p$: for $a\in\mathbb{Z}p^n$ and $b\in\mathbb{Z}p$ define $$h'{a,b}(x)=\left(\sum{j=0}^{n-1} a_j x_j + b\right)\ \text{mod } p.$$

Argument for 2-universality:

Fix two distinct keys $x,y\in U$ with $x_i\ne y_i$ for some index $i$. For uniformly random $(a,b)$, consider the pair $\big(h'{a,b}(x),h'{a,b}(y)\big)$. As $a_i$ and $b$ range uniformly over $\mathbb{Z}_p$, the pair ranges uniformly over $\mathbb{Z}_p^2$. Therefore every ordered pair of values occurs exactly the same number of times among choices of $(a,b)$, so the family is 2-universal.

Practical note: Including an offset (a random additive term) breaks the

FlashcardsKnowledge testSummaryPodcastMindmap

Start for free

Already have an account? Sign in

Hash Functions Overview

Klíčová slova: Hash Tables fundamentals, Collision resolution in Hash Tables, Hashing concepts for Hash Tables, Hash Functions, Open Addressing Fundamentals, Open Addressing Probing Techniques, Binary Search Trees

Klíčové pojmy: Hash function maps keys to $\{0,\dots,m-1\}$, Universal family: $\Pr[h(k)=h(l)]\le 1/m$ for distinct $k,l$, $k$-universal: outputs on any $k$ distinct inputs are uniform over $m^k$, 2-universal implies universal by pairwise uniformity, Linear family $h_a(x)=\sum a_j x_j\;\text{mod }p$ is universal, Adding offset $b$ gives $h'_{a,b}(x)=\sum a_j x_j + b\;\text{mod }p$ which is 2-universal, 2-universal family yields MAC forgery probability $\le 1/p$, Pick prime $p$ larger than key-space to apply these constructions, For authentication, keep $h$ secret and choose from a 2-universal family, Universality controls collision probability regardless of input distribution, Use offset $b$ when pairwise independence is required, Information-theoretic MACs from 2-universal families resist unlimited adversary compute

## Introduction Hash functions are mathematical mappings that convert inputs (keys) from a large universe into a smaller set of values (hash values). They are used widely in computer science, cryptography, networking, and data integrity. This material focuses on the theory and construction of hash functions (including universal and 2-universal families) and their application to authentication, with clear examples and proofs. > **Definition:** A *hash function* is a function $h\colon U \to \{0,1,\dots,m-1\}$ that maps each key in a universe $U$ to an integer in the range $0$ to $m-1$. ## Key concepts and motivation - Hash functions compress or transform keys so they fit into limited-size structures or produce compact tags. - Randomized families of hash functions protect against adversarially chosen inputs by making collisions unlikely in expectation. > **Definition (Universal Family):** A finite family $\mathcal{H}$ of hash functions from $U$ to $\{0,1,\dots,m-1\}$ is *universal* if for every pair of distinct keys $k,l\in U$, the number of functions $h\in\mathcal{H}$ with $h(k)=h(l)$ is at most $|\mathcal{H}|/m$. Equivalently, choosing $h$ uniformly at random from $\mathcal{H}$ gives $\Pr[h(k)=h(l)]\le 1/m$. > **Definition ($k$-Universal Family):** A family $\mathcal{H}$ is *$k$-universal* if for every fixed sequence of $k$ distinct keys $x^{(1)},\dots,x^{(k)}$ and a uniformly random $h\in\mathcal{H}$, the tuple $\big(h(x^{(1)}),\dots,h(x^{(k)})\big)$ is uniformly distributed over the $m^k$ possible $k$-tuples. ### 2-universal implies universal - If a family is 2-universal then for any distinct $k,l$ the pair $\big(h(k),h(l)\big)$ is uniformly distributed over $m^2$ pairs, so the probability $h(k)=h(l)$ equals $m/m^2=1/m$. Thus 2-universal families satisfy the universal property. ## Constructing universal and 2-universal families We present constructions based on arithmetic modulo a prime $p$ with examples, highlighting strengths and weaknesses. ### Linear family (not 2-universal) - Universe: $U=\{0,1,\dots,p-1\}^n$ where $p$ is prime. - For each coefficient vector $a=(a_0,a_1,\dots,a_{n-1})\in U$ define $$h_a(x)=\sum_{j=0}^{n-1} a_j x_j \ \text{mod } p.$$ - Reduce further if desired to range $\{0,\dots,m-1\}$ by taking mod $m$ after mod $p$. Properties: - This family is universal: for distinct $x\neq y$, the equation $h_a(x)=h_a(y)$ becomes a nontrivial linear equation in the components of $a$, which has at most $p^{n-1}$ solutions among the $p^n$ possible $a$, giving collision probability $\le 1/p$ (and after reduction to $m\le p$ this implies $\le 1/m$ in appropriate constructions). - This family is not 2-universal: there exist nonzero input vectors $z$ with $z_j$ such that for every $a$ we have $h_a(z)=0$ (for example, choose $z=0$ or other structured $z$ when reduction or linear dependencies make all outputs identical). Concretely, if you use the linear form without adding an independent offset, some nonzero keys can always map to the same hash value across all $h_a$. > Example: If keys include the zero vector $0$, then for all $a$ we have $h_a(0)=0$, so multiple distinct keys cannot all share this property, but more generally linear dependencies can create fixed collisions. ### Adding a random offset: making it 2-universal - Modify the family to include a constant offset $b\in\mathbb{Z}_p$: for $a\in\mathbb{Z}_p^n$ and $b\in\mathbb{Z}_p$ define $$h'_{a,b}(x)=\left(\sum_{j=0}^{n-1} a_j x_j + b\right)\ \text{mod } p.$$ Argument for 2-universality: - Fix two distinct keys $x,y\in U$ with $x_i\ne y_i$ for some index $i$. For uniformly random $(a,b)$, consider the pair $\big(h'_{a,b}(x),h'_{a,b}(y)\big)$. As $a_i$ and $b$ range uniformly over $\mathbb{Z}_p$, the pair ranges uniformly over $\mathbb{Z}_p^2$. Therefore every ordered pair of values occurs exactly the same number of times among choices of $(a,b)$, so the family is 2-universal. > Practical note: Including an offset (a random additive term) breaks the