hash_tables.md

Hash tables and hashing

Table of contents

• Introduction and overview
• Hash functions
  • Fowler–Noll–Vo hash function
  • Cryptographic hash functions
  • Custom hash functions
  • Combining hash values
• Hash tables
  • Bloom filter
  • Extendible hashing
• Consistent hashing
• Implementations

---

Introduction and overview

🔗

• R.L.Burk. Hashing: From good to perfect – C/C++ Users Journal 10 (1992)

Hash functions

A hash function is a function that maps data of arbitrary size to fixed-size values. A good hash function satisfies two basic properties: it should be very fast to compute and it should minimize duplication of output values (collisions). Hashing in the C++ standard library is implemented via std::hash<T> function object type.

🔗

• Hash function – Wikipedia

❔

• Why is XOR the default way to combine hashes? – Stack Overflow
• Why does Java’s hashCode() in String use 31 as a multiplier? – Stack Overflow

🎥

• D.Kühl. #Hashing – ACCU (2019)

Fowler–Noll–Vo hash function

The FNV hashing algorithm is used in the std::hash implementation in the Microsoft standard library.

Cryptographic hash functions

See Hashing – Cryptographic algorithms.

Custom hash functions

🔗

• xxHash – Extremely fast hash algorithm

Combining hash values

⚓

• N.Josuttis. Convenience functions to combine hash values – WG21/N3876

Hash tables

A hash table is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found. Hash tables in the C++ standard library go by the names of std::unordered_[multi]set and std::unordered_[multi]map. See Unordered containers – The standard library.

🔗

• Hash table – Wikipedia
• Hashtable benchmarks

❔

• Why should hash functions use a prime number modulus? – Stack Overflow
• Does making array size a prime number help in hash table implementation? Why? – Quora

🎥

• M.Kulukundis. Designing a fast, efficient, cache-friendly hash table, step by step – CppCon (2017)

Bloom filter

Bloom filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not.

🔗

• Bloom filter – Wikipedia
• Bloom filter calculator
• M.Majkowski. When Bloom filters don’t bloom (2020)
• J.Talbot. What are Bloom filters? (2015)

🎥

• A.Deutsch. Esoteric data structures and where to find them: Bloom filter – CppCon (2017)
• R.Edwards. Bloom filters
• N.L.Gowda. Bloom filter for system design

📄

• A.Broder, M.Mitzenmacher. Network applications of Bloom filters: A survey – Internet Mathematics 1, 485 (2004)
• B.H.Bloom. Space/time trade-offs in hash coding with allowable errors – Communications of the ACM 13, 422 (1970)

📖

• Sec. 12.5: Bloom filters: The basics, Sec. 12.6: Bloom filters: Heuristic analysis – Roughgarden T. Algorithms illuminated (Part 2): Graph algorithms and data structures – Soundlikeyourself Publishing (2018)

💫

• J.Davies. Bloom filters

Extendible hashing

Extendible hashing is a type of hash system that treats a hash as a bit string and uses a trie for bucket lookup.

🔗

• Extendible hashing – Wikipedia

Consistent hashing

🔗

• Consistent hashing – Wikipedia
• M.Nielsen. Consistent hashing (2009)

Implementations

❔

• Super high performance C/C++ hash map (table, dictionary) – Stack Overflow