Feature Hashing

Unlike one-hot encoding, feature hashing does not require a pre-built vocabulary or dictionary mapping string values to indices. The hash function computes the index directly from the raw feature value. This eliminates the memory overhead of storing a vocabulary and the engineering complexity of handling out-of-vocabulary (OOV) inputs during inference. Any new categorical value encountered in production is immediately mapped to a bucket without model updates.

The output dimensionality is fixed and user-defined by specifying the number of hash buckets (e.g., 2^18). The hash function maps an input to an integer, and the modulo operation (hash(x) % D) constrains it to the pre-allocated vector size. This guarantees a strict, predictable memory budget regardless of the cardinality of the input feature, making it ideal for streaming and online learning environments where feature cardinality is unbounded.

Multiple distinct input features can map to the same hash bucket, creating a collision. This is the primary trade-off of feature hashing. The signed hash trick mitigates this by using a second hash function to determine the sign (+1 or -1) of the feature value, allowing collisions to partially cancel out in linear models. While collisions introduce noise, the impact is often negligible in high-dimensional settings with sparse features.

The transformation is stateless—each feature is hashed independently without requiring global aggregation or coordination. This makes feature hashing embarrassingly parallelizable across distributed computing frameworks like Apache Spark. There is no need to synchronize a shared vocabulary across worker nodes, significantly simplifying distributed feature engineering pipelines.

The MurmurHash3 algorithm is the most widely used non-cryptographic hash function for feature hashing due to its excellent distribution properties and speed. In practice, many implementations use a 32-bit or 64-bit variant. The signed hash trick often employs a second hash function, such as the Jenkins hash, to determine the sign bit, ensuring that collisions are not purely additive.

Feature hashing is a cornerstone of the Vowpal Wabbit online learning system and is widely used in:

• Text classification: Hashing n-gram features to avoid storing a massive term dictionary.
• Ad click prediction: Handling high-cardinality categorical features like ad IDs and user agents.
• Email spam filtering: Efficiently representing tokenized email content in a fixed-size feature space.

The process of projecting high-dimensional data into a lower-dimensional space. Feature hashing is a stateless dimensionality reduction technique specifically for categorical variables, contrasting with data-driven methods like PCA or t-SNE which require learning a projection matrix from data. Hashing achieves reduction without any training phase, making it ideal for streaming contexts where the full feature vocabulary is unknown upfront.

A parameter matrix storing dense vectors for each categorical feature value, enabling GPU-accelerated lookup. Feature hashing eliminates the need for an explicit embedding table by using a hash function to directly index into a fixed-size vector, avoiding the memory overhead of storing a vocabulary-to-index mapping. This is critical when dealing with high-cardinality features like user IDs or search queries where a full table would exceed memory budgets.

A representation strategy for new entities with no historical data. Feature hashing naturally handles the cold-start problem for categorical features because the hash function can map any unseen string to a valid index without retraining. Unlike one-hot encoding, which fails on out-of-vocabulary values, hashing gracefully assigns new categories to existing slots, accepting potential collisions as a trade-off for universal coverage.

Event-driven architectures for ingesting real-time data. Feature hashing is a cornerstone of online feature engineering in streaming pipelines because it requires no vocabulary pre-computation or state maintenance. As raw events arrive, categorical fields can be immediately hashed into fixed-size vectors without consulting a feature store, enabling sub-millisecond transformation in Apache Kafka or Apache Flink workflows.

An efficient training approximation that updates only a small subset of negative examples. In recommendation systems using feature hashing, the hash collision property can inadvertently create shared representations between distinct items, acting as a form of implicit regularization. When combined with in-batch negative sampling, the collision-induced noise can improve generalization by preventing the model from memorizing rare feature combinations.

A vector compression technique that decomposes embedding space into quantized subspaces. While feature hashing reduces dimensionality at the input feature level, PQ operates at the learned representation level, compressing dense embeddings for efficient ANN retrieval. A complete pipeline often uses hashing to bound input feature size, then applies PQ to the resulting user or item embeddings for billion-scale similarity search.