Feature Hashing (Hashing Trick)

Background

Feature hashing (the "hashing trick") encodes high-cardinality categorical features into a fixed-size dense vector without storing a vocabulary. Each category is hashed to one of $d$ buckets; collisions are accepted as the cost of constant memory. Used universally in CTR / ad-ranking pipelines where the feature dictionary doesn't fit in RAM.

Problem statement

Implement feature_hash(values, n_buckets, signed=True). For each input value, hash to a bucket index in $[0, d)$ and write its contribution. If signed=True, also hash to a sign $\in \{-1, +1\}$ to reduce collision bias.

$$v[\text{bucket}(c)] \mathrel{+}= \text{sign}(c)$$

Input

• values - sequence of hashable values.
• n_buckets - int >= 1, output dimensionality.
• signed - bool, default True.

Output

• np.ndarray of shape (n_buckets,), the hashed feature vector.

Examples

Input: values=["a","b","a","c"], n_buckets=8
Output: an 8-vector with entries +/-1 at the hashed positions, sum to 4 in absolute counts

Constraints

• Use hash(...) for bucket index. Modulo by n_buckets.
• For sign, use a second deterministic hash so the same input always produces the same sign within a run.

Notes

• Why signed. Without sign, two values that collide both add positively; with sign, half cancel out on average, so the collision noise is mean-zero.
• Privacy. Hashed features don't leak the original category name, useful in regulated industries.