%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% LATEX-TEMPLATE PRESENTATIE
%-------------------------------------------------------------------------------
% Voor informatie over presenterenn, zie
% http://practicumav.nl/presenteren/presenteren.html
% Voor readme en meest recente versie van het template, zie
% https://gitlab-fnwi.uva.nl/informatica/LaTeX-template.git
% Gebaseerd op een template van: http://www.LaTeXTemplates.com
% Licentie: CC BY-NC-SA 3.0
% (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%-------------------------------------------------------------------------------
%	PACKAGES EN CONFIGURATIE
%-------------------------------------------------------------------------------

\documentclass[aspectratio=43]{uva-inf-presentation}
\usepackage[dutch]{babel}

% ---Added packages---

% Listings
\usepackage{listings}
\usepackage{xcolor}
\definecolor{mGreen}{rgb}{0,0.6,0}
\definecolor{mGray}{rgb}{0.5,0.5,0.5}
\definecolor{mPurple}{rgb}{0.58,0,0.82}
\definecolor{backgroundColour}{rgb}{0.95,0.95,0.92}
\lstdefinestyle{CStyle}{
    %backgroundcolor=\color{backgroundColour},   
    commentstyle=\color{mGreen},
    keywordstyle=\color{red},
    numberstyle=\tiny\color{mGray},
    stringstyle=\color{mPurple},
    basicstyle=\normalsize,
    breakatwhitespace=false,         
    breaklines=true,                 
    captionpos=b,                    
    keepspaces=true,                 
    numbers=left,                    
    numbersep=5pt,                  
    showspaces=false,                
    showstringspaces=false,
    showtabs=false,                  
    tabsize=4,
    language=C
}
\lstdefinestyle{CStyleS}{
    %backgroundcolor=\color{backgroundColour},   
    commentstyle=\color{mGreen},
    keywordstyle=\color{red},
    numberstyle=\tiny\color{mGray},
    stringstyle=\color{mPurple},
    basicstyle=\small,
    breakatwhitespace=false,         
    breaklines=true,                 
    captionpos=b,                    
    keepspaces=true,                 
    numbers=left,                    
    numbersep=5pt,                  
    showspaces=false,                
    showstringspaces=false,
    showtabs=false,                  
    tabsize=4,
    language=C
}

% Graphicx
\usepackage{graphicx}

% PDF Pages
\usepackage{pdfpages}

% SVG
\usepackage{svg}

% PST
\usepackage{pst-node,pst-plot}

% Pi font
\usepackage{pifont}

\title{Hash-tabellen}
\course{Practicum Academische Vaardigheden}
\assignment{Naam van het samen te vatten boek}
\assignmenttype{Samenvatting}
\authors{Robin Wacanno}
\uvanetids{11741163}
\tutor{W.R.J. Vermeulen}
\mentor{}
\docent{}
\group{A1 - ALGOL}

\begin{document}

\begin{titelframe}
% De eerste slide is de titelpagina
\titlepage
\end{titelframe}

\begin{frame}
% Geeft een inhoudsopgave voor de presentatie
\frametitle{Inhoudsopgave}
\tableofcontents
\end{frame}

\section{Inleiding}

\begin{frame}
\Large{\bfseries \centerline{Inleiding}}
\end{frame}

\begin{frame}
\frametitle{Ontstaan}
\begin{itemize}
\item 1953
\item Gene Amdahl
\item {\footnotesize \[Uitvoeringstijd_{na} = \frac{Uitvoeringstijd_{be\ddot invloed}}{Mate\ van\ verbetering} + Uitvoeringstijd_{onbe\ddot invloed}\]}
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Eigenschappen}
\begin{itemize}
\item 
\begin{table}[]
\label{my-label}
\begin{tabular}{|l|l|l|c}
\cline{1-1} \cline{3-3}
Sleutel & + & Waarde & \hspace{4.763cm} \\ \cline{1-1} \cline{3-3}
\end{tabular}
\end{table}
\item Snelheid onafhankelijk van inhoud*
\item Niet gesorteerd
\end{itemize}

\end{frame}

\begin{frame}
\frametitle{Redenen voor gebruik}
\begin{itemize}
\item Koppelen van objecten
\item Snel zoeken
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Introductie voorbeeld}
\centering 
Studentnummer\\
$\downarrow$
\begin{table}[]
\label{my-label}
\begin{tabular}{|c|}
\hline
Naam \\ \hline
Geboortedatum \\ \hline
\end{tabular}
\end{table}
\end{frame}

\begin{frame}[fragile]
\frametitle{Introductie voorbeeld}
\begin{lstlisting}[style=CStyle]
struct student { 
    char* naam;
    char* geboortedatum;
};
\end{lstlisting}
\end{frame}

\section{De hash-functie}

\begin{frame}
\Large{\bfseries \centerline{De hash-functie}}
\end{frame}

\begin{frame}
\frametitle{Wat is hashen}
\begin{itemize}
\item Groot naar klein bereik 
\item Een richting 
\end{itemize}
\begin{figure}
\centering
\scalebox{1}{\input{hash3}}
\end{figure}
\end{frame}

\begin{frame}
\frametitle{Redenen voor gebruik}
\begin{itemize}
\item Wachtwoordopslag
\item Foutherkenning
\item En ... hash-tabellen
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{SHA-256 voorbeeld}

\begin{table}[]
\centering
\begin{tabular}{c}
\large test                                                                                 \\
$\downarrow$                                                                           \\ \hline
\multicolumn{1}{|c|}{\rule{0pt}{1mm} \large SHA-256}                                                        \\ \hline
$\downarrow$                                                                           \\
\multicolumn{1}{l}{\footnotesize f2ca1bb6c7e907d06dafe4687e579fce76b37e4e93b7605022da52e6ccc26fd2}
\end{tabular}
\label{sha-voorbeeld}
\end{table}
\end{frame}

\begin{frame}
\frametitle{SHA-256 verandering}

\begin{table}[]
\centering
\begin{tabular}{c}
\large tast                                                                                 \\
$\downarrow$                                                                           \\ \hline
\multicolumn{1}{|c|}{\rule{0pt}{1mm} \large SHA-256}                                                        \\ \hline
$\downarrow$                                                                           \\
\multicolumn{1}{l}{\footnotesize b5f76f08ac46d0690962cdbd5ca39bfafe370327183fca594dca9c72c4676e61}
\end{tabular}
\label{sha-voorbeeld}
\end{table}
\end{frame}

\begin{frame}
\frametitle{Hashen m.b.t. een hash-tabel}
\begin{itemize}
\item Index
\item Bereik array
\item Gelijke verdeling
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Opbouw van een hash-tabel}
\begin{lstlisting}[style=CStyle]
struct element {
    int studentnummer;
    struct student* studentInfo;
};
\end{lstlisting}
\end{frame}

% \begin{frame}
% \frametitle{Opbouw van een hash-tabel}

% \begin{table}[]
% \label{my-label}
% \begin{tabular}{llllll}
% \hline
% \multicolumn{1}{|c|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} \\ \hline
% 0 & 1 & 2 & 3 & 4 & 5
% \end{tabular}
% \end{table}

% \end{frame}

\begin{frame}[fragile]
\frametitle{Hash-functie voorbeeld}
\begin{lstlisting}[style=CStyle]
int hashSleutel(sleutel)
{
    return sleutel % GROOTTE;
}
\end{lstlisting}
\end{frame}

\begin{frame}
\frametitle{Voorbeeldberekening}

\begin{table}[]
\label{my-label}
\begin{tabular}{|l|l|l|}
\cline{1-1} \cline{3-3}
\multicolumn{1}{|c|}{11678326} & \ding{221} & 4 \\ \cline{1-1} \cline{3-3} 
11467841                       & \ding{221} & 5 \\ \cline{1-1} \cline{3-3} 
11741162                       & \ding{221} & 2 \\ \cline{1-1} \cline{3-3} 
11893267                       & \ding{221} & 1 \\ \cline{1-1} \cline{3-3} 
\end{tabular}
\end{table}

\begin{table}[]
\label{my-label}
\centering
\begin{tabular}{llllll}
\hline
\multicolumn{1}{|c|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} \\ \hline
0 & 1 & 2 & 3 & 4 & 5
\end{tabular}
\end{table}
\end{frame}


\section{Werking hash-tabel}

\begin{frame}
\Large{\bfseries \centerline{Werking van een hash-tabel}}
\end{frame}

\begin{frame}
\frametitle{Handelingen bij een hash-tabel}
\begin{itemize}
\item Plaatsen
\item Zoeken
\item Verwijderen
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Plaatsen}
\begin{lstlisting}[style=CStyleS]
#define GROOTTE 6

void plaats(sleutel, *studentInfo, tabel[])
{
    int index = hashSleutel(sleutel);
    
    tabel[index] = studentInfo
}

\end{lstlisting}
\end{frame}

\begin{frame}[fragile]
\frametitle{Zoeken}
\begin{lstlisting}[style=CStyleS]
struct element* zoek(sleutel, tabel[])
{
    int index = hashSleutel(sleutel);
    
    return tabel[index];
}

\end{lstlisting}
\end{frame}

\begin{frame}[fragile]
\frametitle{Verwijderen}
\begin{lstlisting}[style=CStyleS]
void verwijder(sleutel, tabel[])
{
    int index = hashSleutel(sleutel);
    
    tabel[index] = NULL
}
\end{lstlisting}
\end{frame}

\section{Problematiek bij hash-tabellen}

\begin{frame}
\Large{\bfseries \centerline{Problematiek en oplossingen}}
\end{frame}

\begin{frame}
\frametitle{Botsingen bij het plaatsen}
\begin{table}[]
\label{my-label}
\begin{tabular}{|l|l|l|}
\cline{1-1} \cline{3-3}
\multicolumn{1}{|c|}{11678326} & \ding{221} & 4 \\ \cline{1-1} \cline{3-3} 
11467841                       & \ding{221} & 5 \\ \cline{1-1} \cline{3-3} 
11741162                       & \ding{221} & 2 \\ \cline{1-1} \cline{3-3} 
11893267                       & \ding{221} & 1 \\ \cline{1-1} \cline{3-3} 
\end{tabular}
\end{table}

\begin{table}[]
\label{my-label}
\begin{tabular}{|l|l|l|}
\cline{1-1} \cline{3-3}
\multicolumn{1}{|c|}{11538902} & \ding{221} & 2 \\ \cline{1-1} \cline{3-3} 
\end{tabular}
\end{table}

\begin{table}[]
\label{my-label}
\centering
\begin{tabular}{llllll}
\hline
\multicolumn{1}{|c|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} \\ \hline
0 & 1 & 2 & 3 & 4 & 5
\end{tabular}
\end{table}
\end{frame}

\begin{frame}
\frametitle{Open adressering}
\begin{table}[]
\label{my-label}
\centering
\begin{tabular}{llllll}
\hline
\multicolumn{1}{|c|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} \\ \hline
0 & 1 & 2 & 3 & 4 & 5
\end{tabular}
\end{table}

\begin{itemize}
\item Linear probing
\item Quadratic probing\\
$hash(sleutel) + n^2$
\item Double hashing\\
$hash_1(sleutel) + n \cdot hash_2(sleutel)$
\end{itemize}

\end{frame}

\begin{frame}
\frametitle{Ketenen (gesloten adressering)}
\begin{table}[]
\centering
\label{my-label}
\begin{tabular}{|l|l|l|l|l|}
\cline{1-1} \cline{3-3} \cline{5-5}
1 & \ding{221} & $1_1$ & \ding{221} & $1_n$ \\ \cline{1-1} \cline{3-3} \cline{5-5} 
2 & \ding{221} & $2_1$ & \ding{221} & $2_n$ \\ \cline{1-1} \cline{3-3} \cline{5-5} 
3 & \ding{221} & $3_1$ & \ding{221} & $3_n$ \\ \cline{1-1} \cline{3-3} \cline{5-5} 
4 & \ding{221} & $4_1$ & \ding{221} & $4_n$ \\ \cline{1-1} \cline{3-3} \cline{5-5} 
5 & \ding{221} & $5_1$ & \ding{221} & $5_n$ \\ \cline{1-1} \cline{3-3} \cline{5-5} 
6 & \ding{221} & $6_1$ & \ding{221} & $6_n$ \\ \cline{1-1} \cline{3-3} \cline{5-5} 
\end{tabular}
\end{table}
\end{frame}

\begin{frame}
\frametitle{Voorbeeld ketenen}
\begin{table}[]
\label{my-label}
\begin{tabular}{|l|l|l|}
\cline{1-1} \cline{3-3}
\multicolumn{1}{|c|}{11678326} & \ding{221} & 4 \\ \cline{1-1} \cline{3-3} 
11467841                       & \ding{221} & 5 \\ \cline{1-1} \cline{3-3} 
11741162                       & \ding{221} & 2 \\ \cline{1-1} \cline{3-3} 
11893267                       & \ding{221} & 1 \\ \cline{1-1} \cline{3-3} 
\end{tabular}
\end{table}

\begin{table}[]
\label{my-label}
\begin{tabular}{|l|l|l|}
\cline{1-1} \cline{3-3}
\multicolumn{1}{|c|}{11538902} & \ding{221} & 2 \\ \cline{1-1} \cline{3-3} 
\end{tabular}
\end{table}

\begin{table}[]
\label{my-label}
\centering
\begin{tabular}{llllll}
\hline
\multicolumn{1}{|c|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} \\ \hline
0 & 1 & 2 & 3 & 4 & 5
\end{tabular}
\end{table}
\end{frame}

\begin{frame}
\frametitle{Grootte van de tabel}
\begin{itemize}
\item $Vullingsgraad = \frac{n}{k}$
\item Vulling \ding{221} vertraging
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Uitbreiden van de tabel}
\begin{table}[]
\label{my-label}
\centering
\begin{tabular}{llllll}
\hline
\multicolumn{1}{|c|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} \\ \hline
0 & 1 & 2 & 3 & 4 & 5
\end{tabular}
\end{table}

\centering

$\downarrow$

\begin{table}[]
\label{my-label}
\centering
\begin{tabular}{llllllllllll}
\hline
\multicolumn{1}{|c|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} & \multicolumn{1}{l|}{} \\ \hline
0\  & 1\  & 2\  & 3\  & 4\  & 5\  & 6\  & 7\  & 8\  & 9\  & 10 & 11
\end{tabular}
\end{table}
\end{frame}

\section{Tijdscomplexiteit}

\begin{frame}
\Large{\bfseries \centerline{Tijdscomplexiteit}}
\end{frame}

\begin{frame}
\frametitle{Tijdscomplexiteit}

\centering
\begin{tabular}{|l|c|c|}
\hline
\textbf{Operatie} & \textbf{Gemiddeld} & \textbf{Uiterste} \\ \hline
Zoeken & $\mathcal{O}(1)$ & $\mathcal{O}(n)$ \\ \hline
Toevoegen & $\mathcal{O}(1)$ & $\mathcal{O}(n)$ \\ \hline
Verwijderen & $\mathcal{O}(1)$ & $\mathcal{O}(n)$ \\ \hline
Uitbreiden & $\mathcal{O}(n)$ & $\mathcal{O}(n)$ \\ \hline
\end{tabular}

\end{frame}

\begin{frame}
\vspace{1cm}
\centering
{\huge Zijn er nog vragen?}
\end{frame}

\end{document}
