Theory & Advanced Topics

hash function

A hash function takes a key — a string, a number, any kind of data — and crunches it down into a fixed-size number, often used as an index into an array of buckets. Think of it as a coat-check clerk: you hand over a coat of any shape and get back a small numbered tag. The point is to turn 'where do I store or find this?' from a search into a single calculation: feed the key to the function, get a bucket number, go straight there.

A good hash function for a data structure has three qualities. It should be fast, because you compute it on every lookup. It should be deterministic — the same key must always produce the same number, or you would never find what you stored. And it should spread keys uniformly across the buckets, scattering even similar keys to different places, so the buckets fill up evenly rather than piling everything into one. With those properties a hash table can find a key in O(1) on average.

Here is the catch you cannot escape: collisions are inevitable. If you map a huge universe of possible keys into a finite number of buckets, the pigeonhole principle guarantees that two different keys will sometimes land in the same bucket — there are simply more pigeons than holes. A good hash function makes collisions rare and evenly spread, but it cannot make them impossible, so any hash-based structure also needs a plan (such as chaining or probing) for what to do when two keys collide.

// deterministic, fast, spreads keys across m buckets
int hash(const std::string& key, int m) {
  unsigned long h = 1469598103934665603ULL;  // a seed
  for (char c : key) {
    h ^= (unsigned char)c;
    h *= 1099511628211ULL;     // mix the bits
  }
  return (int)(h % m);         // confine to [0, m)
}

Same input always gives the same bucket; the modulo confines it to [0, m).

Cryptographic hashes (like SHA-256) chase a different goal — being hard to reverse. A data-structure hash just needs to be fast and spread keys evenly.

Also called

hash散列函数哈希函数雜湊函式散列函式