Hashing with linear probing

In grad school, I spent time studying analyses of various hashing schemes: uniform, double, linear probing, whatever. Alan Siegel (from the school of Knuth) at Courant Institute of Mathematical Sciences where I went to school has several fundamental results on simulating idealized hashing that assume n-wise independence among n variables on real models with limited independence and space tradeoffs. He has a simple overview on his homepage with links to papers.

In STOC 07, there is a very nice result on hashing with linear probing that has been much harder to analyze than the other variants. This result due to Pagh, Pagh and Ruzic shows that 5-wise independence suffices to obtain constant expected time per operation. The analysis (atleast as it appeared in Rasmus's talk) is elegant.