\documentclass{paper}

\setlength {\parindent} {0 pt}
\setlength {\parskip} {1.5 ex plus 0.5 ex minus 0.2 ex}

\usepackage{fullpage}
\usepackage {amssymb}
\usepackage {amsmath}
\usepackage {amsthm}
%\usepackage {wasysym}
\usepackage [usenames] {color}

\usepackage {enumerate}
\usepackage {cite}
\usepackage{float}
\usepackage {xspace}


\floatstyle{ruled}
\newfloat{algorithm}{thp}{alg}
\floatname{algorithm}{Algorithm}


%\usepackage {hyperref}

\newcommand {\mathset} [1] {\ensuremath {\mathbb {#1}}}
\newcommand {\R} {\mathset {R}}
\newcommand {\Q} {\mathset {Q}}
\newcommand {\Z} {\mathset {Z}}
\newcommand {\EX} {\mathbf {E}}
\newcommand {\script} [1] {\ensuremath {\mathcal {#1}}}
\newcommand {\etal} {\textit {et al.}}
\newcommand {\eps} {\varepsilon}
\newcommand {\eqdef} {:=}
\newcommand {\boruvka}{Bor\r{u}vka}
\newcommand {\wspd}{\texttt{wspd}}
\DeclareMathOperator{\emst}{emst}
\DeclareMathOperator{\conv}{CH}
\DeclareMathOperator{\argmin}{argmin}
\DeclareMathOperator{\DT}{DT}
\DeclareMathOperator{\UC}{UC}
\DeclareMathOperator{\LC}{LC}
\newcommand{\DKL}{D_\textup{KL}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{problem}[theorem]{Problem}
\newtheorem{obs}[theorem]{Beobachtung}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{definition}[theorem]{Definition}


\title{Hashing}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle

\section{Verkettung}

\begin{itemize}
\item \texttt{put}$(k,v)$:
  Durchsuche die verkettete Liste bei 
  \texttt{elements}$[h(k)]$ nach $k$. Ersetze den
  Wert durch $v$, bzw.~lege einen neuen
  Eintrag an.

\item \texttt{get}$(k)$:
  Durchsuche die verkettete Liste bei
  \texttt{elements}$[h(k)]$ nach $k$. Gib den
  Wert f\"ur $k$ zur\"uck, bzw.~wirf eine
  \texttt{NoSuchElementException}.

\item \texttt{remove}$(k)$:
  Durchsuche die verkettete Liste bei
  \texttt{elements}$[h(k)]$ nach $k$. L\"osche den 
  Eintrag f\"ur $k$, bzw.~wirf eine
  \texttt{NoSuchElementException}.
\end{itemize}

\section{Offene Adressierung (lineares Sondieren)}

\begin{itemize}
\item \texttt{put}$(k,v)$:
\begin{verbatim}
  pos <- h(k)
  delPos <- NULL
  for i := 1 to N do
    if (elements[pos].k == k)
      elements[pos] <- (k,v)  
      return
    if (elements[pos] == DELETED && delPos == NULL)
      delPos <- pos
    if (elements[pos] == NULL) 
      break
    pos <- (pos + 1) mod N
  if (delPos != NULL)
    elements[delPos] <- (k,v)
  else if (elements[pos] == NULL) then
    elements[pos] <- (k,v)
  else
    throw TableFullException
\end{verbatim}

\item \texttt{get}$(k)$:
\begin{verbatim}
  pos <- h(k)
  for i := 1 to N do 
    if (elements[pos] == NULL)
      throw NoSuchElementException
    if (elements[pos].k == k)
      return elements[pos].v
    pos <- (pos + 1) mod N
  throw NoSuchElementException
\end{verbatim}

\item \texttt{remove}$(k)$:
\begin{verbatim}
  pos <- h(k)
  for i := 1 to N do
    if (elements[pos] == NULL)
      throw NoSuchElementException
    if (elements[pos].k == k)
      elements[pos] <- DELETED
      return 
    pos <- (pos + 1) mod N
  throw NoSuchElementException
\end{verbatim}
\end{itemize}

\section{Kuckuck}

\begin{itemize}
\item \texttt{get}$(k)$:
\begin{verbatim}
  if (elements[h1(k)].k == k)
    return elements[h1(k)].v
  if (elements[h2(k)].k == k)
    return elements[h2(k)].v
  throw NoSuchElementException
\end{verbatim}

\item \texttt{remove}$(k)$:
\begin{verbatim}
  if (elements[h1(k)].k == k)
    elements[h1(k)] <- NULL
    return
  if (elements[h2(k)].k == k)
    elements[h2(k)] <- NULL
    return
  throw NoSuchElementException
\end{verbatim}


\item \texttt{put}$(k, v)$:
\begin{verbatim}
  if (elements[h1(k)].k == k)
    elements[h1(k)] <- (k,v)
    return
  if (elements[h2(k)].k == k)
    elements[h2(k)] <- (k,v) 
    return
  if (|S| == N)
    throw TableFullException
  pos <- h1(k)
  for i := 1 to N do
    if (elements[pos] == NULL)
      elements[pos] <- (k,v)
      return
    (k,v) <-> elements[pos]
    if (pos == h1(k))
      pos <- h2(k)
    else
      pos <- h1(k)
  Waehle neue Hashfunktionen und baue die Tabelle neu auf. 
  put(k,v)
\end{verbatim}
\end{itemize}
\end{document}