14. More Hashing

views comments

Open addressed hashing
Fictional analysis: Strongly universal hashing
Linear probing and binary probing
Analysis of binary probing: full versus popular
2-uniformity and Chebyshev imply O(log n) expected time
4-uniformity and Chebychebyshevshev imply O(1) expected time
5-uniform hash families: Polynomial [Carter Wegman], twisted tabulation [Thorup Zhang]
For O(1) time with high probability, use k-way tabulation [Patrascu Thorup]

	Contact Technology Services to report an issue, offer feedback, or request assistance.
	Technology Services Home \| Kaltura Help \| Privacy Policy
	Illinois Media Space, © 2022 Board of Trustees of the University of Illinois