DSAHashing

Hashing

Hashing is the process of mapping data of arbitrary size to a fixed-size value called a hash (or digest). A hash function takes any input — a string, a number, a file — and deterministically produces a compact fingerprint of that input.

This single idea powers some of the most important data structures and algorithms in computer science: hash tables, caches, checksums, cryptography, bloom filters, and deduplication.

What a Hash Function Does

A hash function h maps a key k to an integer in the range [0, m-1], where m is the number of available slots (e.g. the size of a hash table's backing array).

h(k) → [0, m-1]

The resulting integer is called the hash value, hash code, or simply the hash.

A naive hash function for strings

JS
function simpleHash(key, tableSize) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash = (hash + key.charCodeAt(i)) % tableSize;
  }
  return hash;
}

simpleHash("apple", 10);  // e.g. 2
simpleHash("mango", 10);  // e.g. 7
simpleHash("apple", 10);  // still 2 — deterministic
Note
This naive function is a teaching example — it is far too weak for real use. Real hash functions are discussed below.
Properties of a Good Hash Function

A hash function is only useful if it satisfies several key properties:

  • Determinism — the same input must always produce the same output. If h("apple") returns 42 today, it must return 42 tomorrow, on every machine, in every run.

  • Uniform distribution — hash values should spread evenly across the full output range. Clustering (many keys mapping to the same slot) degrades performance.

  • Avalanche effect — a tiny change in the input (one bit) should drastically change the output. This prevents attackers from predicting where a nearby key will land.

  • Speed — hashing must be fast (ideally O(1) per input byte) because it is on the critical path of every hash table operation.

  • Low collision rate — different inputs should (ideally) produce different outputs. Collisions are unavoidable but a good function minimises them.

The Avalanche Effect in Practice

Avalanche effect demo with a strong hash

JS
// Using Node.js built-in crypto for illustration
const crypto = require('crypto');

function md5(s) {
  return crypto.createHash('md5').update(s).digest('hex');
}

console.log(md5("hello"));        // 5d41402abc4b2a76b9719d911017c592
console.log(md5("hellO"));        // 2f2f3e5a9ed7b7b7697b32bb2e8de8e8
//                                    ↑ completely different despite one letter change
The Birthday Paradox: Why Collisions Are Inevitable

Suppose your hash function produces values in the range [0, 364] (365 possible outputs). How many random inputs do you need before two of them are likely to share the same hash?

Intuitively you might guess 183 (half of 365). The correct answer is about 23.

This is the Birthday Paradox: the probability that two people in a room share a birthday exceeds 50% once the room has just 23 people — even though there are 365 possible birthdays.

The formula for the probability of at least one collision after inserting n items into a hash space of size m is approximately:

P(collision) ≈ 1 - e^(-n² / 2m)

For SHA-256 with m = 2^256 outputs, you would need to hash roughly 2^128 inputs before a collision became likely — a number far beyond any feasible computation. For a 32-bit hash (m ≈ 4 billion) a collision is already more likely than not at just n ≈ 77,000 inputs.

Implication for hash tables: if your table has m buckets and you insert n keys, collisions become common once n grows to the same order of magnitude as sqrt(m). This is why hash tables resize (rehash) when they get too full — not to prevent all collisions, but to keep the expected number of collisions per bucket small.

Load Factor: The Key Performance Variable

The load factor α (alpha) of a hash table is:

α = n / m

where n is the number of stored entries and m is the number of buckets.

  • If α = 0.1, the table is 10% full — very few collisions, but wasted memory.
  • If α = 0.7, the table is 70% full — a common sweet spot balancing speed and memory.
  • If α = 1.0, the table is 100% full — severe performance degradation.
  • If α > 1.0, impossible with open addressing; with chaining, every bucket has more than one entry on average.

Most production hash tables trigger a resize (typically doubling m and rehashing all entries) when α crosses a threshold — usually 0.75 in Java's HashMap, ~0.66 in Python's dict.

Load Factor α

Average lookups (chaining)

Behaviour

0.1

1.05

Very sparse — memory inefficient

0.5

1.25

Light load — fast

0.75

1.88

Typical resize threshold — good balance

0.9

5.50

Heavy load — noticeably slower

1.0

∞ (for open addressing)

Table full — unacceptable

Common Hash Functions

Division Method

The simplest approach: divide the key by the table size and take the remainder.

h(k) = k mod m

Choose m to be a prime number not close to a power of 2. A prime table size distributes keys more evenly because it has no common factors with typical key patterns.

Division method

JS
function divisionHash(key, m) {
  return ((key % m) + m) % m;  // +m handles negative keys in JS
}

divisionHash(123, 97);  // 26  (97 is prime)
divisionHash(456, 97);  // 68
divisionHash(789, 97);  // 13

Multiplication Method

Multiply the key by a constant A (0 < A < 1), take the fractional part, then multiply by m:

h(k) = floor(m × (k × A mod 1))

Knuth recommends A ≈ 0.6180339887 (the golden ratio conjugate). Unlike the division method, m does not need to be prime, making it convenient when table size is a power of 2.

Multiplication method (Knuth)

JS
function multiplicationHash(key, m) {
  const A = 0.6180339887;  // (sqrt(5) - 1) / 2
  return Math.floor(m * ((key * A) % 1));
}

multiplicationHash(123, 1024);  // e.g. 611
multiplicationHash(124, 1024);  // e.g. 236  (very different — good spread)

Polynomial Rolling Hash for Strings

Strings require a hash function that treats the order of characters as significant. The polynomial rolling hash does exactly that:

h(s) = (s[0]×p^(n-1) + s[1]×p^(n-2) + … + s[n-1]×p^0) mod m

where p is a small prime (commonly 31 for lowercase letters, 53 for mixed case) and m is a large prime (e.g. 10^9 + 7). This function gives different hashes to anagrams like "abc" and "bca" because position matters.

Polynomial rolling hash

JS
function polyRollingHash(s, p = 31, m = 1_000_000_007) {
  let hash = 0n;
  let pPow = 1n;
  const P = BigInt(p);
  const M = BigInt(m);

  for (const ch of s) {
    const val = BigInt(ch.charCodeAt(0) - 'a'.charCodeAt(0) + 1);
    hash = (hash + val * pPow) % M;
    pPow = (pPow * P) % M;
  }
  return Number(hash);
}

polyRollingHash("abc");  // e.g. 1404
polyRollingHash("bca");  // e.g. 1426  (different — order matters)
polyRollingHash("abc");  // 1404 again — deterministic
Tip
Polynomial rolling hash is the foundation of the Rabin-Karp string search algorithm and is used widely in competitive programming for fast string comparison and substring matching.
Cryptographic vs Non-Cryptographic Hash Functions

Not all hash functions are created equal. They split into two broad categories:

Property

Cryptographic (SHA-256, SHA-3)

Non-Cryptographic (MurmurHash3, xxHash)

Primary goal

Security — hard to reverse or forge

Speed — fast lookup

Speed

Slower (100–500 MB/s)

Extremely fast (5–20 GB/s)

Collision resistance

Computationally infeasible to find

Best-effort, not guaranteed

Pre-image resistance

Cannot reverse hash to input

Not required

Typical output size

128–512 bits

32 or 64 bits

Used in

TLS, checksums, digital signatures

Hash tables, bloom filters, caches

Hash-flooding attacks

Immune (randomised output)

Vulnerable unless seed is secret

Warning
Never use a non-cryptographic hash function for security purposes (passwords, tokens, signatures). Never use a cryptographic hash function for a high-frequency hash table — the overhead is enormous. Choose the right tool for the job.
Hash vs BST: When to Use Each

The two dominant dictionary data structures are hash tables (average O(1)) and balanced BSTs like Red-Black trees (O(log n) guaranteed). Choosing between them depends on your requirements:

Criterion

Hash Table

Balanced BST (TreeMap/SortedMap)

Lookup / Insert / Delete

O(1) average

O(log n) guaranteed

Worst-case guarantee

O(n) without randomisation

O(log n) always

Key order preserved?

No (JS Map preserves insertion order)

Yes — sorted by key

Range queries (find all keys in [a, b])

Not supported

O(log n + k) efficient

Successor / predecessor queries

Not supported

O(log n)

Key type requirement

Must be hashable + equality-comparable

Must be comparable (has ordering)

Memory overhead

Lower (amortised)

Higher (tree nodes with pointers)

Cache performance

Better (flat array)

Worse (pointer chasing)

Use a hash table when:

  • You need fast average-case lookup (the common case).
  • Keys are unordered strings, numbers, or objects.
  • Frequency counting, membership testing, grouping by key.

Use a BST / sorted map when:

  • You need the smallest or largest key.
  • You need all keys in sorted order (iteration).
  • You need range queries: "give me all keys between X and Y."
  • You need a predictable worst-case (real-time systems).
Applications of Hashing

  • Hash tables — O(1) key-value lookup, the backbone of most language runtimes.

  • Caches (e.g. LRU) — hash table for O(1) access + linked list for eviction order.

  • Checksums and file integrity — SHA-256 of a file detects any modification.

  • Password storage — hash + salt before storing; never store plaintext passwords.

  • Bloom filters — probabilistic set membership using multiple hash functions.

  • Consistent hashing — distributing data across servers in distributed systems.

  • Rabin-Karp string search — rolling hash enables O(n+m) pattern matching.

  • Deduplication — hash a file/block to detect if it was seen before.

  • Frequency counting — count occurrences of items in a stream.

  • Grouping — group items by a computed key (e.g. anagram groups).

When Hashing Is the Right Tool

Reach for a hash table (or JavaScript's Map/Set) whenever your problem fits one of these patterns:

Lookup pattern — "Is X present?" or "What is the value for key X?" Constant-time membership test beats any sorted structure for this.

Frequency count — "How many times does each item appear?" Iterate once, increment a counter in the map. O(n) total.

Deduplication — "Remove all duplicates." Add each item to a Set; duplicates are silently ignored. O(n) time, O(n) space.

Grouping — "Partition items by some property." Use the property as the map key, accumulate items into an array value. Classic example: group anagrams.

Two-pointer complement trick — "Are there two items that sum to target?" Store each item in a Set/Map as you scan; check if the complement was seen.

The four core hashing patterns

JS
// 1. Lookup
const seen = new Set(["apple", "mango"]);
seen.has("apple");   // true  O(1)

// 2. Frequency count
function freq(arr) {
  const count = new Map();
  for (const x of arr) count.set(x, (count.get(x) ?? 0) + 1);
  return count;
}
freq([1, 2, 2, 3, 3, 3]);
// Map { 1 => 1, 2 => 2, 3 => 3 }

// 3. Deduplication
const unique = [...new Set([1, 2, 2, 3, 3])];
// [1, 2, 3]

// 4. Grouping
function groupBy(items, keyFn) {
  const map = new Map();
  for (const item of items) {
    const k = keyFn(item);
    if (!map.has(k)) map.set(k, []);
    map.get(k).push(item);
  }
  return map;
}
groupBy(["eat","tea","tan","ate","nat","bat"], s => [...s].sort().join(''));
// Map { 'aet' => ['eat','tea','ate'], 'ant' => ['tan','nat'], 'abt' => ['bat'] }
Note
All four patterns above run in O(n) time — a dramatic improvement over nested loops (O(n²)) or sorted structures (O(n log n)). Recognising which pattern applies is the core skill for solving hash table problems.