A Note on Second-Order Expected Maximum-Load Bounds for Binary Linear Hashing

Nader H. Bshouty · 2026

Read A Note on Second-Order Expected Maximum-Load Bounds for Binary Linear Hashing by Nader H. Bshouty (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-18335.txt.

Introduction

Nader Bshouty sharpens, in a 2026 note, bounds on the heaviest-loaded bucket when a random linear hash map throws keys into bins. Refining the exponential-potential argument behind a 2025 result, he shows binary linear hashing nearly matches fully independent hashing at second order, not just in the leading term. A separate argument gives a tight tail bound for a single fixed bucket, with a subspace construction showing the bound cannot be improved asymptotically.

Catalog record

CREATORNader H. Bshouty
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62492
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.18335

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Note on Second-Order Expected Maximum-Load Bounds for Binary Linear Hashing Nader H. Bshouty Abstract Let S ⊆ 𝔽 2 u S\subseteq\mathbb{F}_{2}^{u} have size n = 2 ℓ n=2^{\ell} , and let h : 𝔽 2 u → 𝔽 2 ℓ h:\mathbb{F}_{2}^{u}\to\mathbb{F}_{2}^{\ell} be a uniformly random linear map. For y ∈ 𝔽 2 ℓ y\in\mathbb{F}_{2}^{\ell} , write load h ⁡ ( y ) := | h − 1 ​ ( y ) ∩ S | \operatorname{load}_{h}(y):=|h^{-1}(y)\cap S| , and let 𝖬 ⁡ ( S , h ) := max y ∈ 𝔽 2 ℓ ⁡ load h ⁡ ( y ) \mathsf{M}(S,h):=\max_{y\in\mathbb{F}_{2}^{\ell}}\operatorname{load}_{h}(y) be the maximum load. Jaber, Kumar and Zuckerman (STOC 2025) proved that the expected maximum load of h h on S S is at most 16 ​ log ⁡ n / log ⁡ log ​ n 16\log n/\log\log n , matching the fully independent keys-into-bins scale up to constants. Their proof also gives the tail estimate Pr [ 𝖬 ( S , h ) ≥ R log ⁡ n log ⁡ log ⁡ n ] ≤ O ( 1 R 2 ) . \Pr\left[\mathsf{M}(S,h)\geq R\frac{\log n}{\log\log n}\right]\leq O\left(\frac{1}{R^{2}}\right). We record a base optimization in their exponential-potential method showing that binary linear hashing nearly matches fully independent hashing also at the level of the second-order maximum-load scale. For every R > 1 R>1 satisfying R ​ ℓ 1 − 1 / R ≥ D ​ ln ⁡ ℓ R\ell^{1-1/R}\geq D\ln\ell , where D D is an absolute constant, we prove Pr [ 𝖬 ( S , h ) ≥ R log ⁡ n log ⁡ log ⁡ n ] ≤ O ( ( log ⁡ log ⁡ n ) 2 R 2 ​ ( log ⁡ n ) 2 − 2 / R ) . \Pr\left[\mathsf{M}(S,h)\geq R\frac{\log n}{\log\log n}\right]\leq O\left(\frac{(\log\log n)^{2}}{R^{2}(\log n)^{2-2/R}}\right). Integrating this tail yields 𝔼 ⁡ [ 𝖬 ⁡ ( S , h ) ] ≤ ( 1 + ( 1 + o ⁡ ( 1 ) ) ​ log ⁡ log ⁡ log ⁡ n log ⁡ log ⁡ n ) ​ log ⁡ n log ⁡ log ⁡ n . \mathbb{E}[\mathsf{M}(S,h)]\leq\left(1+(1+o(1))\frac{\log\log\log n}{\log\log n}\right)\frac{\log n}{\log\log n}. Thus binary linear hashing matches fully independent hashing in the leading term and matches the dominant second-order correction up to a 1 + o ⁡ ( 1 ) 1+o(1) factor. We also prove, by an independent self-contained argument, a sharp tail bound for one prescribed bucket: for fixed y ∈ 𝔽 2 ℓ y\in\mathbb{F}_{2}^{\ell} , Pr [ load h ( y ) > 2 a − 2 ] ≤ γ − 1 2 − a 2 , \Pr[\operatorname{load}_{h}(y)>2^{a}-2]\leq\gamma^{-1}2^{-a^{2}}, where γ = ∏ j ≥ 1 ( 1 − 2 − j ) \gamma=\prod_{j\geq 1}(1-2^{-j}) . A subspace construction shows that this is asymptotically tight even in the leading constant as a → ∞ a\to\infty . However, this controls only a fixed bucket; a direct union bound over all buckets loses a factor 2 ℓ 2^{\ell} . 1 Introduction Hashing is often used to distribute a set of keys among bins. If the hash function maps many keys to the same bin, then operations such as lookup with chaining may take a long time. Thus a central quantity is the maximum load, the largest number of keys mapped to any single bin. In this note we study this question for binary linear hashing. Let u\geq\ell , let h:\mathbb{F}_{2}^{u}\to\mathbb{F}_{2}^{\ell} be a uniformly random linear map, and let S\subseteq\mathbb{F}_{2}^{u} have size n=2^{\ell} . For y\in\mathbb{F}_{2}^{\ell} , define \operatorname{load}_{h}(y):=|h^{-1}(y)\cap S|, and define the maximum load \mathsf{M}(S,h):=\max_{y\in\mathbb{F}_{2}^{\ell}}\operatorname{load}_{h}(y). Throughout this paper, all logarithms are base 2 . We call the elements of S keys and the elements of \mathbb{F}_{2}^{\ell} bins . For y\in\mathbb{F}_{2}^{\ell} , the bucket at y is the set h^{-1}(y)\cap S . For fully independent hashing of n keys into n bins, the expected maximum load is (1+o(1))\frac{\log n}{\log\log n}. More precisely, the classical second-order asymptotic is \mathbb{E}[M_{n}]=\frac{\log n}{\log\log n}+(1+o(1))\frac{\log n\cdot\log\log\log n}{(\log\log n)^{2}}. A uniformly random linear map is much simpler than a fully random function, but it is only pairwise independent. Therefore the fully independent keys-into-bins analysis does not directly apply. 1.1 The expected max-load of a linear map The maximum-load behavior of linear hashing has been studied for several decades. Alon, Dietzfelbinger, Miltersen, Petrank and Tardos [ 1 ] proved that, for binary linear hashing, \mathbb{E}_{h}[\mathsf{M}(S,h)]=O(\log n\log\log n). They asked whether the fully independent scale O(\log n/\log\log n) is also valid for random binary linear maps. Jaber, Kumar and Zuckerman [ 3 ] then proved the optimal expected maximum-load bound for the binary case. They showed that \mathbb{E}_{h}[\mathsf{M}(S,h)]\leq 16\frac{\log n}{\log\log n}. They also proved the tail estimate \Pr\left[\mathsf{M}(S,h)\geq R\frac{\log n}{\log\log n}\right]\leq O\left(\frac{1}{R^{2}}\right). Their proof uses an exponential-potential method. One advantage of this method is that it directly tracks the growth of bucket loads as the kernel of the linear map is revealed one dimension at a time. 1.2 Our result and comparison with fully independent hashing We record a small optimization of the Jaber–Kumar–Zuckerman potential argument. Their method uses an exponential potential with a certain base. To detect a bucket of load R\frac{\log n}{\log\log n}, it is enough to use base roughly \ell^{1/R} , rather than base roughly \ell . This lowers the initial potential and gives a sharper tail bound. Our main tail estimate is the following. There are absolute constants C,D>0 such that, for every R>1 satisfying R\ell^{1-1/R}\geq D\ln\ell, we have \Pr\left[\mathsf{M}(S,h)\geq R\frac{\log n}{\log\log n}\right]\leq C\frac{(\log\log n)^{2}}{R^{2}(\log n)^{2-2/R}}. This improves the O(R^{-2}) tail bound in the range where R is fixed, and it remains useful even when R is very close to 1 . Integrating the optimized tail gives \mathbb{E}_{h}[\mathsf{M}(S,h)]\leq\frac{\log n}{\log\log n}+(1+o(1))\frac{\log n\cdot\log\log\log n}{(\log\log n)^{2}}. Thus binary linear hashing matches fully independent hashing in the leading term and also matches the dominant part of the second-order correction. 1.3 A sharp tail bound for one prescribed bucket We also prove a separate fixed-bucket result. This part is independent of the potential method. Fix one bucket y\in\mathbb{F}_{2}^{\ell} . We prove that \Pr[\operatorname{load}_{h}(y)>2^{a}]\leq\gamma^{-1}2^{-a^{2}},\qquad\gamma:=\prod_{j=1}^{\infty}(1-2^{-j}). The proof is elementary. If a prescribed bucket is large, then it contains many ordered linearly independent tuples. On the other hand, a random linear map sends any fixed independent tuple to that prescribed bucket with very small probability. Counting such tuples and applying Markov’s inequality gives the tail bound. This fixed-bucket bound is essentially sharp. A subspace example shows that the upper bound is asymptotically tight even in the leading constant as a\to\infty . Thus the 2^{-a^{2}} fixed-bucket tail is the correct scale. However, this fixed-bucket theorem does not by itself imply the correct expectation bound for the maximum load. A direct union bound over all 2^{\ell} buckets loses a factor 2^{\ell} . Therefore the fixed-bucket estimate is best viewed as a sharp far-tail result for one prescribed bucket, while the optimized potential method is needed to control the maximum load near the expectation scale. 1.4 The case of m keys and n bins The same base-optimized argument also applies when the number of keys is not equal to the number of bins. Let the number of bins be n=2^{\ell} , let |S|=m , and write \lambda:=\frac{m}{n} for the average load. We consider the regime where the maximum-load scale

Read the complete text