Feature hashing (the hashing trick)

Deep dive

How it works

In: feature names (each with a namespace), a seed, and b · Out: a sparse vector of at most k nonzeros in 2^b dimensions · State: none (seed and b are configuration, and must be versioned with the model) · Cost: O(k) hashes plus a merge of the k indices

1. Name each feature with its namespace: u:cat (unigram), b:the\x1fcat (bigram). A feature cross is one concatenated name, country=DE|device=ios.
2. Compute one seeded 64-bit hash h of the name.
3. Index i = h & (2^b - 1) (a mask, since the size is a power of two); sign s = ±1 from the top bit of h (Weinberger et al. use a second hash function; one well-mixed hash gives both).
4. Add s · value into slot i. Colliding features add, and random signs cancel in expectation: E[⟨φ(x), φ(y)⟩] = ⟨x, y⟩.
5. Keep it sparse: sort by index and merge, or scatter into a dense array when 2^b is small.
6. The learner treats slot i as column i; a deep model treats it as a row of an embedding table.

Collision arithmetic: n distinct features in m buckets occupy m(1 - (1 - 1/m)^n) buckets on average, so the fraction landing in an already used bucket is 1 - (m/n)(1 - (1 - 1/m)^n): about n/(2m) for n much less than m, 1/e (37 %) for n = m. The first collision comes after about sqrt(πm/2) features (1,283 for m = 2^20). This is arithmetic, not model quality: collisions between rare features cost little, between two strong ones a lot.

Code

Std-only Rust: seeded FNV-1a plus the splitmix64 finaliser, signed unigram and bigram features, a sorted sparse vector, three tests.

/// Seeded 64-bit hash: FNV-1a over the bytes, then the splitmix64 finaliser
/// (FNV-1a alone has weak low bits; the finaliser mixes every output bit).
pub fn hash64(seed: u64, bytes: &[u8]) -> u64 {
    let mut h = 0xcbf29ce484222325 ^ seed.wrapping_mul(0x9e3779b97f4a7c15);
    for &b in bytes {
        h = (h ^ b as u64).wrapping_mul(0x100000001b3);
    }
    h ^= h >> 30; h = h.wrapping_mul(0xbf58476d1ce4e5b9);
    h ^= h >> 27; h = h.wrapping_mul(0x94d049bb133111eb);
    h ^ (h >> 31)
}

/// Sparse vector: (bucket, value) pairs sorted by bucket.
pub type Sparse = Vec<(u32, f32)>;

/// Namespace byte + name -> (index = low `bits` bits, sign = top bit).
fn slot(seed: u64, ns: u8, name: &[u8], bits: u32, signed: bool) -> (u32, f32) {
    let h = hash64(seed, &[&[ns], name].concat());
    let sign = if signed && h >> 63 == 1 { -1.0 } else { 1.0 };
    ((h & ((1u64 << bits) - 1)) as u32, sign)
}

/// Unigrams ("u") and bigrams ("b") of whitespace tokens into 2^bits buckets.
pub fn featurize(text: &str, seed: u64, bits: u32, signed: bool) -> Sparse {
    let toks: Vec<&str> = text.split_whitespace().collect();
    let mut raw: Sparse = toks.iter().map(|t| slot(seed, b'u', t.as_bytes(), bits, signed)).collect();
    for w in toks.windows(2) { // 0x1f separator: "a b"+"c" must differ from "a"+"b c"
        raw.push(slot(seed, b'b', &[w[0].as_bytes(), b"\x1f", w[1].as_bytes()].concat(), bits, signed));
    }
    raw.sort_by_key(|&(i, _)| i);
    let mut out: Sparse = Vec::with_capacity(raw.len());
    for (i, v) in raw {
        match out.last_mut() {
            Some(l) if l.0 == i => l.1 += v, // collision: values add, signs may cancel
            _ => out.push((i, v)),
        }
    }
    out
}

pub fn dot(a: &Sparse, b: &Sparse) -> f32 { // merge join over sorted indices
    let (mut i, mut j, mut s) = (0, 0, 0.0);
    while i < a.len() && j < b.len() {
        if a[i].0 == b[j].0 { s += a[i].1 * b[j].1; i += 1; j += 1; }
        else if a[i].0 < b[j].0 { i += 1 } else { j += 1 }
    }
    s
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::collections::HashSet;
    fn doc(seed: u64, n: usize, vocab: u64) -> String { // LCG words
        let mut x = seed;
        (0..n).map(|_| { x = x.wrapping_mul(6364136223846793005).wrapping_add(1442695040888963407);
                         format!("w{}", (x >> 33) % vocab) }).collect::<Vec<_>>().join(" ")
    }
    #[test]
    fn same_token_same_index() { // golden value: if it changes, trained weights no longer match serving
        assert_eq!(hash64(0, b"hello"), 0x16fe05a1c75bcd0f);
        assert_eq!(featurize("a b c", 1, 10, true), featurize("a b c", 1, 10, true));
    }
    #[test]
    fn collision_fraction_matches_arithmetic() {
        let (n, m) = (50_000usize, 1usize << 16);
        let used: HashSet<u64> = (0..n).map(|i| hash64(3, format!("tok{i}").as_bytes()) & (m as u64 - 1)).collect();
        let measured = 1.0 - used.len() as f64 / n as f64; // tokens landing in an already-used bucket
        // expected occupied buckets = m(1-(1-1/m)^n), so fraction = 1 - (m/n)(1-(1-1/m)^n)
        let expected = 1.0 - (m as f64 / n as f64) * (1.0 - (n as f64 * (-1.0 / m as f64).ln_1p()).exp());
        assert!((measured - expected).abs() < 0.01, "{measured} vs {expected}"); // 0.2977 vs 0.3005
    }
    #[test]
    fn signed_dot_is_unbiased() {
        let (a, b) = (doc(1, 400, 300), format!("{} {}", doc(1, 200, 300), doc(2, 200, 300)));
        let exact = dot(&featurize(&a, 0, 24, false), &featurize(&b, 0, 24, false)); // 2^24: almost no collisions
        let mean = |signed| (0..2000u64).map(|s| dot(&featurize(&a, s, 8, signed), &featurize(&b, s, 8, signed)) as f64)
            .sum::<f64>() / 2000.0; // 256 buckets: heavy collisions, averaged over 2000 seeds
        assert!((mean(true) - exact as f64).abs() < 0.03 * exact as f64); // 875.6 vs 884
        assert!(mean(false) > 1.5 * exact as f64); // 3370: all-positive collisions inflate it
    }
}

Compiled and run with cargo test --release: 3 tests pass; the comments hold the measured values. The unsigned bias matches the arithmetic (Σx · Σy - x·y) / m ≈ (800·800 - 884)/256 ≈ 2,480 above the exact 884.

Complexity and constants

• Time O(k) for k features, plus O(k log k) for the sort (use a dense scatter when 2^b is small).
• Memory: 4 · 2^b bytes of weights: b = 20 is 4 MiB, b = 24 is 64 MiB (arithmetic); a deep model's table is 2^b · d values per field.
• Variance of a hashed inner product falls as 1/m; each extra bit halves the collision rate.

Efficiency

• Cost: measured on one core of an Apple M4 Pro, release build: featurize on 100,000 tokens from a 50,000-word vocabulary (199,999 features), 2^20 buckets, signed: about 9 M tokens/s (18 M features/s, order of 55 ns per feature) including allocation, sort and merge. hash64 alone on a 10-byte key: about 2 ns per call in a loop of independent calls (throughput, not latency). Weights take 4 · 2^b bytes. Bound: allocation and the sort, then memory traffic on the weights; the hash is not the bottleneck.
• Levers:
  • hash namespace byte and name incrementally instead of concatenating — removes one allocation per feature (not measured) — hot loops
  • dense scatter into a 2^b array instead of sort and merge — O(k) instead of O(k log k) — 2^b small or k large
  • precompute hashed ids of repeated tokens and n-grams — rehash once, not every epoch (order of) — multi-epoch training
  • raise b — collision rate halves per bit (arithmetic above) — memory allows
• Naive → standard → state of the art:
  • dictionary built in a full pass, shared by every worker · memory grows with the vocabulary, rebuild for new tokens
  • signed hashing to 2^18-2^22 buckets with a fixed seed · constant memory, one streaming pass
  • several hashes or compositional (quotient and remainder) tables in deep models · fewer collisions at the same table size; Shi et al. report lower loss than the plain hashing trick

Implementation notes

• Use a mask (& (2^b - 1)) and a power-of-two m; Spark's docs warn that other sizes map features unevenly.
• Hash bytes with a documented function (MurmurHash3, xxHash, FarmHash, SipHash with a fixed key), identical in every language in the pipeline.
• Version the seed, b, namespace rules and hash together with the model; changing any one silently moves every weight.
• Reserve a slot for the bias (VW adds a constant feature) so it does not collide with data.
• Hash feature crosses as one concatenated name with an unambiguous separator; combining two hashes with + or XOR loses order.
• To debug, keep a sample dictionary slot -> names and reverse-map the largest weights (VW has --invert_hash).

Pitfalls

• Train/serve mismatch. Python's hash() of a string is randomised per process, Java's hashCode is not MurmurHash, and Rust's DefaultHasher does not promise stability across releases. Training works, serving returns noise. Pin a golden value, as in the code.
• No inverse. A slot holds a sum of features; explanations and audits by name need a side dictionary.
• Not private. The hash is deterministic and cheap: anyone with a candidate list recovers which tokens are present. Collisions do not anonymise. A salt (TensorFlow's Hashing layer uses SipHash64 with salt) only helps against someone without the key.
• Frequent features colliding. Two strong features in one slot hurt more than the average rate says; sweep b.
• Unsigned hashing. Collisions then bias inner products upward (3.8 times the exact value in the test).

Variants and alternatives

In production

Vowpal Wabbit hashes feature names with MurmurHash3 into -b bits (default 18). scikit-learn HashingVectorizer and FeatureHasher use signed 32-bit MurmurHash3, 2^20 columns by default, alternate_sign=True. Spark ML has HashingTF (2^18 default) and FeatureHasher; Keras has a Hashing layer (FarmHash64).

Fields: text and spam classification (Weinberger et al. hash a multitask problem with hundreds of thousands of tasks into one space); ads and recommendation models with hashed-id embedding tables (deep recommendation models, CTR prediction); online learners such as FTRL; byte n-grams and log tokens in security and fraud pipelines (common practice, no single source); genomics k-mers (4^12 is 16.8 M).

Implementations

Sources

• Kilian Weinberger, Anirban Dasgupta, Josh Attenberg, John Langford, Alex Smola, Feature Hashing for Large Scale Multitask Learning, ICML 2009. paper
• Qinfeng Shi, James Petterson, Gideon Dror, John Langford, Alex Smola, S.V.N. Vishwanathan, Hash Kernels for Structured Data, JMLR 10:2615-2637, 2009. paper
• Dan Svenstrup, Jonas Meinertz Hansen, Ole Winther, Hash Embeddings for Efficient Word Representations, NeurIPS 2017. paper
• Hao-Jun Michael Shi, Dheevatsa Mudigere, Maxim Naumov, Jiyan Yang, Compositional Embeddings Using Complementary Partitions for Memory-Efficient Recommendation Systems, KDD 2020. paper
• scikit-learn docs: FeatureHasher, HashingVectorizer
• Vowpal Wabbit, Feature Hashing and Extraction (wiki)
• Apache Spark, ML features: HashingTF and FeatureHasher
• TensorFlow, tf.keras.layers.Hashing