A brief guide to hash tables



Summary: A brief guide to hash tables.
Topics: Hash tables, data structures, algorithms, coding
Slides: link (pdf)

References
  • W. W. Peterson, "Addressing for random-access storage." IBM journal of Research and Development (1957)
  • R. P. Brent, "Reducing the retrieval time of scatter storage techniques", Communications of the ACM (1973)
  • D. E. Knuth, "The art of computer programming, vol. 3: sorting and searching", Chap 6.4, (1974)
  • J. L. Carter et al., "Universal classes of hash functions", ACM STOC (1977)
  • P. Celis et al., "Robin hood hashing" Symposium on Foundations of Computer Science (1985)
  • J-P Aumasson et al., "SipHash: a fast short-input PRF", ICC (2012)
  • C. Heimes, "PEP 456 – Secure and interchangeable hash algorithm", https://peps.python.org/pep-0456/ (2013)
  • H. Stevens, "Hans Peter Luhn and the birth of the hashing algorithm", IEEE spectrum (2018)
  • J. Erickson, "Algorithms" http://algorithms.wtf/ "Lecture 5: Hash Tables" (2019)
  • V. Skvortsov, https://tenthousandmeters.com/blog/python-behind-the-scenes-10-how-python-dictionaries-work/ (2021)
  • T. Cormen et al., "Introduction to algorithms", Chap 11, MIT press, (2022)