How does the hashing trick encode millions of ad publisher domains, and what do collisions cost?
answer
- no vocabulary table to store or refresh
- index equals hash value modulo bucket count
- memory fixed before you see the data
- two levels can share one slot
- a sign hash makes collisions cancel
basics
~20 sA hash function maps each domain to a bucket index modulo a fixed bucket count, say 2^20, and that bucket is the feature slot. Nothing is stored, so new domains need no special case. Colliding domains share one blended weight.
solid answer
~40 sFeature hashing fixes the output width in advance: hash the raw string, take the result modulo B buckets — 2^20 is a common choice for web-scale identifiers — and use that index as the feature position. The appeal is operational rather than statistical: there is no vocabulary table to build, store or keep in sync between training and serving, memory is bounded however many domains appear, and a first-seen domain needs no special case. The price is collisions: two distinct domains in one bucket become indistinguishable and share a blended weight. The damage stays small because collisions mostly pair rare domains with rare domains, and a signed variant — a second hash giving +1 or -1 — makes colliding contributions cancel in expectation. The real cost is interpretability, since the mapping is not invertible.
go deeper
Know the one-line mechanic: hash the category string, take it modulo a fixed number of buckets, use that as the feature slot. Know that two categories can land in the same bucket.
Explain why the fixed width is the point — bounded memory, no vocabulary to ship, unseen values handled for free — and describe what the model learns when two values collide.
Argue about the bucket count with numbers, discuss why collisions between tail values are cheap, and be honest about the debugging and explainability cost in a live scoring path.
Own the choice between a stateless transform and a stateful learned mapping across the platform, weighing serving simplicity and unbounded level growth against interpretability obligations and the signal a supervised encoding would have added.
## The mechanism Feature hashing, or the hashing trick, replaces the usual "build a dictionary of levels, assign each an index" step with a function. Choose a number of buckets `B`, usually a power of two so the modulo is a bit mask. For a category value `v`, compute `index = hash(v) mod B` and treat that index as the feature slot: either a sparse indicator set at that position, or a bucket id fed to a model that handles categorical splits. Interaction features are hashed the same way — hash the concatenation of publisher domain and ad slot to get a crossed feature without ever enumerating the crosses. `B` is a modelling decision made up front. At `B = 2^20` there are 1,048,576 slots, which for a linear model means about a million weights — a few megabytes, fixed forever, regardless of how many domains the internet produces. ## Why anyone accepts collisions Everything attractive here is operational: - **No vocabulary.** A learned level-to-index mapping is state: it has to be built from training data, stored, shipped with the model, refreshed, and kept identical between the training job and the serving path. A hash function is code. There is nothing to drift. - **Bounded memory.** The parameter count is chosen, not discovered. A column that grows from 200,000 to 2,000,000 domains costs nothing extra. - **Streaming and unseen levels.** A brand-new domain hashes to a valid bucket on its first request. There is no unknown-level branch, which matters when the level set genuinely never stops growing. - **One pass.** The encoding can be computed row by row without a prior scan of the data to collect levels. ## What a collision actually does Two distinct domains landing in the same bucket become the same feature to the model, which then learns a single weight representing their blended effect. How often does it happen? With `n` distinct values in `B` buckets, the expected fraction of values sharing a bucket with at least one other is roughly `1 - exp(-n/B)`. With 200,000 domains in 2^20 buckets that is about 17% — not rare at all. It hurts less than that number suggests, for two reasons. First, the distribution of traffic is extremely skewed: the few hundred domains carrying most impressions are unlikely to collide with each other, and when a head domain collides it is almost always with a long-tail domain contributing a handful of rows, which barely perturbs the learned weight. Second, the **signed** variant uses a second hash to multiply each contribution by +1 or -1 before accumulating. Colliding contributions then cancel in expectation instead of summing, so the inner products the model sees are unbiased estimates of the uncollided ones, with variance that shrinks as `B` grows. If collisions do bite, the lever is `B`. Doubling the buckets roughly halves the collision rate, at linear cost in memory. Treat `B` as a hyperparameter and sweep it: the validation curve usually flattens well before memory becomes the constraint. ## What you give up - **Interpretability.** The map is one-way. Bucket 774,113 has a weight, and recovering which domains feed it requires hashing the whole known level set and looking for matches. For a model that must be explained to a risk or compliance function, that is a serious drawback. - **Debuggability.** "Why did this request score high?" is harder to answer when the features are anonymous indices. - **No supervision.** Hashing carries no information about the target; it only preserves identity. A hashed bucket for a domain with three impressions tells the model nothing that a count or a smoothed target mean would. ## Where it fits against the alternatives Hashing is the right default when the level set is unbounded or streaming, when serving cannot afford stateful mapping tables, and when the model is a wide linear or factorisation-style model that thrives on millions of sparse features. It is the wrong default for a modest tabular problem with a few thousand levels and a gradient-boosted model, where a compact supervised encoding gives more signal per column and stays readable. The two are also composable: hash the raw identifier for the sparse part of the model, and separately feed a smoothed target mean or a count for the head of the distribution. Nothing forces one encoding per column.
- How would you choose the number of buckets in practice?Treat it as a hyperparameter over a log-spaced sweep of powers of two, bounded above by the memory the serving path allows. Use the expected collision rate, roughly one minus exp of minus levels over buckets, to pick the starting range, then let validation score decide where the curve flattens.
- Why does the signed variant of feature hashing reduce collision damage?A second hash assigns each raw value a sign of plus or minus one before its contribution is accumulated into the bucket. Two colliding values then contribute with the same sign only half the time, so their interference has mean zero rather than always adding, and the resulting feature values are unbiased.
- When would you not reach for hashing on a high-cardinality column?When the model must be explainable, since the mapping is not invertible; when the level set is small and stable enough to store; and when the level's relationship to the target is the signal you want, because hashing preserves identity only and adds no supervised information.
Assigning conference attendees to rooms by a rule on their name instead of a guest list. Nobody maintains the list and latecomers are handled instantly, but two strangers occasionally get the same room.
saying these in an interview costs you the question
- Claims hashing avoids collisions if the hash is good
- Thinks the hashed feature carries target information
- Cannot say what happens when two levels share a bucket
- Believes bucket weights can be read back as levels
- Picks the bucket count with no memory or validation reasoning