\documentclass[12pt]{article} \usepackage{wide,me} \parindent0pt

Hashing

Dictionaries

Model

Hashing:

Hash families:

Set of all functions?

How about a random function?

Problem:

Our analysis:

Universal Hashing

Recall our pairwise independent “pseudorandom-generator”:

2-universal family: [Carter-Wegman]