# Fully Understanding the Hashing Trick

arXiv: https://arxiv.org/abs/1805.08539 · HTML: https://mlsanity.com/paper/1805.08539/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 May 2018.

## Built on by (most cited first, 11 of 11)

- [Unified Embedding: Battle-Tested Feature Representations for Web-Scale ML Systems](https://mlsanity.com/paper/2305.12102/) (2023)
- [An Introduction to Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/2103.00564/) (2021)
- [The Fast Johnson-Lindenstrauss Transform is Even Faster](https://mlsanity.com/paper/2204.01800/) (2022)
- [Hashing embeddings of optimal dimension, with applications to linear least squares](https://mlsanity.com/paper/2105.11815/) (2021)
- [Machine Learning for Detecting Malware in PE Files](https://mlsanity.com/paper/2212.13988/) (2022)
- [Robust and Provable Guarantees for Sparse Random Embeddings](https://mlsanity.com/paper/2202.10815/) (2022)
- [Sparse Dimensionality Reduction Revisited](https://mlsanity.com/paper/2302.06165/) (2023)
- [Johnson-Lindenstrauss embeddings for noisy vectors -- taking advantage of the noise](https://mlsanity.com/paper/2209.01006/) (2022)
- [Node Similarities under Random Projections: Limits and Pathological Cases](https://mlsanity.com/paper/2404.10148/) (2024)
- [DCN^2: Interplay of Implicit Collision Weights and Explicit Cross Layers for Large-Scale Recommendation](https://mlsanity.com/paper/2506.21624/) (2025)
- [SHA-256 Infused Embedding-Driven Generative Modeling of High-Energy Molecules in Low-Data Regimes](https://mlsanity.com/paper/2510.25788/) (2025)

## Abstract (arXiv)

Feature hashing, also known as em the hashing trick, introduced by Weinberger et al. (2009), is one of the key techniques used in scaling-up machine learning algorithms. Loosely speaking, feature hashing uses a random sparse projection matrix A : ℝn → ℝm (where m ll n) in order to reduce the dimension of the data from n to m while approximately preserving the Euclidean norm. Every column of A contains exactly one non-zero entry, equals to either -1 or 1. Weinberger et al. showed tail bounds on |Ax|22. Specifically they showed that for every varepsilon, δ, if |x|∞ / |x|2 is sufficiently small, and m is sufficiently large, then Pr[ ; | ;|Ax|22 - |x|22; | < varepsilon |x|22 ;] ≥ 1 - δ ;. These bounds were later extended by Dasgupta etal (2010) and most recently refined by Dahlgaard et al. (2017), however, the true nature of the performance of this key technique, and specifically the correct tradeoff between the pivotal parameters |x|∞ / |x|2, m, varepsilon, δ remained an open question. We settle this question by giving tight asymptotic bounds on the exact tradeoff between the central parameters, thus providing a complete understanding of the performance of feature hashing. We complement the asymptotic bound with empirical data, which shows that the constants "hiding" in the asymptotic notation are, in fact, very close to 1, thus further illustrating the tightness of the presented bounds in practice.