Learn AI Create the Future — with Pranay
Main site

Preprocessing and Feature Selection

The hashing trick

The hashing trick turns words or categories into column numbers with a fixed formula instead of a stored dictionary, so memory stays constant no matter how many new values appear.

Read these first

On this page 5
  1. Why it exists
  2. How it works
  3. A real example you have seen
  4. Remember this
  5. What to learn next

One lesson, three depths. Pick the one that fits you today — you can switch any time.

Beginner — No maths. Plain English.

The hashing trick assigns every word or category to a numbered bucket using a fixed formula, instead of keeping a dictionary.

Think of a cloakroom at a huge wedding with exactly 1,000 hooks. The attendant never writes a guest's name in a register. Instead they use a rule: add up the letters of your name in a fixed way. The total picks your hook number. No register exists. Any guest — even one nobody expected — gets a hook instantly, by arithmetic alone.

Two guests can land on the same hook. The attendant accepts this. With enough hooks, it is rare, and the wedding never stops to expand the register.

Why it exists

The normal way to turn words into columns is a vocabulary: scan all the data, list every distinct word, give each its own column. That breaks in three common situations.

  1. The list never ends. User IDs, URLs, product codes, new slang — tomorrow always brings values you have never seen. A vocabulary built today is stale by tonight.
  2. The list is enormous. Millions of distinct values means millions of columns and a giant lookup table to store and ship.
  3. The data arrives as a stream. To build a vocabulary you must see all the data first. A live system never has "all" the data. This matters again in learning from data that does not fit in memory.

The hash function — the letter-adding rule — solves all three. It converts any value to a bucket number directly. No scan, no table, no memory growth, no "unknown word" panic.

How it works

"battery"  --hash-->  bucket 8      fixed 16 buckets,
"excellent"--hash-->  bucket 4      decided before seeing
"terrible" --hash-->  bucket 14     any data at all
"overnight"--hash-->  bucket 14     <- collision! shares a bucket

A row of text becomes counts per bucket: how many of its words landed in bucket 0, bucket 1, and so on. Collisions blur things a little — the model cannot tell "terrible" from "overnight" above. The trade is deliberate: a small, controllable amount of blur in exchange for constant memory forever.

A real example you have seen

Email spam filters run on exactly this. Spammers invent fresh nonsense words daily to dodge word lists. A hashed filter does not care: any word, however new, hashes straight into one of its fixed buckets and gets scored.

Remember this

  • A hash function turns any value into a bucket number by formula, with no stored list.
  • Memory is fixed up front and never grows, and unseen values need no special handling.
  • Collisions — two values sharing a bucket — are the price, kept small by using many buckets.

What to learn next

Developer — Code and libraries.

Setup

bash
pip install scikit-learn

Outputs verified with scikit-learn 1.7.2.

Sixteen buckets, on purpose too few

Real systems use hundreds of thousands of buckets. Sixteen makes collisions visible on one screen.

hashing.py
from sklearn.feature_extraction.text import HashingVectorizer

reviews = [
    "battery life is excellent",
    "battery drains overnight, terrible",
    "excellent camera, terrible battery",
]

# 16 buckets so collisions are visible; real use starts at 2**18
vec = HashingVectorizer(n_features=16, alternate_sign=False, norm=None)
X = vec.transform(reviews)

print("matrix shape:", X.shape)
print(X.toarray().astype(int))

words = ["battery", "life", "is", "excellent", "drains",
         "overnight", "terrible", "camera"]
for word in words:
    col = vec.transform([word]).nonzero()[1][0]
    print(f"{word!r:12} -> bucket {col}")
Output
matrix shape: (3, 16)
[[0 0 0 0 2 0 0 0 1 0 0 0 0 1 0 0]
 [0 0 0 1 0 0 0 0 1 0 0 0 0 0 2 0]
 [0 0 0 0 2 0 0 0 1 0 0 0 0 0 1 0]]
'battery'    -> bucket 8
'life'       -> bucket 4
'is'         -> bucket 13
'excellent'  -> bucket 4
'drains'     -> bucket 3
'overnight'  -> bucket 14
'terrible'   -> bucket 14
'camera'     -> bucket 4

The walkthrough

There was no fit. Only transform. That is the entire point: nothing is learned from the data, so there is no vocabulary to build, store, or keep in sync between training and production.

Find the collisions in the matrix. Bucket 4 holds "life", "excellent" and "camera" — three words the model can no longer tell apart. Row 1 shows a 2 in bucket 14 because "overnight" and "terrible" collided. With 16 buckets and 8 distinct words, collisions are guaranteed. At the realistic default of 2**20 buckets, they become rare.

alternate_sign=False makes the output plain counts, which is easiest to read. The default True gives half the words a negative sign, so colliding words tend to cancel instead of merging — an accuracy trick explained in the Researcher block. Keep the default in real use; it confuses first-time readers of the raw matrix, which is why it is off here.

The output is sparse. X is a sparse matrix: only non-zero entries are stored. A million buckets costs nothing per row beyond the handful of words actually present.

For dictionaries of categories rather than text, the same idea ships as FeatureHasher. HashingVectorizer is string-in, FeatureHasher is dict-in.

Common mistakes

Too few buckets. Collisions grow until unrelated features merge and accuracy sags. Symptoms look like mysterious underfitting. Start at 2**18 for text; going bigger is nearly free because the matrix is sparse.

Expecting to map columns back to words. Hashing is one-way. Bucket 4 does not know it holds "excellent". If you must explain the model's features to a human — regulators, doctors, your future self — use a fitted vectorizer with a vocabulary instead. This trade-off is permanent, not a setting.

Comparing vectors made with different n_features. The same word lands in different buckets under different bucket counts. Vectors from mismatched settings share no meaning. Pin n_features once per system and record it.

Reaching for hashing when the vocabulary is small and stable. For 30 known product categories, one-hot encoding is exact, interpretable and even cheaper. Hashing earns its place when values are unbounded, high-cardinality, or streaming.

Try it yourself

Set n_features=1024 and rerun. Check whether any of the eight words still collide. Then try n_features=4 and predict, before running, how many buckets end up shared.

What to learn next

Researcher — Mathematics and papers.

Formalisation

Feature hashing maps an input feature space (strings, arbitrary tokens) to R^m via a hash function h: tokens -> {0, ..., m-1} and a sign hash s: tokens -> {-1, +1}:

phi_i(x) = sum over tokens t in x with h(t) = i of s(t) * c(t, x)

Where m is the number of buckets, c(t, x) the count of token t in example x, and s the Rademacher sign that alternate_sign toggles. Weinberger et al. (2009), Feature hashing for large scale multitask learning, ICML, is the standard reference; sklearn implements signed 32-bit MurmurHash3.

Why the sign hash matters

With signs, the hashed inner product is an unbiased estimator of the original:

E[phi(x) . phi(y)] = x . y

Collisions contribute s(t1) * s(t2) cross-terms with zero mean, rather than always-positive mass. The variance of the estimate is O(||x||^2 ||y||^2 / m), so distortion shrinks as 1/m. Without signs, collisions bias inner products upward. This is a Johnson-Lindenstrauss-flavoured guarantee achieved with O(1) memory and no matrix — compare random projections, which buy tighter guarantees at the cost of storing the projection.

Collision accounting

With v distinct tokens hashed uniformly into m buckets, the expected number of colliding token pairs is roughly v(v-1)/(2m); the probability that a given token shares its bucket is about 1 - exp(-v/m). At v = 100,000 and m = 2^20, about 9% of tokens share a bucket with something — yet measured accuracy loss is typically negligible, because collisions act as random weight-tying, a mild regulariser. Empirical curves in Weinberger et al. show accuracy flat until m falls well below v.

Context and descendants

Vowpal Wabbit built its entire input format around hashing, enabling learning at rates of millions of features per second in the 2010s ad-click era. The idea reappears in deep learning as hash embeddings (Svenstrup et al., 2017): embedding tables indexed by multiple hashes with learned combination weights, cutting table memory for huge vocabularies. Modern subword tokenisation (tokenization) attacks the same unbounded-vocabulary problem from a different angle — a learned, reversible decomposition rather than an oblivious, irreversible one.

What to learn next