Hashing and High Cardinality

September 2026 · 12 min read

A merchant-ID feature may contain millions of distinct names. Sparse one-hot encoding can avoid a huge dense input matrix, but it still needs a vocabulary and a model coordinate for each retained name. Feature hashing chooses a fixed number of output columns and maps names directly into those columns.

The same name always reaches the same column under the same hash settings. A new name can be encoded immediately. The tradeoff is that different names can share a column, creating a collision.

A hash selects a bucket, not a numerical category value

Think of the output columns as numbered buckets. A deterministic hash turns a feature name into an integer; the encoder uses it to select one of the buckets. For a present feature with value 1, it adds a contribution to that bucket. It does not hand the large hash integer to the model as a scalar feature.

One example below contains two tags, a channel, and a region. With four buckets, channel=web and region=west both land in bucket 2. Unsigned hashing adds 1 + 1 there. Signed hashing assigns each name a fixed +1 or −1 sign; these two contributions become +1 − 1 = 0.

Collisions are added, not overwritten

Let $x_i$ be the value of original feature $i$, $h(i)$ its bucket index, and $s(i)$ its fixed sign. The output value $x'_j$ in bucket $j$ is the sum of all contributions assigned there:

Unsigned hashing uses +1 for every sign. In the figure all original values are 1, but a numeric input can contribute another finite value. Repeated occurrences also add: the same tag listed twice contributes twice unless you deduplicate it before hashing.

The zero in bucket 2 under signed hashing does not mean no original features were present. Two contributions canceled. Hashing does not retain the information needed to reverse that operation.

Why use signs if they can cancel real features?

With unsigned hashing, a collision between unrelated positive features adds a positive term to their dot product. Random signs make collision terms sometimes positive and sometimes negative. Under the hash-family assumptions in the feature-hashing paper, the extra terms cancel in expectation, preserving the original dot product on average.

That expectation is over the choice of hashes. For a deployed model, each name’s bucket and sign stay fixed. A particular collision can still hurt, and signed hashing does not recover the identities of colliding names.

Include the field name in what you hash

A country field and a merchant field might both contain the string “US.” Hashing only the value makes them exactly the same input feature. Build names from both the field and its value, with unambiguous escaping or serialization when values can contain separators.

Fix string normalization, character encoding, hash algorithm, sign rule, and output width across training and serving. Python’s built-in string hash() is salted across processes by default, so it is not a substitute for a specified stable feature hash. Scikit-learn uses MurmurHash3 and converts Unicode strings to UTF-8; it does not normalize visually equivalent Unicode spellings for you.

Python: sparse features without a learned vocabulary

FeatureHasher is stateless: fitting validates parameters rather than learning names from the data. With input_type="string", supply a collection of feature names for each row, not one unwrapped string per row.

from sklearn.feature_extraction import FeatureHasher

# One outer item per example; each inner item is one active feature name.
rows = [["tag=red", "tag=blue", "channel=web", "region=west"]]
hasher = FeatureHasher(n_features=4, input_type="string", alternate_sign=True)
encoded = hasher.fit_transform(rows)
print(encoded.toarray())  # Dense display only for this tiny example.
assert encoded.toarray().tolist() == [[1.0, 0.0, 0.0, -1.0]]

# No vocabulary update is needed to transform a new name.
new = hasher.transform([["tag=new"]])
assert new.shape == (1, 4)
assert new.toarray().tolist() == [[-1.0, 0.0, 0.0, 0.0]]

[[ 1.  0.  0. -1.]]

The new name tag=new maps to bucket 0 with sign −1. It has a valid representation, but the model has never learned an effect specifically for that name. Its prediction uses the coefficient already attached to that bucket.

Keep the result sparse in a large application. If the downstream estimator requires nonnegative inputs, such as multinomial naive Bayes, signed hashing is unsuitable; unsigned hashing is an option when the original values are nonnegative.

Choose the width by the memory and accuracy tradeoff

A wider output usually reduces collisions but enlarges the model’s coefficient array. One linear score with $2^{20}$ float32 coefficients needs about 4 MiB just for those coefficients. Multiple classes and optimizer state add storage. Sparse rows save input memory without removing the model’s width cost.

Compare several widths on the same held-out task and inspect rare and unseen categories. Hashing needs no fitted vocabulary, but choosing its width, feature construction, and model still requires validation. Other learned preprocessing steps must stay inside the training boundary.

Use hashing when bounded vocabulary storage and easy processing of new names matter. Use rare grouping or a retained vocabulary when named effects and inspectability matter more. Hashing is not anonymization: someone who knows the hash can test candidate names, and collisions are not a privacy mechanism.

C++: trace the collision-aggregation step

This example starts with the bucket and sign assignments from the figure and implements the sum. It isolates the part where overwriting a bucket would silently lose contributions. It does not reimplement MurmurHash3; production code must use the same specified hash as training. The dense vector is only for this four-column illustration.

#include <cmath>
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <vector>

struct HashedFeature {
    std::size_t bucket;
    int sign;
    double value;
};

// Column and sign have already been computed by the chosen hash function.
std::vector<double> aggregate(std::size_t width,
                              const std::vector<HashedFeature>& features,
                              bool signed_hashing) {
    if (!width) throw std::invalid_argument("width must be positive");
    std::vector<double> row(width, 0.0);
    for (const auto& feature : features) {
        if (feature.bucket >= width ||
            (feature.sign != 1 && feature.sign != -1) ||
            !std::isfinite(feature.value))
            throw std::invalid_argument("invalid hashed feature");
        row[feature.bucket] += feature.value * (signed_hashing ? feature.sign : 1);
    }
    return row;
}

int main() {
    // The four names in the figure, hashed into four buckets.
    const std::vector<HashedFeature> features = {
        {0, +1, 1}, {3, -1, 1}, {2, +1, 1}, {2, -1, 1}
    };
    for (bool use_sign : {false, true}) {
        std::cout << (use_sign ? "signed:" : "unsigned:");
        for (double value : aggregate(4, features, use_sign))
            std::cout << " " << value;
        std::cout << "\n";
    }
}

unsigned: 1 0 2 1
signed: 1 0 0 -1

References and further reading

• Scikit-learn: FeatureHasher — input formats, stable hashing behavior, fixed width, and sparse output.
• Scikit-learn: feature hashing guide — signed collisions, repeated-feature aggregation, and implementation details.
• Weinberger et al.: Feature Hashing for Large Scale Multitask Learning — the random-hashing analysis behind inner-product preservation.
• Python: object.__hash__ — why built-in string hashes are not a stable cross-process feature specification.