Member-only story
The Art of Hashing
Introduction
Hash Maps stand out as a versatile and efficient solution for storing and retrieving key-value pairs in constant time. From searching for items in a dictionary to accessing data in a database, hash maps silently power many everyday tasks. However, the intricacies of hashing often remain a mystery. This article aims to demystify hashing by delving deep into various hash functions and hashing schemes.
Hash Functions
The Hash Function tells us how to map a large key space into a smaller domain. In simpler words, It is used to compute an index on an array of buckets or slots. There are various ways to calculate the hash of a key. We need to consider the trade-off between fast execution and collision rate. On one extreme, we have a hash function that always returns a constant (very fast, but everything is a collision). Conversely, we have a “perfect” hashing function with no collisions that would take extremely long to compute. The ideal design is somewhere in the middle.
Examples of some hash functions
- CRC-64 (1975): Used in networking for error detection.
- MurmurHash (2008): Designed as a fast, general-purpose hash function.
- Google CityHash (2011): Designed to be faster for short keys (<64 bytes).
