\documentclass[12pt]{article}
\usepackage[margin=0.65in]{geometry}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{booktabs}
\usepackage{enumitem}
\usepackage{xcolor}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}

\setlength{\parindent}{0pt}
\setlength{\parskip}{3pt}

\newcommand{\DEL}{\textsc{Deleted}}

\title{\bfseries Open Addressing (CLRS 4th ed., \S 11.4)}
\author{CS5800 --- Algorithms}
\date{}

\begin{document}
\maketitle
\vspace{-2em}

\section{Setup}

\subsection{Generalized hash function}
\begin{itemize}[itemsep=1pt]
  \item No pointers, no chains: every slot holds a key or \textsc{Nil}. All $n$ elements live in the table $\Rightarrow \alpha = n/m \le 1$.
  \item $h: U\times\{0,\dots,m-1\}\to\{0,\dots,m-1\}$; second argument is the \emph{probe number} $i$.
  \item Probe sequence of key $k$: $\langle h(k,0), h(k,1),\dots,h(k,m-1)\rangle$.
  \item \textbf{Requirement:} this sequence must be a permutation of $\langle 0,\dots,m-1\rangle$ --- every slot gets visited eventually.
\end{itemize}

\subsection{Insert / Search}
\begin{algorithm}[H]
\begin{algorithmic}[1]
\Function{Hash-Insert}{$T,k$}
  \State $i\gets 0$
  \Repeat
    \State $q\gets h(k,i)$
    \If{$T[q]=\textsc{Nil}$ \textbf{or} $T[q]=\DEL$}
      \State $T[q]\gets k$; \Return $q$
    \EndIf
    \State $i\gets i+1$
  \Until{$i=m$}
  \State \textbf{error} ``overflow''
\EndFunction
\Statex
\Function{Hash-Search}{$T,k$}
  \State $i\gets 0$
  \Repeat
    \State $q\gets h(k,i)$
    \If{$T[q]=k$} \Return $q$ \EndIf
    \State $i\gets i+1$
  \Until{$T[q]=\textsc{Nil}$ \textbf{or} $i=m$}
  \State \Return \textsc{Nil}
\EndFunction
\end{algorithmic}
\end{algorithm}
\begin{itemize}[itemsep=1pt]
  \item Correctness of \textsc{Search} relies on: insertion never leaves a ``hole'' inside a key's probe sequence that stops search early.
\end{itemize}

\subsection{Delete}
\begin{itemize}[itemsep=1pt]
  \item Cannot write \textsc{Nil} into $T[q]$: some other key $k'$ may have probed through $q$ (found it occupied) and landed further along. Zeroing $q$ breaks \textsc{Search}$(T,k')$.
  \item Fix: sentinel \DEL. \textsc{Insert} may overwrite \DEL; \textsc{Search} treats \DEL as ``keep probing,'' not as a stop condition.
  \item Cost: \DEL slots inflate probe lengths over time $\Rightarrow$ chaining preferred under heavy deletion.
\end{itemize}
\begin{algorithm}[H]
\begin{algorithmic}[1]
\Function{Hash-Delete}{$T,k$}
  \State $q \gets \Call{Hash-Search}{T,k}$
  \If{$q \ne \textsc{Nil}$} $T[q]\gets \DEL$ \EndIf
\EndFunction
\end{algorithmic}
\end{algorithm}

\section{Probing schemes}
All built from an auxiliary ordinary hash function $h'(k)$ (or $h_1,h_2$).

\subsection{Linear probing}
\begin{itemize}[itemsep=1pt]
  \item $h(k,i) = (h'(k)+i)\bmod m$.
  \item Only $m$ distinct probe sequences (determined by $h'(k)$ alone).
  \item \textbf{Primary clustering}: runs of occupied slots grow; any key hashing into the run must walk it.
\end{itemize}

\subsection{Quadratic probing}
\begin{itemize}[itemsep=1pt]
  \item $h(k,i) = (h'(k)+c_1 i + c_2 i^2)\bmod m$, $c_1,c_2\ne0$.
  \item Need $c_1,c_2,m$ constrained (e.g.\ $m=2^r$) to actually hit all $m$ slots.
  \item Same $h'(k)$ $\Rightarrow$ identical later probes $\Rightarrow$ \textbf{secondary clustering}. Still only $m$ distinct sequences.
\end{itemize}

\subsection{Double hashing}
\begin{itemize}[itemsep=1pt]
  \item $h(k,i) = (h_1(k) + i\cdot h_2(k))\bmod m$.
  \item Need $h_2(k)$ coprime to $m$: take $m$ prime with $1<h_2(k)<m$, or $m=2^r$ with $h_2(k)$ odd.
  \item $\Theta(m^2)$ distinct probe sequences (depends on pair $(h_1(k),h_2(k))$) $\Rightarrow$ closest of the three to uniform hashing.
\end{itemize}

\subsection{Uniform hashing (analysis idealization)}
\begin{itemize}[itemsep=1pt]
  \item Each key's probe sequence equally likely to be any of the $m!$ permutations. No scheme achieves this exactly; double hashing approximates it best.
\end{itemize}

\begin{theorem}[11.6]
Under uniform hashing, $\alpha=n/m<1$, expected \# probes in an unsuccessful search $\le \dfrac{1}{1-\alpha}$.
\end{theorem}
\begin{proof}
$\Pr[\text{probe }i\text{ occupied}\mid \text{probes }1..i-1\text{ occupied}] = \dfrac{n-i+1}{m-i+1} \le \dfrac{n}{m} = \alpha$ (since $n<m$). Expected number of probes is
\[
1+\alpha\bigl(1+\alpha(1+\alpha(\cdots))\bigr) \le \sum_{i=0}^{\infty}\alpha^i = \frac{1}{1-\alpha}. \qedhere
\]
\end{proof}

\begin{corollary}[11.7]
Expected cost of \textsc{Insert} $\le \dfrac{1}{1-\alpha}$ (insertion = unsuccessful search + one write).
\end{corollary}

\begin{theorem}[11.8]
Under uniform hashing, expected \# probes for a successful search (uniform over the $n$ keys present) is $\le \dfrac{1}{\alpha}\ln\dfrac{1}{1-\alpha}$: average the insertion-time bound $\frac{1}{1-i/m}$ over $i=0,\dots,n-1$.
\end{theorem}

\section{Running example}
$m=11$ (prime). $h'(k) = k\bmod 11$. Insert order: $22, 33, 43, 10, 25$.

$h'(22){=}0,\ h'(33){=}0,\ h'(43){=}10,\ h'(10){=}10,\ h'(25){=}3$.

\subsection{Linear probing walk-through}
\begin{itemize}[itemsep=1pt]
  \item Insert $22$: slot $0$ empty $\to$ placed at $0$.
  \item Insert $33$: slot $0$ occupied, $i{=}1\Rightarrow$ slot $1$ empty $\to$ placed at $1$.
  \item Insert $43$: slot $10$ empty $\to$ placed at $10$.
  \item Insert $10$: slot $10$ occupied ($43$), $i{=}1\Rightarrow 0$ occ., $i{=}2\Rightarrow 1$ occ., $i{=}3\Rightarrow 2$ empty $\to$ placed at $2$.
  \item Insert $25$: slot $3$ empty $\to$ placed at $3$.
\end{itemize}
Table: slot $0{:}22,\ 1{:}33,\ 2{:}10,\ 3{:}25,\ 10{:}43$; rest \textsc{Nil}.

\textbf{Search $10$:} probe $10$ (holds $43\ne10$) $\to$ probe $0$ ($22\ne10$) $\to$ probe $1$ ($33\ne10$) $\to$ probe $2$ ($10=10$, found) --- exactly retraces the insertion probe sequence, as guaranteed.

\textbf{Delete $33$ (slot 1), naively:} set $T[1]=\textsc{Nil}$. Now search$(10)$: probe $10$ occ., probe $0$ occ., probe $1 = \textsc{Nil}\Rightarrow$ loop stops, reports ``not found'' --- \emph{wrong}, $10$ is still at slot $2$. This is exactly the hole-in-the-middle failure motivating \DEL.

\textbf{Delete $33$, correctly:} $T[1]\gets\DEL$. Now search$(10)$: probe $10$ occ., probe $0$ occ., probe $1=\DEL\Rightarrow$ keep going (not a stop condition), probe $2$: found. Correct.

\subsection{Same keys, double hashing}
$h_1(k)=k\bmod 11$, $h_2(k) = 1+(k\bmod 7)$, so $h(k,i)=(h_1(k)+i\cdot h_2(k))\bmod 11$.

\begin{itemize}[itemsep=1pt]
  \item Insert $22$: $h_1{=}0$, slot $0$ empty $\to 0$.
  \item Insert $33$: $h_1{=}0$ occ.; $h_2(33)=1+(33\bmod7)=1+5=6$; $i{=}1\Rightarrow (0+6)\bmod11=6$, empty $\to 6$.
  \item Insert $43$: $h_1{=}10$, empty $\to 10$.
  \item Insert $10$: $h_1{=}10$ occ.; $h_2(10)=1+3=4$; $i{=}1\Rightarrow (10+4)\bmod11=3$, empty $\to 3$.
  \item Insert $25$: $h_1{=}3$ occ. (by $10$ now!); $h_2(25)=1+4=5$; $i{=}1\Rightarrow(3+5)\bmod11=8$, empty $\to 8$.
\end{itemize}
Table: $0{:}22,\ 3{:}10,\ 6{:}33,\ 8{:}25,\ 10{:}43$ --- occupied slots spread out rather than bunched at $\{0,1,2,3\}$ as under linear probing, even though three of the five keys share $h_1$-collisions with another key. Deletion works identically via \DEL; the correctness argument doesn't depend on which probing scheme produced the sequence.

\section{Comparison}
\begin{center}
\begin{tabular}{@{}lccc@{}}
\toprule
 & Linear & Quadratic & Double hashing \\
\midrule
Formula & $h'(k){+}i$ & $h'(k){+}c_1i{+}c_2i^2$ & $h_1(k){+}i\,h_2(k)$ \\
Distinct probe sequences & $m$ & $m$ & $\Theta(m^2)$ \\
Clustering & primary & secondary & essentially none \\
Extra constraints & none & $c_1,c_2$ vs.\ $m$ & $\gcd(h_2(k),m)=1$ \\
Closeness to uniform hashing & worst & middle & best \\
\bottomrule
\end{tabular}
\end{center}
\begin{itemize}[itemsep=1pt]
  \item All three share the same deletion problem and the same $\alpha\le1$ ceiling --- these are properties of open addressing itself, not of the probing scheme.
  \item As $\alpha\to1$, expected probe counts $\to\infty$ (Thm.\ 11.6/11.8) for any scheme; open addressing degrades harder near capacity than chaining does.
  \item Practical takeaway: double hashing dominates linear/quadratic whenever clustering matters and is the usual default; chaining still wins when deletions are frequent, since \DEL markers never get reclaimed under open addressing without a table rebuild.
\end{itemize}

\section*{Advanced ($\star$): Cuckoo Hashing}
\textit{Not in CLRS \S 11.4 --- Pagh--Rodler 2001. Included because it's the natural next question after double hashing.}

\subsection*{Setup}
\begin{itemize}[itemsep=1pt]
  \item Two tables $T_1,T_2$ (size $m$ each), two hash functions $h_1,h_2$.
  \item Key $k$ may live \emph{only} at $T_1[h_1(k)]$ or $T_2[h_2(k)]$ --- exactly two candidate homes, ever.
  \item Contrast with double hashing: there, a key has $m$ candidate homes (the whole probe sequence); here, just $2$.
\end{itemize}

\subsection*{Search / Delete}
\begin{itemize}[itemsep=1pt]
  \item \textsc{Search}$(k)$: check $T_1[h_1(k)]$, then $T_2[h_2(k)]$. Two probes, always --- \textbf{worst-case $O(1)$}, not just expected.
  \item \textsc{Delete}$(k)$: locate via search, set that slot to \textsc{Nil} directly. \emph{No \DEL{} sentinel needed} --- unlike double hashing, no other key's path can be broken, since paths don't exist (only two fixed homes each).
\end{itemize}

\subsection*{Insert: eviction chain}
\begin{algorithm}[H]
\begin{algorithmic}[1]
\Function{Cuckoo-Insert}{$k$}
  \For{$\mathit{tries} = 1$ \textbf{to} $\mathit{MaxLoop}$}
    \If{$T_1[h_1(k)] = \textsc{Nil}$} $T_1[h_1(k)]\gets k$; \Return \EndIf
    \State $k \leftrightarrow T_1[h_1(k)]$ \Comment{swap $k$ in, evict resident}
    \If{$T_2[h_2(k)] = \textsc{Nil}$} $T_2[h_2(k)]\gets k$; \Return \EndIf
    \State $k \leftrightarrow T_2[h_2(k)]$ \Comment{swap, evict resident}
  \EndFor
  \State \textbf{rehash} with new $h_1,h_2$ (or grow tables); reinsert everything
\EndFunction
\end{algorithmic}
\end{algorithm}
\begin{itemize}[itemsep=1pt]
  \item Each eviction bounces the displaced key to its \emph{other} home; that may evict someone else, etc. --- a chain.
  \item Chain usually terminates quickly (empty slot found). It can also \textbf{cycle} back to $k$'s own home $\Rightarrow$ declare failure, rehash from scratch.
  \item Cycles become likely once $\alpha \gtrsim 0.5$ (for the 2-table version) --- much tighter ceiling than open addressing's $\alpha<1$.
\end{itemize}

\subsection*{Running example, continued}
$T_1,T_2$ size $5$. $h_1(k)=k\bmod 5$, $h_2(k) = \lfloor k/5\rfloor \bmod 5$.
\begin{itemize}[itemsep=1pt]
  \item Insert $22$: $h_1(22)=2$, $T_1[2]$ empty $\to$ placed.
  \item Insert $33$: $h_1(33)=3$, $T_1[3]$ empty $\to$ placed.
  \item Insert $43$: $h_1(43)=3$, occupied by $33$. Evict $33$: $h_2(33) = \lfloor33/5\rfloor\bmod5 = 6\bmod5=1$, $T_2[1]$ empty $\to$ $33$ placed there; $43$ takes $T_1[3]$.
  \item Insert $10$: $h_1(10)=0$, $T_1[0]$ empty $\to$ placed.
  \item Insert $25$: $h_1(25)=0$, occupied by $10$. Evict $10$: $h_2(10)=\lfloor10/5\rfloor\bmod5=2$, $T_2[2]$ empty $\to$ $10$ placed there; $25$ takes $T_1[0]$.
\end{itemize}
Final: $T_1[0]{=}25,\ T_1[2]{=}22,\ T_1[3]{=}43$; \ $T_2[1]{=}33,\ T_2[2]{=}10$. One eviction chain of length $1$ occurred twice; no cycle.

\textsc{Search}$(10)$: $T_1[h_1(10){=}0]=25\ne10$, $T_2[h_2(10){=}2]=10$ --- found in exactly $2$ probes, regardless of table state. Compare to double hashing's $10$, which took $2$ probes there \emph{by luck of the sequence}, not by guarantee.

\subsection*{Cuckoo vs.\ double hashing}
\begin{center}
\begin{tabular}{@{}lcc@{}}
\toprule
 & Double hashing & Cuckoo hashing \\
\midrule
Candidate homes per key & up to $m$ & exactly $2$ \\
Search cost & expected $O(1/(1-\alpha))$ & \textbf{worst-case} $O(1)$ (2 probes) \\
Insert cost & expected $O(1/(1-\alpha))$ & amortized $O(1)$, occasional rehash \\
Deletion & needs \DEL{} sentinel & direct \textsc{Nil}, no sentinel \\
Max useful load $\alpha$ & up to $\approx 1$ & $\lesssim 0.5$ (2-table version) \\
Failure mode & degrades gracefully & can cycle $\Rightarrow$ full rehash \\
\bottomrule
\end{tabular}
\end{center}
\begin{itemize}[itemsep=1pt]
  \item Cuckoo trades table-space efficiency (lower max $\alpha$) for a hard worst-case search guarantee --- valuable when tail latency matters more than average load.
  \item Both are pointer-free, cache-friendly schemes; cuckoo's two-probe search is friendlier to hardware/parallel lookups (two independent cache lines, checked concurrently).
\end{itemize}

\section{Chaining vs.\ Open Addressing}

\subsection*{Chaining (\S 11.2)}
\begin{itemize}[itemsep=1pt]
  \item Each slot $T[j]$ is a linked list (or other structure) of all keys hashing there.
  \item \textbf{+} Simple, correct deletion: unlink the node, $O(1)$ given a pointer to it. No sentinel, no degradation.
  \item \textbf{+} $\alpha=n/m$ can exceed $1$ --- table doesn't "fill up"; performance degrades smoothly ($\Theta(1+\alpha)$ expected search).
  \item \textbf{+} Insert is $O(1)$ worst case (prepend to list) --- no probing, no failure mode, no rehash trigger.
  \item \textbf{+} Robust to a bad load factor: cost grows linearly in $\alpha$, not via a $1/(1-\alpha)$ blowup.
  \item \textbf{--} Pointer overhead per element (space), and pointer-chasing is cache-unfriendly --- list nodes scattered in memory.
  \item \textbf{--} Needs dynamic memory allocation for nodes; more constant-factor overhead than array slots.
\end{itemize}

\subsection*{Open addressing (\S 11.4)}
\begin{itemize}[itemsep=1pt]
  \item \textbf{+} No pointers: all data lives in the table array itself. Better cache locality (probes are nearby/computed, not chased).
  \item \textbf{+} Lower memory overhead per element --- just the key (and maybe a status bit), no node/pointer.
  \item \textbf{--} Hard ceiling $\alpha \le 1$; performance craters as $\alpha \to 1$ ($1/(1-\alpha)\to\infty$, Thm.\ 11.6/11.8) --- much more load-factor-sensitive than chaining.
  \item \textbf{--} Deletion is awkward: needs \DEL{} sentinel (linear/quadratic/double hashing), which \emph{never gets reclaimed} without a full rehash --- long-running tables with many deletes silently degrade.
  \item \textbf{--} Clustering (primary for linear, secondary for quadratic) unless double hashing (or cuckoo) is used.
  \item Cuckoo hashing (advanced, above) fixes open addressing's search-time variance (worst-case $O(1)$) but pays for it with an even tighter load ceiling ($\alpha\lesssim0.5$) and a genuine failure mode (cycles $\Rightarrow$ rehash).
\end{itemize}

\subsection*{When to use which}
\begin{center}
\begin{tabular}{@{}ll@{}}
\toprule
Use chaining when & Use open addressing when \\
\midrule
deletions are frequent & deletions are rare/absent \\
load factor unpredictable or $>1$ & $n$ known in advance, $\alpha$ kept moderate \\
elements are large/variable-size & elements are small, uniform (fit in a slot) \\
simplicity/correctness prioritized & cache performance / memory footprint matters \\
\bottomrule
\end{tabular}
\end{center}
\begin{itemize}[itemsep=1pt]
  \item Rule of thumb: open addressing (esp.\ double hashing or cuckoo) wins in performance-critical, insert/lookup-heavy, low-deletion settings (e.g.\ compilers' symbol tables during a single pass, static dictionaries). Chaining wins whenever the table's contents churn heavily or $\alpha$ can't be bounded away from $1$.
\end{itemize}

\end{document}
