  These lecture notes show that linear probing takes expected constant time if
the hash function is 5-independent. This result was first proved by Pagh et al.
[STOC'07,SICOMP'09]. The simple proof here is essentially taken from [Patrascu
and Thorup ICALP'10]. We will also consider a smaller space version of linear
probing that may have false positives like Bloom filters.
  These lecture notes illustrate the use of higher moments in data structures,
and could be used in a course on randomized algorithms.
