[name=Theorem,numberwithin=section]thm

# Locally Uniform Hashing

Ioana O. Bercea  IT University of Copenhagen
<EMAIL_ADDRESS>Lorenzo Beretta  University of Copenhagen
{beretta, jokl, jakn<EMAIL_ADDRESS>Jonas Klausen  University of
Copenhagen
{beretta, jokl, jakn<EMAIL_ADDRESS>Jakob Bæk Tejs Houen  University of
Copenhagen
{beretta, jokl, jakn<EMAIL_ADDRESS>Mikkel Thorup  University of
Copenhagen
{beretta, jokl, jakn<EMAIL_ADDRESS>
###### Abstract

Hashing is a common technique used in data processing, with a strong impact on
the time and resources spent on computation. Hashing also affects the
applicability of theoretical results that often assume access to (unrealistic)
uniform/fully-random hash functions. In this paper, we are concerned with
designing hash functions that are practical and come with strong theoretical
guarantees on their performance.

To this end, we present tornado tabulation hashing, which is simple, fast, and
exhibits a certain full, local randomness property that provably makes diverse
algorithms perform almost as if (abstract) fully-random hashing was used. For
example, this includes classic linear probing, the widely used HyperLogLog
algorithm of Flajolet, Fusy, Gandouet, Meunier [AOFA’97] for counting distinct
elements, and the one-permutation hashing of Li, Owen, and Zhang [NIPS’12] for
large-scale machine learning. We also provide a very efficient solution for
the classical problem of obtaining fully-random hashing on a fixed (but
unknown to the hash function) set of $n$ keys using $O(n)$ space. As a
consequence, we get more efficient implementations of the splitting trick of
Dietzfelbinger and Rink [ICALP’09] and the succinct space uniform hashing of
Pagh and Pagh [SICOMP’08].

Tornado tabulation hashing is based on a simple method to systematically break
dependencies in tabulation-based hashing techniques.

##  1 Introduction

The generic goal of this paper is to create a practical hash function that
provably makes important algorithms behave almost as if (unrealistic) fully
random hashing was used. By practical, we mean both simple to implement and
fast. Speed is important because hashing is a common inner loop for data
processing. Suppose for example that we want to sketch a high-volume data
stream such as the packets passing a high-end Internet router. If we are too
slow, then we cannot handle the stream at all. Speed matters, also within
constant factors.

The use of weak hash functions is dangerous, not only in theory but also in
practice. A good example is the use of classic linear hashing. Linear hashing
is 2-independent and Mitzenmacher and Vadhan [27] have proved that, for some
applications, 2-independent hashing performs as well as fully random hashing
if the input has enough entropy, and indeed this often works in practice.
However, a dense set has only 1 bit of entropy per element, and [36, 30] have
shown that with a linear hashing scheme, if the input is a dense set (or more
generally, a dense subset of an arithmetic sequence), then linear probing
becomes extremely unreliable and the expected probe length111The probe length
is defined as the number of contiguous cells probed to answer a query of a
linear probing hash table. increases from constant to $\Omega(\log n)$. This
is also a practical problem because dense subsets may occur for many reasons.
However, if the system is only tested on random inputs, then we may not
discover the problem before deployment.

The issue becomes even bigger with, say, sampling and estimation where we
typically just trust our estimates with no knowledge of the true value. We may
never find out that our estimates are bad. With 2-independent hashing, we get
the right variance, but not exponential concentration. Large errors can happen
way too often, yet not often enough to show up in a few tests. This phenomenon
is demonstrated on synthetic data in [2] and on real-world data in [1]. All
this shows the danger of relying on weak hash functions without theoretical
guarantees for all possible inputs, particularly for online systems where we
cannot just change the hash function if the input is bad, or in situations
with estimates whose quality cannot be verified. One could instead, perhaps,
use hash functions based on cryptographic assumptions, but the hash function
that we propose here is simple to implement, fast, and comes with strong
unconditional guarantees.

In this paper, we introduce _tornado tabulation hashing_. A tornado tabulation
hash function $h:\Sigma^{c}\to\mathcal{R}$ requires $O(c\left|\Sigma\right|)$
space and can be evaluated in $O(c)$ time using, say, $2c$ lookups in tables
with $\left|\Sigma\right|$ entries plus some simple AC0 operations (shifts,
bit-wise xor, and assignments). As with other tabulation schemes, this is very
fast when $\Sigma$ is small enough to fit in fast cache, e.g., for 32-bit keys
divided into $c=4$ characters of 8 bits (namely, $|\Sigma|=2^{8}$), the speed
is similar to that of evaluating a degree-2 polynomial over a Mersenne prime
field.

Tornado hashing has the strong property that if we hash a set of
$\left|\Sigma\right|/2$ keys, then with high probability, the hash values are
completely independent. For when we want to handle many more keys, e.g., say
$\left|\Sigma\right|^{3}$ (as is often the case when $\Sigma$ is small),
tornado tabulation hashing offers a certain _local uniformity_ that provably
makes a diverse set of algorithms behave almost as if the hashing was fully
random on all the keys. The definition of local uniformity is due to
Dahlgaard, Knudsen, Rotenberg, and Thorup [10]. The definition is a bit
complicated, but they demonstrate how it applies to the widely used
HyperLogLog algorithm of the Flajolet, Fusy, Gandouet, Meunier [18] for
counting distinct elements in data streams, and the One-Permutation Hashing of
Li, Owen, and Zhang [26] used for fast set similarity. They conclude that the
estimates obtained are only a factor $1+o(1)$ worse than if fully-random
hashing was used. Interestingly, [10] proves this in a high-level black-box
manner. Loosely speaking, the point is that the algorithm using locally
uniform hashing behaves as well as the same algorithm using fully-random
hashing on a slightly worse input.

As a new example, we will demonstrate this on linear probing. Knuth’s original
1963 analysis of linear probing [25], which started the field of algorithms
analysis, showed that with fully-random hashing and load $(1-\varepsilon)$,
the expected probe length is $(1+1/\varepsilon^{2})/2$. From this, we conclude
that tornado tabulation hashing yields expected probe length
$(1+o(1))(1+1/\varepsilon^{2})/2$, and we get that without having to
reconsider Knuth’s analysis.

For contrast, consider the work on linear probing with $k$-independent
hashing. Pagh, Pagh, Ružić [29] showed that $5$-independence is enough to
obtain a bound of $O(1/\varepsilon^{13/6})$ on the expected probe length. This
was further improved to $O(1/\varepsilon^{2})$ by Pǎtraşcu and Thorup [31],
who achieved the optimal $O(1/\varepsilon^{2})$. They matched Knuth’s bound
modulo some large constants hidden in the $O$-notation and needed a very
different analysis.

In practice, the guarantee that we perform almost like fully-random hashing
means that no set of input keys will lead to substantially different
performance statistics. Thus, if we tested an online system on an arbitrary
set of input keys, then we do not have to worry that future input keys will
degrade the performance statistics, not even by a constant factor.

The definition of local uniformity is due to Dahlgaard, Knudsen, Rotenberg,
and Thorup [10]. They did not name it as an independent property, but they
described it as a property of their new hashing scheme: mixed tabulation
hashing. However, the local uniformity of mixed tabulation assumes table size
$\left|\Sigma\right|\to\infty$, but the speed of tabulation hashing relies on
$\left|\Sigma\right|$ being small enough to fit in fast cache and all reported
experiments use 8-bit characters (see [31, 2, 1, 11]). However, none of the
bounds from [10] apply to 8 or even 16-bit characters, e.g., they assume
$O(\log\left|\Sigma\right|)^{c}<\left|\Sigma\right|$. Our new scheme avoids
the exponential dependence on $c$, and we get explicit error probability
bounds that are meaningful, not just in theory, but also for practice with
tables in fast cache.

For when we want full randomness on more keys than fit in fast cache, we
could, as above, increase $\left|\Sigma\right|$ in all $O(c)$ lookup tables.
In this paper, we show that it suffices to augment the in-cache tornado
hashing with just $2$ lookups in tables of size $2n$ to get full randomness on
$n$ keys with high probability. This would work perfectly inside a linear
space algorithm assuming fully-random hashing, but it also leads to more
efficient implementations of the spitting trick of Dietzfelbinger and Rink
[13] and the succinct space uniform hashing of Pagh and Pagh [28].

In Section 1.1 we define our hash function, and in Section 1.2 we present our
technical results, including the definition of local uniformity. In Section
1.3, we discuss more explicitly how our work compares to mixed tabulation and
explain some of our techniques in comparison. In Section 1.4 we discuss
several applications. In Section 1.5, we relate our work to previous work on
achieving highly independent hash functions. Finally, in Section 1.6 we
discuss how tornado tabulation can be employed to improve the so-called
‘‘splitting trick’’ and succinct uniform hashing.

###  1.1 Tornado tabulation hashing

#### Simple tabulation hashing.

We first introduce our main building block, which is the simple tabulation
hash function dating back to at least Zobrist [38] and Wegman and Carter [37].
Throughout the paper, we will consider keys to come from the universe
$\Sigma^{c}$ and hash values to be in $\mathcal{R}=[2^{r}]$. More concretely,
we interpret a key $x$ as the concatenation of $c$ _characters_ $x_{1}\dots
x_{c}$ from $\Sigma$. We then say that a function
$h:\Sigma^{c}\longrightarrow\mathcal{R}$ is a _simple tabulation_ hash
function if

$h(x)=T_{1}[x_{1}]\oplus\cdots\oplus T_{c}[x_{c}]$

where, for each $i=1\dots c$, $T_{i}:\Sigma\longrightarrow\mathcal{R}$ is a
fully-random function stored as a table.

We think of $c$ as a small constant, e.g., $c=4$, for 32-bit keys divided into
8-bit characters, yet we will make the dependence on $c$ explicit. We assume
that both keys and hash values fit in a single word and that
$\left|\Sigma\right|\geq 2^{8}$.

#### Tornado tabulation hashing.

To define a tornado tabulation hash function $h$, we use several simple
tabulation hash functions. A tornado tabulation function has a number $d$ of
_derived_ characters. Think of $d$ as, say, $c$ or $2c$. It will later
determine our error probability bounds. We will always assume $d=O(c)$ so that
$d$ characters from $\Sigma$ can be represented in $O(1)$ words of memory
(since a key from $\Sigma^{c}$ fits in a single word).

For each $i=0,\ldots,d$, we let
$\widetilde{h}_{i}:\Sigma^{c+i-1}\longrightarrow\Sigma$ be a simple tabulation
hash function. Given a key $x\in\Sigma^{c}$, we define its _derived key_
$\widetilde{h}(x)\in\Sigma^{c+d}$ as
$\widetilde{x}=\widetilde{x}_{1}\cdots\widetilde{x}_{c+d}$, where

$\widetilde{x}_{i}=\begin{cases}x_{i}&\text{if $i<c$}\\\
x_{c}\oplus\widetilde{h}_{0}(\widetilde{x}_{1}\cdots\widetilde{x}_{c-1})&\text{if
$i=c$}\\\
\widetilde{h}_{i-c}\left(\widetilde{x}_{1}\cdots\widetilde{x}_{i-1}\right)&\text{if
$i>c$}.\end{cases}$ (1)

We note that each of the $d$ derived characters
$\widetilde{x}_{c+1},\ldots,\widetilde{x}_{c+d}$ is progressively defined by
applying a simple tabulation hash function to all its preceding characters in
the derived key $\widetilde{x}$. Hence, the name tornado tabulation. The step
by which we obtain $\widetilde{x}_{c}$ corresponds to the twist from [32]. By
Observation $1.1.$ in [32], $x_{1}\dots
x_{c}\mapsto\widetilde{x}_{1}\dots\widetilde{x}_{c}$ is a permutation, so
distinct keys have distinct derived keys. Finally, we have a simple tabulation
hash function $\widehat{h}:\Sigma^{c+d}\longrightarrow\mathcal{R}$, that we
apply to the derived key. The _tornado tabulation_ hash function
$h:\Sigma^{c}\longrightarrow\mathcal{R}$ is then defined as
$h(x)=\widehat{h}(\widetilde{x})$.

#### Implementation.

The simplicity of tornado tabulation is apparent from its C implementation
below. In the code, we fold tornado’s lookup tables together so we can
implement them using $c+d$ character tables
$\Sigma\to\Sigma^{d+1}\times\mathcal{R}$. Elements of
$\Sigma^{d+1}\times\mathcal{R}$ are just represented as $w$-bits numbers. For
memory alignment and ease of implementation, we want $w$ to be a power of two
such as $64$ or $128$.

We now present a C-code implementation of tornado tabulation for 32-bit keys,
with $\Sigma=[2^{8}]$, $c=4$, $d=4$, and $\mathcal{R}=[2^{24}]$. Besides the
key x, the function takes as input an array of $c+d$ tables of size
$|\Sigma|$, all filled with independently drawn 64-bit values.

⬇

INT32 Tornado(INT32 x, INT64[8][256] H) {

INT32 i; INT64 h=0; INT8 c;

for (i=0;i<3;i++) {

c=x;

x>>=8;

h^=H[i][c];}

h^=x;

for (i=3;i<8;i++) {

c=h;

h>>=8;

h^=H[i][c];}

return ((INT32) h);}

#### Speed.

As we can see in the above implementation, tornado hashing uses $c+d$ lookups
and $O(c+d)$ simple AC0 operations. The speed of tabulation hashing depends on
the tables fitting in fast cache which means that $\Sigma$ should not be too
big. In the above code, we used $\Sigma=[2^{8}]$, as in all previously
reported experiments with tabulation hashing. (see [31, 2, 1, 11]).

The speed of tabulation schemes is incomparable to that of polynomial methods
using small space but multiplication. Indeed, the ratio between the cost of
cache lookups and multiplication depends on the architecture. In line with
previous experiments, we found our tornado implementation for 32-bit keys to
be as fast as a degree-2 polynomial over a Mersenne prime ($2^{89}-1$) field.

We note that our implementation for the random table H only needs a pointer to
an area filled with ‘‘fixed" random bits, and it could conceivably be made
much faster if we instead of cache had access to random bits stored in simple
read-only memory (ROM or EPROM).

###  1.2 Theoretical Results

The main aim of our paper is to prove that, with high probability (whp), a
tornado tabulation hash function is fully random on some set $X$ of keys. The
challenge is to characterize for which kinds of sets we can show such bounds.

Full randomness for fixed keys. We begin with a simpler result that follows
directly from our main technical theorem. In this case, the set $X$ of keys is
fixed.

######  Theorem 1.

Let $h:\Sigma^{c}\to\mathcal{R}$ be a random tornado tabulation hash function
with $d$ derived characters. For any fixed $X\subseteq\Sigma^{c}$, if
$\left|X\right|\leq|\Sigma|/2$, then $h$ is fully random on $X$ with
probability at least

$1-7|X|^{3}(3/|\Sigma|)^{d+1}-1/2^{\left|\Sigma\right|/2}\;.$

With $c,d=O(1)$, Theorem 1 gives an $O(\left|\Sigma\right|)$ space hash
function that can be evaluated in constant time and, with high probability,
will be fully random for any fixed set $X$ of at most $\left|\Sigma\right|/2$
keys. This is asymptotically tight as we need $|X|$ random hash values to get
this randomness.

The random process behind the error probability that we get will be made clear
in the next paragraph. We note here that, since $|X|\leq|\Sigma|/2$, we have
that $7|X|^{3}(3/|\Sigma|)^{d+1}\leq 24(3/|\Sigma|)^{d-2}$. With
$\left|\Sigma\right|\geq 2^{8}$, the bound is below $1/300$ for $d=4$, and
decreases rapidly for larger $d$. For $c\geq 4$, if we set $d=2c$, we get an
error probability below $1/u$ where $u=\left|\Sigma\right|^{c}$ is the size of
the universe. We can get error probability $1/u^{\gamma}$ for any constant
$\gamma$ with $d=O(c)$, justifying this assumption on $d$.

Linear independence. The general structure of our results is to identify some
error event such that (1) if the event does not occur, then the hash function
will be fully random on $X$, and (2) the error event itself happens with low
probability. The error event that we consider in Theorem 1 is inherent to all
tabulation-based hashing schemes. Namely, consider some set $Y$ of keys from
some universe $\Sigma^{b}$. We say that $Y$ is _linearly independent_ if and
only if, for every subset $Y^{\prime}\subseteq Y$, there exists a character
position $i\in\left\\{1,\ldots,b\right\\}$ such that some character appears an
odd number of times in position $i$ among the keys in $Y^{\prime}$. A useful
connection between this notion and tabulation-based hashing was shown by
Thorup and Zhang [36], who proved that a set of keys is linearly independent
if and only if simple tabulation hashing is fully random on these keys:

######  Lemma 2 (Simple tabulation on linearly independent keys).

Given a set of keys $Y\subseteq\Sigma^{b}$ and a simple tabulation hash
function $h:\Sigma^{b}\rightarrow\mathcal{R}$, the following are equivalent:

  1. (i)

$Y$ is linearly independent

  2. (ii)

$h$ is fully random on $Y$ (i.e., $h|_{Y}$ is distributed uniformly over
$\mathcal{R}^{Y}$).222In general, we employ the notation $h|_{S}$ to denote
the function $h$ restricted to the keys in some set $S$.

To prove Theorem 1, we employ Lemma 2 with sets of derived keys. Namely, given
a set of keys $X\subseteq\Sigma^{c}$, we consider the error event that the set
$\widetilde{X}=\left\\{\widetilde{h}(x)\mid x\in X\right\\}$ of its derived
keys is linearly dependent. We then show that this happens with probability at
most $7|X|^{3}(3/|\Sigma|)^{d+1}+1/2^{\left|\Sigma\right|/2}$. If this doesn’t
happen, then the derived keys are linearly independent, and, by Lemma 2, we
get that the tornado tabulation hash function
$h=\widehat{h}\circ\widetilde{h}$ is fully random on $X$ since it applies the
simple tabulation hash function $\widehat{h}$ to the derived keys
$\widetilde{X}$. We note that the general idea of creating linearly
independent lookups to create fully-random hashing goes back at least to [33].
The point of this paper is to do it in a really efficient way.

#### Query and selected keys.

Our main result, Theorem 5, is a more general version of Theorem 1.
Specifically, while Theorem 1 holds for any fixed set of keys, it requires
that $\left|X\right|\leq\left|\Sigma\right|/2$. For a fast implementation, we
want $\left|\Sigma\right|$ to be small enough to fit in fast cache, e.g.,
$\left|\Sigma\right|=2^{8}$, but in most applications, we want to hash a set
$S$ of keys that is much larger, e.g.,
$\left|S\right|\sim\left|\Sigma\right|^{3}$. Moreover, we might be interested
in showing full randomness for subsets $X$ of $S$ that are not known in
advance: consider, for instance, the set $X$ of all the keys in $S$ that hash
near to $h(q)$ for some fixed key $q\in S$. In this case, Theorem 1 would not
help us, since the set $X$ depends on $h(q)$ hence on $h$.

To model this kind of scenario, we consider a set of _query keys_
$Q\subseteq\Sigma^{c}$ and define a set of _selected keys_
$X\subseteq\Sigma^{c}$. Whether a key $x$ is selected or not depends only on
$x$, its own hash value $h(x)$, and the hash values of the query keys $h|_{Q}$
(namely, conditioning on $h(x)$ and $h|_{Q}$ makes $x\in X$ and $h$
independent). In Theorem 5, we will show that, if the selected keys are few
enough, then $h|_{X}$ is fully random with high probability.

Formally, we have a selector function
$f:\Sigma^{c}\times\mathcal{R}\times\mathcal{R}^{Q}\longrightarrow\\{0,1\\}$
and we define the set of selected keys as

$X^{f,h}=\left\\{x\in\Sigma^{c}\;|\;f(x,h(x),h|_{Q})=1\right\\}.$

We make the special requirement that $f$ should always select all the query
keys $q\in Q$, that is, $f(q,\cdot,\cdot)=1$ regardless of the two last
arguments. We then define

$\mu^{f}:=\sum_{x\in\Sigma^{c}}p^{f}_{x}\quad\text{ with }\quad
p^{f}_{x}:=\max_{\varphi\in\mathcal{R}^{Q}}\Pr_{r\sim\mathcal{U}(\mathcal{R})}\left[f(x,r,\varphi)=1\right]\;.$
(2)

Here the maximum is taken among all possible assignments of hash values to
query keys $\varphi:Q\to\mathcal{R}$ and $r$ is distributed uniformly over
$\mathcal{R}$. Trivially we have that

######  Observation 3.

If $h:\Sigma^{c}\to\mathcal{R}$ is fully random then
$\textnormal{E}[|X^{f,h}|]\leq\mu^{f}$.

When $f$ and $h$ are understood, we may omit these superscripts. It is
important that $X$ depends on both $f$ and $h$ while $\mu$ only depends on the
selector $f$. We now have the following main technical theorem:

######  Theorem 4.

Let $h=\widehat{h}\circ\widetilde{h}:\Sigma^{c}\to\mathcal{R}$ be a random
tornado tabulation hash function with $d$ derived characters and $f$ as
described above. If $\mu^{f}\leq\Sigma/2$ then the derived selected keys
$\widetilde{h}(X^{f,h})$ are linearly dependent with probability at most
$\textsf{DependenceProb}(\mu^{f},d,\Sigma$), where

$\textsf{DependenceProb}(\mu,d,\Sigma):=7\mu^{3}(3/|\Sigma|)^{d+1}+1/2^{|\Sigma|/2}\;.$

Note that Theorem 4 only bounds the probability of the error event. Similarly
as in Theorem 1, we would like to then argue that, if the error event does not
happen, we could apply Lemma 2 to claim that the final hash values via the
simple tabulation function $\widehat{h}$ are fully random. The challenge,
however, is the presence of an inherent dependency in how the keys are
selected to begin with, namely that $h=\widehat{h}\circ\widetilde{h}$ is
already used to select the keys in $X^{f,h}$. In other words, by the time we
want to apply $\widehat{h}$ to the derived selected keys
$\widetilde{h}(X^{f,h})$, we have already used some information about
$\widehat{h}$ in selecting them in $X^{f,h}$.

Local uniformity. Nevertheless, there is a general type of selector functions
for which we can employ Theorem 4 in conjunction with Lemma 2 to claim full
randomness. Namely, we consider selector functions that partition the bit
representation of the final hash values into $s$ _selection bits_ and $t$
_free bits_ so that
$\mathcal{R}=\mathcal{R}_{s}\times\mathcal{R}_{t}=[2^{s}]\times[2^{t}]$. Given
a key $x\in\Sigma^{c}$, we then denote by $h^{(s)}(x)\in\mathcal{R}_{s}$ and
$h^{(t)}(x)\in\mathcal{R}_{t}$ the selection and free bits of $h(x)$
respectively. We then say that a selector function $f$ is an _$s$ -selector_
if, for all $x\in\Sigma^{c}$, the output of $f(x,h(x),h|_{Q})$ only depends on
the selection bits of the hash function, i.e.,
$f(x,h(x),h|_{Q})=f(x,h^{(s)}(x),h^{(s)}|_{Q})$.

We now crucially exploit the fact that the output bits of a simple tabulation
hash function are completely independent. Formally, we split the simple
tabulation $\widehat{h}$ into two independent simple tabulation functions:
$\widehat{h}^{(s)}$ producing the selection bits and $\widehat{h}^{(t)}$
producing the free bits. We then apply Theorem 4 to
$h^{(s)}=\widehat{h}^{(s)}\circ\widetilde{h}$ to conclude that the set of
selected derived keys $\widetilde{h}(X^{f,h^{(s)}})$ is linearly independent
with high probability. Assuming this, we then apply Lemma 2 to conclude that
$\widehat{h}^{(t)}$ is fully random on
$\widetilde{h}(X^{f,\widehat{h}^{(s)}})$, hence that
$h^{(t)}=\widehat{h}^{(t)}\circ\widetilde{h}$ is fully random on
$X^{f,h^{(s)}}$.

######  Theorem 5.

Let $h:\Sigma^{c}\to\mathcal{R}$ be a tornado tabulation hash function with
$d$ derived characters and $f$ be an $s$-selector as described above. If
$\mu^{f}\leq\Sigma/2$, then $h^{(t)}$ is fully random on $X^{f,h^{(s)}}$ with
probability at least

$1-\textsf{DependenceProb}(\mu^{f},d,\Sigma)\;.$

While the concept of an $s$-selector function might seem a bit cryptic, we
note that it intuitively captures the notion of locality that linear probing
and other applications depend on. Namely, the effect of the (high
order333Thinking about selector bits as higher order bits helps our intuition.
However, they do not have to be higher-order bits necessarily. More generally,
any representation of $\mathcal{R}$ as a product
$\mathcal{R}_{s}\times\mathcal{R}_{t}$ would do the job.) selector bits is to
specify a dyadic interval444Recall that a dyadic interval is an interval of
the form $[j2^{i},(j+1)2^{i})$, where $i,j$ are integers. of a given length
such that all the keys with hash values falling in that interval are possibly
selected (with this selection further depending, perhaps, on the query keys
$Q$, or on other specific selector bits, leading to more refined dyadic
intervals). Theorem 5 then says that the (low order) free bits of these
selected keys will be fully-random with high probability. In other words, the
distribution inside such a neighborhood is indistinguishable from what we
would witness if we had used a fully-random hash function.

As mentioned earlier, the concept of local uniformity stems from [10], except
that they did not consider query keys. Also, they didn’t name the concept.
They demonstrated its power in different streaming algorithms. For those
applications, it is important that _the selection bits are not known to the
algorithm_. They are only set in the analysis based on the concrete input to
demonstrate good performance on this input. The problem in [10] is that their
error probability bounds only apply when the alphabet is so large that the
tables do not fit in fast cache. We will describe this issue closer in Section
1.3. In Section 1.4 we will sketch the use of local uniformity on linear
probing where the locality is relative to a query key.

Upper tail Chernoff bounds. Theorem 5 is only concerned with the distribution
of the free bits of the selected keys, but to employ it in our applications,
we often require that the number of selected keys is not much larger than
$\mu^{f}$ with high probability (see Sections 1.4 and 1.6). We show that this
size can be bounded from above with the usual Chernoff bound when the set of
derived selected keys is linearly independent.

######  Lemma 6.

Let $h=\widehat{h}\circ\widetilde{h}:\Sigma^{c}\to\mathcal{R}$ be a random
tornado tabulation hash function with $d$ derived characters, query keys $Q$
and selector function $f$. Let $\mathcal{I}_{X^{f,h}}$ denote the event that
the set of derived selected key $\widetilde{h}(X^{f,h})$ is linearly
independent. Then, for any $\delta>0$, the set $X^{f,h}$ of selected keys
satisfies the following:

$\Pr\left[{\left|X^{f,h}\right|\geq(1+\delta)\cdot\mu^{f}\wedge\mathcal{I}_{X^{f,h}}}\right]\leq\left(\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\right)^{\mu^{f}}\;.$

For a nice direct application, consider hash tables with chaining, or throwing
$n$ keys into $n$ bins using tornado hashing. We can select a given bin, or
the bin of a given query key. In either case we have $\mu^{f}=1$ and then
Lemma 6 together with Theorem 4 says that the probability of getting $k$ keys
is bounded by

$e^{k-1}/k^{k}+7(3/\left|\Sigma\right|)^{d+1}+1/2^{\left|\Sigma\right|/2}.$
(3)

If $k$ is not too large, the first term dominates.

Lower bound. Finally, we show that our upper bound for the error probability
in Theorem 4 is tight within a constant factor.

######  Theorem 7.

Let $h=\widehat{h}\circ\widetilde{h}:\Sigma^{c}\to\mathcal{R}$ be a random
tornado tabulation hash function with $d$ derived characters. There exists a
selector function $f$ with $\mu^{f}\leq\Sigma/2$ such that the derived
selected keys $\widetilde{h}(X^{f,h})$ are linearly dependent with probability
at least $\Omega((3/|\Sigma|)^{d-2})$.

Full randomness for larger sets of selected keys. As mentioned earlier, for a
fast implementation of tabulation hashing, we pick the alphabet $\Sigma$ small
enough for the tables to fit in fast cache. A common choice is 8-bit
characters. However, we only get full randomness for (selected) sets of
(expected) size at most $\left|\Sigma\right|/2$ (c.f. Theorems 5 and 1).

To handle larger sets, we prove that it suffices to only increase the alphabet
of the last two derived characters; meaning that only two lookups have to use
larger tables. This is close to best possible in that we trivially need at
least one lookup in a table at least as big as the set we want full randomness
over. More precisely, if we use alphabet $\Psi$ for the last two derived
characters, then our size bound increases to $\left|\Psi\right|/2$. The error
probability bound of Theorems 5 becomes

$14(\mu^{f})^{3}(3/|\Psi|)^{2}(3/|\Sigma|)^{d-1}+1/2^{\left|\Sigma\right|/2}\;.$

With the above mix of alphabets, we have tornado hashing running in fast cache
except for the last two lookups that could dominate the overall cost, both in
time and space. Because they dominate, we will consider a slight variant,
where we do not store derived characters in any of the two large tables.
Essentially this means that we change the definition of the last derived
character from
$\widetilde{x}_{c+d}=\widetilde{h}_{d}(\widetilde{x}_{1}\cdots\widetilde{x}_{c+d-1})$
to
$\widetilde{x}_{c+d}=\widetilde{h}_{d}(\widetilde{x}_{1}\cdots\widetilde{x}_{c+d-2})$.
This is going to cost us a factor two in the error probability, but in our
implementation, we will now have $c+d-2$ lookups in tables
$\Sigma\to\Sigma^{d-1}\times\Psi^{2}\times R$ (where the values are
represented as a single $w$-bit numbers), and 2 lookups in tables $\Psi\to R$.
We shall refer to this scheme as _tornado-mix_. Corresponding to Theorem 5, we
get

######  Theorem 8.

Let $h=\widehat{h}\circ\widetilde{h}:\Sigma^{c}\to\mathcal{R}$ be a random
tornado-mix tabulation hash function with $d$ derived characters, the last two
from $\Psi$, and an $s$-selector function $f$. If
$\mu=\mu^{f}\leq\left|\Psi\right|/2$ then $h^{(t)}$ is fully random on
$X^{f,h}$ with probability at least

$1-14\mu^{3}(3/|\Psi|)^{2}(3/|\Sigma|)^{d-1}-1/2^{\left|\Sigma\right|/2}\;.$

An interesting case is when we want linear space uniform hashing for a fixed
set $X$, in which case $\mu=\left|X\right|$ above. This leads to a much better
implementation of the uniform hashing fo Pagh and Pagh [28]. The main part of
their paper was to show a linear space implementation, and this would suffice
for all but the most succinct space algorithms. They used highly independent
hashing [33, 35] as a subroutine, but this subroutine alone is orders of
magnitude slower than our simple implementation (see, e.g., [1]). They
combined this with a general reduction from succinct space to linear space,
for which we now have a really efficient construction.

###  1.3 Techniques and relation to mixed tabulation

In spirit, our results are very related to the results on mixed tabulation
[10]. For now, we only consider the case of a single alphabet $\Sigma$.
Indeed, tornado and mixed tabulation are very similar to implement. Both deal
with $c$-character keys from some alphabet $\Sigma$, produce a derived key
with $c+d$ characters, and then apply a top simple tabulation to the resulting
derived keys. Both schemes can be implemented with $c+d$ lookups. The
difference is in how the two schemes compute the derived keys. For ease of
presentation, let $\widetilde{h}_{i}:\Sigma^{*}\to\Sigma$, that is,
$\widetilde{h}_{i}$ adjusts to the number of characters in the input. Now for
mixed tabulation, we define the derived key
$\widetilde{x}_{1}\cdots\widetilde{x}_{c+d}$ by

$\widetilde{x}_{i}=\begin{cases}x_{i}&\text{if $i\leq c$}\\\
\widetilde{h}_{i-c}\left(\widetilde{x}_{1}\dots\widetilde{x}_{c}\right)&\text{if
$i>c$}.\end{cases}$

The analysis from [10] did not consider query keys, but ignoring this issue,
their analysis works in the limit $\left|\Sigma\right|\to\infty$. For example,
the analysis from [10] requires that 555While using their Lemma 3, if $t$ goes
up to $s$ in case D.

$(\log|\Sigma|)^{c}\leq|\Sigma|/2.$

This is true for $c=O(1)$ and $|\Sigma|\to\infty$, but simply false for
realistic parameters. Assuming the above condition to be satisfied, if we
consider scenarios with non-constant $c$ and $d$, the error probability from
[10] becomes

$\left(O(cd)^{c}/|\Sigma|\right)^{\lfloor
d/2\rfloor-1}+1/2^{\Omega(|\Sigma|)}.$

Now, even if we replace $O(cd)$ with $cd$, the error probability is not below
1 even with $16$-bit characters and $c=4$. In contrast, practical tabulation
schemes normally use $8$-bit characters for efficiency, and our explicit bound
of $7\mu^{3}(3/|\Sigma|)^{d+1}+1/2^{|\Sigma|/2}$ from Theorem 4 works fine
even in this case, implying that our theory actually applies to practice.

The reason that mixed tabulation has the problematic exponential dependency on
$c$ is that for a set of linearly dependent keys, it uses a clever encoding of
each of the $c$ characters in some of the keys. With tornado, the only
encoding we use is that if we have a zero set of keys, then each key is the
xor of the other keys in the zero set, and this is independent of $c$. 666A
set is linearly dependent if it contains a subset that is a zero set. See
Section 2 for the precise definition.

To describe the advantage of tornado tabulation over mixed tabulation, it is
easier to first compare with what we call _simple tornado_ where the derived
key $\widetilde{x}_{1}\cdots\widetilde{x}_{c+d}$ is defined by

$\widetilde{x}_{i}=\begin{cases}x_{i}&\text{if $i\leq c$}\\\
\widetilde{h}_{i-c}\left(\widetilde{x}_{1}\dots\widetilde{x}_{i-1}\right)&\text{if
$i>c$}.\end{cases}$

The implementation difference is that with simple tornado, each derived
character uses all preceding characters while mixed tabulation uses only the
original characters. This difference gives tornado a big advantage when it
comes to breaking up linear dependence in the input keys. Recall that a set
$Y\subset\Sigma^{c+d}$ of derived keys is linearly independent if and only if,
for every subset $Y^{\prime}\subseteq Y$, there exists a character position
$i\in\left\\{1,\ldots,c+d\right\\}$ such that some character appears an odd
number of times in position $i$ among the keys in $Y^{\prime}$. Intuitively,
the strategy is to argue that whatever linear dependence exists in the input
key set to begin with (essentially, in the first $c$ characters of the derived
keys) will, whp, be broken down by their $d$ derived characters (and hence,
disappear in the derived keys). In this context, the way we compute the
derived characters becomes crucial: in mixed tabulation, each derived
character is computed independently of the other derived characters. Thus,
whether a derived character breaks a dependency or not is independent of what
other derived characters do. In contrast, we make the derived characters in
tornado tabulation depend on all previously computed derived characters such
that, if we know that some derived character does not break a dependency, then
we also know that none of its previously computed derived characters have
broken it either. Or, in other words, each successive tornado-derived
character benefits from the dependencies already broken by previously computed
derived characters, i.e., the benefits compound each time we compute a new
derived character.

This structural dependence between tornado-derived characters turns out to be
very powerful in breaking linear dependencies among the input keys and indeed,
leads to a much cleaner analysis. The most important benefit, however, is that
tornado tabulation has a much lower error probability. For simple tornado, we
get an error probability of

$7(\mu^{f})^{3}(3/|\Sigma|)^{d}+1/2^{\left|\Sigma\right|/2}\;\textnormal{,}$

which essentially gains a factor $(3/|\Sigma|)$ for each derived character. It
turns out that we gain an extra factor $(3/|\Sigma|)$ if we twist the last
original character as we did in the original tornado definition (1), and then
we get the bound from Theorem 5, the point being that this twisting does not
increase the number of lookups.

One might wonder if twisting more characters would help further, that is,
setting
$\widetilde{x}_{i}=x_{i}\oplus\widetilde{h}_{i}(\widetilde{x}_{1}\cdots
x_{i-1})$ for $i=2,\ldots,c$, but it doesn’t. The point is that the bad key
set from our lower bound in Theorem 7 is of the form $[0]^{c-2}\times[2]\times
A$ for some $A\subseteq\Sigma$, and then it is only the last character where
twisting makes a difference.

As a last point, recall tornado-mix which was designed to deal with larger
sets. There it only costs us a factor 2 when we let the last derived character
$\widetilde{x}_{c+d}$ depend only on
$\widetilde{x}_{1}\dots\widetilde{x}_{c+d-2}$ and not on
$\widetilde{x}_{c+d-1}$. This is essentially like switching to mixed
tabulation on the last two derived keys, hence the name _tornado-mix_. This
only works for the last two derived characters that can play a symmetric role.

The exponential dependence on $c$. We note that having an exponential
dependence on $c$ is symptomatic for almost all prior work on tabulation
hashing, starting from the original work in [31]. Above, we discussed how
tornado tabulation hashing avoided such exponential dependence on $c$ in the
error probability from mixed tabulation. The dependence on $c$ was
particularly destructive for mixed tabulation because it pushed the error
probability above 1 for the relevant parameters.

Concentration bounds. Tornado hashing inherits the strongest concentration
bounds known for mixed tabulation [22]. The reason is that they only require
one derived character and tornado tabulation can be seen as applying mixed
tabulation with one character to a derived tornado key with one less
character. Unlike our Lemma 6, which essentially only applies for expected
values $\mu\leq\left|\Sigma\right|/2$, the concentration bounds we get from
[22] work for unbounded $\mu$ and for both the upper and lower tail. They fall
exponentially in $\mu/K_{c}$ where $K_{c}$ is exponential in $c$, but this
still yields strong bounds when $\mu$ is large. Inheriting the strongest
concentration bound for mixed tabulation implies that tornado tabulation can
replace mixed tabulation in all the applications from [10] while improving on
the issue of local uniformity.

###  1.4 The power of locally uniform hashing

We now describe, on a high level, how the notion of locally uniform hashing
captures a type of randomness that is sufficient for many applications to work
almost as if they employed full randomness. For the discussion, we will assume
the parameters from Theorem 8 with tornado-mix. The main observation is that,
for many algorithms, the performance measure (i.e., its distribution) depends,
whp, only on the behavior of keys that hash inside a local neighborhood
defined via some selected bits of the hash value (the selection may depend
both on the algorithm and on the concrete input since the selection is only
used for analysis). Moreover, the set of keys $X^{f,h}$ that land in that
selected neighborhood has expected size $\leq\left|\Psi\right|/2$. For any
such neighborhood, our results imply that the keys in $X^{f,h}$ have fully
random free bits whp.

To understand the role of the free bits, it is helpful to think of hashing a
key $x$ as a two-stage process: the selector bits of $h(x)$ tell us whether
$x$ hashes in the desired neighborhood or not, while the remaining free bits
of $h(x)$ determine how $x$ hashes once it is _inside_ the neighborhood. This
suggests a general coupling, where we let both fully-random hashing and
tornado tabulation hashing first choose the select bits and then the free
bits. Since both are fully random on the free bits (for us with high
probability), the only difference is in the selection, but here concentration
bounds imply that we select almost the same number of keys as fully-random
hashing.

In [10], this approach was demonstrated for the HyperLogLog algorithm of
Flajolet, Fusy, Gandouet, Meunier [18] for counting distinct elements in data
streams, and the One-Permutation Hashing of Li, Owen, and Zhang [26] used for
fast set similarity in large scale machine learning. In [10] they implemented
the local uniformity with mixed tabulation, but with tornado hashing we get a
realistic implementation. This also includes later application of mixed
tabulation, e.g., the dynamic load balancing from [3]. Below, as a new
example, we illustrate how local uniformity makes classic linear probing
perform almost as if fully random hashing was used.

We briefly recall the basic version of linear probing. We employ an array T of
length $m$ and hash keys to array entries using a tornado tabulation hash
function $h:\Sigma^{c}\rightarrow[m]$. Thus, in Theorem 8, we have
$\mathcal{R}=[m]=[2^{r}]$. Upon insertion of a key $x$, we first check if
entry $T[h(q)]$ is empty. If it is, we insert the key in $T[h(q)]$. Otherwise,
we scan positions in $T$ sequentially starting with $T[h(q)+1]$ until we find
an empty position and store $x$ in this next available free entry. To search
for $x$, we inspect array entries sequentially starting with $T[h(q)]$ until
we find $x$ or we find an empty array entry, concluding that the key is not in
the array. The general concept that dominates the performance of linear
probing is the _run_ of $q$, which is defined as the longest interval
$I_{q}\subseteq[m]$ of full (consecutive) array entries that $h(q)$ is part
of. The run affects the probe length (the length of the interval from $h(q)$
till the end of $I_{q}$) and other monotone measures such as insertion and
deletion time (i.e., monotonically increasing in the number of keys). Thus,
any corresponding analysis depends only on the set $X_{q}$ of keys that fall
in the interval $I_{q}$, and it is there that we are interested in showing
full randomness.

The first step is to argue that the behavior of $I_{q}$ is local in nature, in
that it is affected only by the keys that hash in a fixed length interval
around $h(q)$. To that end, we show that, whp, the length of the run is no
bigger than a specific $\Delta=2^{\ell}$. This $\Delta$ implies locality:
consider the interval $J_{q}\subseteq[m]$, centered at $h(q)$, which extends
$\Delta$ entries in each direction, i.e.,
$J_{q}=\left\\{j\in[m]\mid\left|j-h(q)\right|\leq\Delta\right\\}$. Then, whp,
any run that starts outside $J_{q}$ is guaranteed to end by the time we start
the run of $q$. In other words, whp, the behavior of $I_{q}$ depends only on
the set $X_{q}$ of keys that hash inside the fixed length neighborhood $J_{q}$
(and specifically where in $J_{q}$ the keys hash). A similar argument can be
made for other variants of linear probing, such as linear probing with
tombstones [6], where the run/neighborhood must also take into account the
tombstones that have been inserted.

At this point, it is worthwhile pointing out that the set $X_{q}$ is no longer
a fixed set of keys but rather a random variable that depends on the
realization of $h(q)$. We cannot just apply Theorem 1. Nevertheless, in the
second step, we argue that $X_{q}$ can be captured by our notion of selector
functions. For this, we cover $J_{q}$ with three dyadic intervals, each of
length $\Delta$: one including $h(q)$ and the corresponding ones to the left
and to the right. Since each interval is dyadic, it is determined only by the
leftmost $r-\ell$ bits of the hash value: for example, an element
$x\in\Sigma^{c}$ hashes into the same dyadic interval as $q$ iff the leftmost
$r-\ell$ bits of $h(x)$ match those of $h(q)$. We can then design a selector
function that returns a $1$ if and only if $x$ is in the input set and the
leftmost $r-\ell$ bits of $h(x)$ (its selector bits) hash it into any of the
three specific dyadic intervals we care about. Such a selector function is
guaranteed to select all the keys in $X_{q}$. By setting $\Delta$
appropriately, we get that the expected size of the selected set is at most
$\Sigma/2$, and can thus apply Theorem 5. We get that inside the intervals,
keys from $X^{f,h}$ hash (based on their free bits) in a fully random fashion.

Finally, what is left to argue is that the number of keys hashing inside each
of the three dyadic intervals is not much bigger than what we would get if we
used a fully-random hash function for the entire set (one in which the
selector bits are also fully random). For this, we employ Lemma 6, and can
conclude that we perform almost as well with fully-random hashing. In
particular, from Knuth’s [25] analysis of linear probing with fully-random
hashing, we conclude that with load $(1-\varepsilon)$, the expected probe
length with tornado hashing is $(1+o(1))(1+1/\varepsilon^{2})/2$.

The above type of analysis could be applied to other variants of linear
probing, e.g., including lazy deletions and tombstones as in the recent work
of Bender, Kuszmaul, and Kuszmaul [6]. We would need to argue that the run,
including tombstones, remains within the selected neighborhood and that we
have concentration both on live keys and tombstones. However, since the
analysis from [6] is already based on simple hash functions, we would not get
new bounds from knowing that tornado hashing performs almost as well as fully-
random hashing.

###  1.5 Relation to high independence

The $k$-independence approach to hashing [37] is to construct hash functions
that map every set of $k$ keys independently and uniformly at random. This is
much stronger than getting fully random hashing for a given set and, not
surprisingly, the results for highly independent hashing [9, 33, 35] are
weaker. The strongest high independence result from [9] says that we get
$|\Sigma|^{1-\varepsilon}$-independent hashing in
$O((c/\varepsilon)\log(c/\varepsilon))$ time, but the independence is much
less than our $|\Sigma|/2$. Experiments from [1] found that even the simpler
non-recursive highly independent hashing from [35] was more than an order of
magnitude slower than mixed tabulation which is similar to our tornado
tabulation.

We also note that the whole idea of using derived characters to get linear
independence between keys came from attempts to get higher $k$-independence
Indeed, [15, 23, 36] derive their characters deterministically, guaranteeing
that we get $k$-independence. The construction for $k=5$ is efficient but for
larger $k$, the best deterministic construction is that from [36] using
$d=(k-1)(c-1)+1$ derived characters, which for larger $k$ is much worse than
the randomized constructions.

###  1.6 Relation to the splitting trick and to succinct uniform hashing

We will now describe how tornado-mix provides a much more efficient
implementation of the succinct uniform hashing by Pagh and Pagh [28] and the
splitting trick of Dietzfelbinger and Rink [13]. This further illustrates how
our work provides a component of wide applicability within hashing.

Succinct uniform hashing. The main contribution in [28] is to obtain uniform
hashing in linear space. The succinct construction is then obtained through a
general reduction from the linear-space case. They achieved uniform hashing in
linear space using the highly independent hashing of Siegel [33] as a
subroutine in combination with other ideas. Now, thanks to Theorem 8, we know
that tornado-mix offers an extremely simple and efficient alternative to
implement that. Indeed, if $n$ is the size of the set we want linear space
uniform hashing on, then setting $|\Psi|$ to the power of two just above $2n$
is sufficient to ensure the degree of independence that we need. Moreover, we
can set $\left|\Sigma\right|\sim\sqrt{\Psi}$ and $c$ so that we obtain (i)
$c|\Sigma|=o(|\Psi|)$ and (ii) setting $d=2c+1$ the probability bound in
Theorem 8 becomes $1-O(1/u)$ where $u$ is the size of the universe. The two
previous conditions ensure respectively that tornado-mix uses linear space and
that it is, whp, fully random.

The splitting trick. We now explain how our tornado-mix tabulation hashing
provides a very simple and efficient implementation of the splitting trick of
Dietzfelbinger and Rink [13] which is a popular method for simulating full-
randomness in the context of data structures, most notably various dictionary
constructions [14, 16, 19, 5]. This is an especially relevant application
because it usually requires hashing keys into a range of size $\Theta(n)$ and,
in this context, employing the uniform hashing of Pagh and Pagh [28] would be
too costly, i.e., (compared to the size of the overall data structure). This
trick was also used to obtain a simpler and exponentially faster
implementation of succinct uniform hashing [28]. We note that the splitting
idea had also been used earlier works of Dietzfelbinger and Meyer auf der
Heide [12] and Dietzfelbinger and Woelfel [15].

The idea is to first split the input set $S$ of size $n$ into $n^{1-\delta}$
subsets $S_{1},\ldots,S_{m}$, for some $\delta\in(0,1)$. The splitting is done
through a hash function $h_{1}:\Sigma^{c}\rightarrow[n^{1-\delta}]$ such that
$S_{i}$ is defined as all the keys in $S$ that hash to the same value, i.e.,
$S_{i}=\left\\{x\in S\mid h_{1}(x)=i\right\\}$. In many applications, we want
the splitting to be balanced, that is, we need a joint upper bound $s$ on all
set sizes with $s$ close to the expected size $n^{\delta}$. On top of this, we
need a shared hash function $h_{2}:\Sigma^{c}\to\mathcal{R}$ which with high
probability is fully random on each set $S_{i}$ and we ensure this with a hash
function that w.h.p. is fully random on any set of size at most $s$. The
problem is then solved separately for each subset (e.g., building
$n^{1-\delta}$ dictionaries, each responsible for just one subset $S_{i}$).

The above splitting trick can be easily done with tornado-mix hashing from
Theorem 8. The dominant cost for larger $s$ is two lookups in tables of size
at most $4s$. We let $h_{1}$ be the select bits (with the strong concentration
from Lemma 6) and $h_{2}$ as the remaining free bits. Getting both for the
price of one is nice, but the most important thing is that we get an efficient
implementation of the shared hash function $h_{2}$. Specifically, we compare
this with how $h_{1}$ and $h_{2}$ were implemented in [13] to get uniform
hashing. For the splitter $h_{1}$, instead of using Siegel’s [33] highly
independent hashing, [13, §3.1] uses that if $h_{1}$ has sufficiently high,
but constant, independence, then it offers good concentration (though not as
good as ours from Lemma 6).

The bigger issue is in the implementation of the shared $h_{2}$ from [13,
§3.2]. For this, they first employ a hash function
$f:[s]\to[s^{1+\varepsilon}]$ such that, whp, $f$ has at most $k=O(1)$ keys
that get the same hash value. For small $\varepsilon$ and $k$, this forces a
high independence of $f$. Next, for every $i\in[s^{1+\varepsilon}]$, they use
a $k$-independent hash function $g_{i}:\Sigma^{c}\to\mathcal{R}$, and finally,
$h_{2}$ is implemented as $g_{f(x)}(x)$. The space to implement $h_{2}$ is
dominated by the $O(s^{1+\varepsilon})$ space to store the $s^{1+\varepsilon}$
$k$-independent hash functions $g_{i}$, and time-wise, we have to run several
sufficiently independent hash functions. This should be compared with our
tornado-mix that only uses $O(s)$ space and runs in time corresponding to a
few multiplications (in tests with 32-bit keys).

###  1.7 Paper Organization

The remainder of our paper is structured as follows. In Section 2, we
introduce some notation, a more general notion of generalized keys and Lemma 9
(the corresponding version of Lemma 2 for them). Our main technical result,
Theorem 4, is proved in three steps: we first define obstructions, the main
combinatorial objects we study, in Section 3. In Section 4 we present a
simplified analysis of Theorem 4 that achieves a weaker error probability. We
then show in Section 5 a tighter analysis that finally achieves the desired
bound. The Chernoff bounds for the upper tail are proved in Section 6. The
details for the linear probing analysis can be found in Section 7. Finally,
the lower bound from Theorem 7 is proved in Section 8.

##  2 Preliminaries

#### Notation.

We use the notation $n!!=n(n-2)\cdots$. More precisely, $n!!=1$ for
$n\in\\{0,1\\}$, while $n!!=n(n-2)!!$ for $n>1$. For odd $n$, this is exactly
the number of perfect matchings of $n+1$ nodes. We use the notations

$\displaystyle n^{\underline{k}}$
$\displaystyle=n(n-1)\cdots(n+1-k)=n!/(n-k)!$ $\displaystyle
n^{\underline{\underline{k}}}$
$\displaystyle=n(n-2)\cdots(n+2(1-k))=n!!/(n-2k)!$

Here $n^{\underline{\underline{k}}}$ appears to be non-standard, though it
will be very useful in this paper in connection with something we will call
greedy matchings. We note that

$n^{\underline{\underline{k}}}\leq n^{\underline{k}}\leq n^{k}.$

#### Position characters and generalized keys.

We employ a simple generalization of keys going back to Pǎtraşcu and Thorup
[31]. Namely, a _position character_ is an element of $\\{1\dots
b\\}\times\Sigma$, e.g., where $b=c$ or $c+d$. Under this definition a key
$x\in\Sigma^{b}$ can be viewed as a set of $b$ position characters
$(1,x_{1})\dots(b,x_{b})$, and, in general, we consider _generalized keys_
that may be arbitrary subsets of $\\{1\dots b\\}\times\Sigma$. A natural
example of a generalized key is the symmetric difference $x\triangle y$ of two
(regular) keys. We then have that

$h(x)=h(y)\iff h(x\triangle y)=0.$

These symmetric differences will play an important role in our constructions,
and we shall refer to $x\triangle y$ as a _diff-key_. A diff-key is thus a
generalized key where we have zero or two characters in each position. For a
generalized key $x$, we can then define

$x[i]=\\{(i,a)\in x\\}\textnormal{,}\quad x[<i]=\\{(j,a)\in x\mid
j<i\\}\quad\textnormal{and}\quad x[\leq i]=\\{(j,a)\in x\mid j\leq i\\}.$

For example, if we have a regular key $x=x_{1},\ldots,x_{c}$, then
$x[i]=x_{i}$ and $x[\leq i]=x_{1}\ldots,x_{i}$. Also note that $(x\triangle
y)[\leq i]=x[\leq i]\triangle y[\leq i]$. We shall also apply this indexing to
sets $X$ of generalized keys by applying it to each key individually, e.g.,

$X[<i]=\\{x[<i]\mid x\in X\\}.$

#### Generalized keys and linear independence.

A generalized key $x$ can also be interpreted as a $(|\Sigma|\cdot
b)$-dimensional vector over $\mathbb{F}_{2}$, where the only entries set to
$1$ are those indexed by position characters in $x$. The generalized key
domain is denoted by $\mathbb{F}_{2}^{\\{1\dots b\\}\times\Sigma}$. Now, if we
have a simple tabulation hash function $h:\Sigma^{b}\to\mathcal{R}$ using
character tables $T_{1},\ldots,T_{b}$, then $h$ can be lifted to hash any
generalized key $x\in\mathbb{F}_{2}^{\\{1\dots b\\}\times\Sigma}$ by

$h(x)=\bigoplus_{(i,a)\in x}T_{i}[a].$

Thus $h$ provides a mapping $\mathbb{F}_{2}^{\\{1\dots b\\}\times\Sigma}$ to
$\mathcal{R}$.

As for (regular) keys, for a set $Y$ of generalized keys, we can then define
$\operatorname*{\scalerel*{\triangle}{\sum}}Y$ to be the set of position
characters that appear an odd number of times across the keys in $Y$. We then
say that $Y$ is a _zero-set_ if
$\operatorname*{\scalerel*{\triangle}{\sum}}Y=\emptyset$. We also say that $Y$
is _linearly dependent_ if it contains a subset which is a zero-set, and
_linearly independent_ otherwise. It is apparent then that a set of
generalized keys is linearly independent if and only if the set of their
vector representations is linearly independent. Indeed, the proof of Thorup
and Zhang [36] for Lemma 9 works quite directly in this generality. Thus we
have

######  Lemma 9 (Simple tabulation on linearly independent generalised keys).

Given a set of generalized keys $Y\subseteq\left(\mathbb{F}_{2}^{\\{1\dots
c\\}\times\Sigma}\right)$ and a simple tabulation hash function
$h:\Sigma^{c}\rightarrow\mathcal{R}$, the following are equivalent:

  1. (i)

$Y$ is linearly independent

  2. (ii)

$h$ is fully random on $Y$ (i.e., $h|_{Y}$ is distributed uniformly over
$\mathcal{R}^{Y}$).

##  3 Obstructions with simple tornado tabulation

We prove Theorem 4 by first considering a simpler version of tornado
tabulation hashing, which we call _simple tornado hashing_ , where we do not
change the last character of the (original) key. Formally, for a key
$x=x_{1}\cdots x_{c}$, its corresponding derived key
$\widetilde{x}=\widetilde{x}_{1}\ldots\widetilde{x}_{c+d}$ is computed as

$\widetilde{x}_{i}=\begin{cases}x_{i}&\text{if $i=1,\ldots,c$}\\\
\widetilde{h}_{i-c}\left(\widetilde{x}_{1}\dots\widetilde{x}_{i-1}\right)&\text{otherwise}.\end{cases}$

Note that, in the original tornado hashing, we had
$\widetilde{x}_{c}=x_{c}\oplus\widetilde{h}_{0}(\widetilde{x}_{1}\dots\widetilde{x}_{c-1})$.
Removing this extra step is thus equivalent to fixing
$\widetilde{h}_{0}(\cdot)=0$. While this step comes at almost no cost in the
code, it allows us to gain a factor of $3/\left|\Sigma\right|$ in the overall
error probability. See Section 5.3 for details. For the simple tornado
hashing, we will prove a slightly weaker probability bound.

For ease of notation, for every key $x$, we use $\widetilde{x}$ to denote the
corresponding derived key $\widetilde{h}(x)$; and likewise for any set of
keys. We also define $X=X^{f,h}$ to be the set of selected keys and
$\widetilde{X}=\tilde{h}(X)$. We want to argue that the derived selected keys
$\widetilde{X}$ are linearly independent with high probability. To prove this,
we assume that $\widetilde{X}$ is linearly dependent and hence, contains some
zero-set $\widetilde{Z}$. From $\widetilde{Z}$ we construct a certain type of
‘‘obstruction’’ that we show is unlikely to occur.

###  3.1 Levels and matchings

We first define some necessary concepts. We use the notion of _level_ $i$ to
refer to position $c+i$ in the derived keys. Let
$M\subseteq\binom{|\Sigma|^{c}}{2}$ be a (partial) matching on the keys
$\Sigma^{c}$.777Here, we mean the graph-theoretic definition of a matching as
a set of edges with disjoint endpoints. In our case, the vertices of the graph
are keys in $\Sigma^{c}$, and the edges of the matching are represented as
$\left\\{x,y\right\\}\in M$.  We say that $M$ is an _$i$ -matching_ if for all
$\\{x,y\\}\in M$, it holds that $\widetilde{x}[c+i]=\widetilde{y}[c+i]$,
namely if every pair of keys in $M$ matches on level $i$. Our obstruction
will, among other things, contain an $i$-matching $M_{i}$ for each level $i$.

Recall that a diff-key $x\triangle y$ is the symmetric difference of two keys
$x$ and $y$ in terms of their position characters. We then say that $M$ is an
_$i$ -zero, $i$-dependent, or $i$-independent_ matching if

$\textnormal{DiffKeys}(M,i)=\left\\{(\widetilde{x}\triangle\;\widetilde{y})[\leq
c+i]\mid\\{x,y\\}\in M\right\\}$

is a zero-set, linearly dependent, or linearly independent, respectively. In
other words, for each pair $\left\\{x,y\right\\}$ in the matching, we consider
the diff-key corresponding to the first $c+i$ characters of their derived
keys. We then ask if this set of diff-keys now forms a zero-set or contains
one as a subset, by looking at their (collective) symmetric difference. We
employ this notion to derive the probability that the function $\widetilde{h}$
satisfies a certain matching as such:

######  Lemma 10.

Let $M$ be a partial matching on $\Sigma^{c}$. Conditioning on $M$ being
$(i-1)$-independent, $M$ is an $i$-matching with probability
$1/|\Sigma|^{|M|}$.

###### Proof.

First, we notice that the event “$M$ is $(i-1)$-independent” only depends on
$\widetilde{h}_{j}$ for $j<i$. Then, by Lemma 9, when we apply the simple
tabulation hash function $\widetilde{h}_{i}:\Sigma^{c+i}\to\Sigma$ to the
linearly independent generalized key set $\textnormal{DiffKeys}(M,i-1)$, the
resulting hash values $\widetilde{h}(z)[c+i]$ for
$z\in\textnormal{DiffKeys}(M,i-1)$ are independent and uniform over $\Sigma$.
Hence, so are the resulting derived characters $\widetilde{h}(z)[c+i]$ for
$z\in\textnormal{DiffKeys}(M,i)$. The probability that they are all $0$ is
therefore $1/|\Sigma|^{|M|}$. ∎

Similarly, as for matchings, we say that a set of keys $Z\subseteq\Sigma^{c}$
is _$i$ -zero_, _$i$ -dependent, or $i$-independent_ if $\widetilde{Z}[\leq
c+i]$ is a zero-set, linearly dependent, or linearly independent,
respectively. We note the following relations:

######  Observation 11.

Let $M$ be a partial matching on $\Sigma^{c}$ and $Z=\bigcup M$. Then $M$ is
an $i$-zero matching iff $Z$ is an $i$-zero set. Furthermore, if $M$ is
$i$-dependent then $Z$ is also $i$-dependent (but not vice versa).

We will also make use of the following observation repeatedly:

######  Observation 12.

If $Z$ is an $i$-zero set, then there is a perfect $j$-matching on $Z$ for
every level $j\leq i$.

###  3.2 Constructing an obstruction

In this section, we show that whenever the set of selected derived keys
$\widetilde{X}$ is linearly dependent, it gives rise to a certain
_obstruction_. We now show how to construct such an obstruction.

Since $\widetilde{X}$ is linearly dependent, there must be some $d$-zero set
$Z\subseteq X$. We are going to pick a $d$-zero set that (1) minimizes the
number of elements contained that are not in the query set $Q$ and, subject to
(1), (2) minimizes the number of elements from $Q$ contained. In particular,
$Z$ is contained in $Q$ if $\widetilde{Q}$ is not linearly independent.

If $Z$ is not contained in $Q$, we let $x^{*}$ be any element from $Z\setminus
Q$. Then $Q\cup Z\setminus\\{x^{*}\\}$ must be linearly independent since any
strict subset $Z^{\prime}$ would contradict (1). If $Z$ is contained in $Q$,
then we let $x^{*}$ be an arbitrary element of $Z$.

#### The top two levels.

By Observation 12, we have a perfect $d$-matching $M^{*}_{d}$ and a perfect
$(d-1)$-matching $M^{*}_{d-1}$ on $Z$ (we also have perfect matchings on other
levels, but they will be treated later). These two perfect matchings partition
$Z$ into alternating cycles.

We will now traverse these cycles in an arbitrary order except that we
traverse the cycle containing $x^{*}$ last. For all but the last cycle, we
start in an arbitrary vertex and its cycle starting with the edge from
$M^{*}_{d-1}$. When we get to the last cycle, we start at the $M^{*}_{d}$
neighbor of $x^{*}$ and follow the cycle from the $M^{*}_{d-1}$ neighbor of
this key. This ensures that $x^{*}$ will be the very last vertex visited. The
result is a traversal sequence $x_{1},\ldots,x_{|Z|}$ of the vertices in $Z$
ending in $x_{|Z|}=x^{*}$. Note that $M^{*}_{d-1}$ contains the pairs
$\\{x_{1},x_{2}\\},\\{x_{3},x_{4}\\},\ldots$. For $M^{*}_{d}$ it is a bit more
complicated, since its pairs may be used to complete a cycle (and hence are
not visible in the traversal).

We now define $W=\\{x_{1}\dots x_{w}\\}$ to be the shortest prefix of
$x_{1}\dots x_{|Z|}$ such that $M^{*}_{d-1}$ restricted to the keys in $W$ is
a $(d-1)$-dependent matching, i.e., we go through the pairs
$\left\\{x_{1},x_{2}\right\\},\left\\{x_{3},x_{4}\right\\},\ldots$ until the
set of their diff-keys (up to level $d-1$) contains a zero-set. Note that such
a $W\subseteq Z$ always exists because $M^{*}_{d-1}$ itself is a $(d-1)$-zero
matching. Also note that $W\setminus\\{x_{w}\\}\subseteq
Z\setminus\\{x^{*}\\}$. Let $e_{d-1}:=\\{x_{w-1},x_{w}\\}$ be the last pair in
the prefix, and as $e_{d-1}\in M^{*}_{d-1}$, we get that $w$ is even. We then
define $M_{d-1}$ to be the restriction of $M^{*}_{d-1}$ to the keys in $W$ and
$M_{d}$ to be the restriction of $M^{*}_{d}$ to the keys in
$W\setminus\left\\{x_{w}\right\\}$. Note that $M_{d-1}$ is a perfect matching
on $W$ while $M_{d}$ is a maximal matching on $W\setminus\\{x_{w}\\}$. Since
$M_{d-1}$ is $(d-1)$-dependent, we can define a submatching $L_{d-1}\subseteq
M_{d-1}$ such that $L_{d-1}$ is a $(d-1)$-zero matching (this corresponds
exactly to the subset of $\textnormal{DiffKeys}(M_{d-1},d-1)$ that is a zero-
set). By construction, $e_{d-1}\in L_{d-1}$. Finally, we set $Z_{d-1}=\bigcup
L_{d-1}$ and notice that $Z_{d-1}$ is an $(d-1)$-zero key set (by Observation
11).

#### A special total order.

We now define a special new total order $\preceq$ on $\Sigma^{c}$ that we use
in order to index the keys in $W$ and describe matchings on levels $<d-1$.
Here $x_{w}$ has a special role and we place it in a special position; namely
at the end. More precisely, we have the natural $\leq$-order on $\Sigma^{c}$,
i.e, in which keys are viewed as numbers $<|\Sigma|^{c}$. We define $\preceq$
to be exactly as $\leq$ except that we set $x_{w}$ to be the largest element.
Moreover, we extend the total order $\preceq$ to disjoint edges in a matching
$M$: given $\\{x_{1},x_{2}\\},\\{y_{1},y_{2}\\}\in M$, we define
$\\{x_{1},x_{2}\\}\preceq\\{y_{1},y_{2}\\}$ if and only if $\min
x_{i}\prec\min_{i}y_{i}$.

#### Lower levels.

Now for $i=d-2\dots 0$, we do the following: from level $i+1$, we have an
$(i+1)$-zero set $Z_{i+1}$. By Observation 12, there exists a perfect
$i$-matching $M_{i}^{*}$ over $Z_{i+1}$. Notice that $M^{*}_{i}$ is an
$i$-zero matching. We define $M_{i}$ as the shortest prefix (according to
$\preceq$) of $M^{*}_{i}$ that is $i$-dependent. Denote by $e_{i}$ the
$\preceq$-maximum edge in $M_{i}$. Define the submatching $L_{i}\subseteq
M_{i}$ such that $L_{i}$ is an $i$-zero set. By construction, $e_{i}\in
L_{i}$. Finally, we set $Z_{i}=\bigcup L_{i}$ and notice that $Z_{i}$ is an
$i$-zero set.

###  3.3 Characterizing an obstruction

Our main proof strategy will be to show that an obstruction is unlikely to
happen, implying that our selected derived keys $\widetilde{X}$ are unlikely
to be linearly dependent. To get to that point, we first characterize such an
obstruction in a way that is independent of how it was derived in Section 3.2.
With this classification in hand, we will then be able to make a union bound
over all possible obstructions.

Corresponding to the two top levels, our obstruction consists of the following
objects:

  * •

A set of keys $W\subseteq\Sigma^{c}$ of some size $w=|W|$.

  * •

A special key $x_{w}\in W$, that we put last when we define $\preceq$.

  * •

A maximal matching $M_{d}$ on $W\setminus\\{x_{w}\\}$.

  * •

A perfect matching $M_{d-1}$ on $W$, where $e_{d-1}$ is the only edge in
$M_{d-1}$ incident to $x_{w}$.

  * •

A submatching $L_{d-1}\subseteq M_{d-1}$, which includes $e_{d-1}$, and its
support $Z_{d-1}=\bigcup L_{d-1}$.

Note that the above objects do not include the whole selected set $X^{f,h}$,
the $d$-zero set $Z$, or the perfect matchings $M_{d-1}^{*},M_{d}^{*}$ that we
used in our construction of the obstruction. Also, note that thus far, the
objects have not mentioned any relation to the hash function $h$.

To describe the lower levels, we need to define greedy matchings. We say a
matching $M$ on a set $Y$ is _greedy_ with respect to the total order
$\preceq$ on $Y$ if either: (i) $M=\emptyset$ or; (ii) the key
$\min_{\preceq}Y$ is incident to some $e\in M$ and $M\setminus\\{e\\}$ is
greedy on $Y\setminus e$. Assuming that $|Y|$ is even, we note that $M$ is
greedy if and only if it is a prefix of some $\preceq$-ordered perfect
matching $M^{*}$ on $Y$.

For the lower levels $i=d-2,\ldots,1$, we then have the following objects:

  * •

A greedy matching $M_{i}$ on $Z_{i+1}$. Denote with $e_{i}$ the
$\preceq$-maximum edge in $M_{i}$.

  * •

A submatching $L_{i}\subseteq M_{i}$ which includes $e_{i}$, and its support
$Z_{i}=\bigcup L_{i}$.

Note that the above objects describe all possible obstructions that we might
construct. Moreover, any obstruction can be uniquely described as the tuple of
objects

$(W,x_{w},M_{d},M_{d-1},e_{d-1},L_{d-1},Z_{d-1},\ldots
M_{1},e_{1},L_{1},Z_{1})\;.$

###  3.4 Confirming an obstruction

In order for a given obstruction to actually occur, the tornado tabulation
hash function $h=\widehat{h}\circ\widetilde{h}$ must satisfy the following
conditions with respect to it:

  * •

The keys in $W$ are all selected, that is, $W\subseteq X^{f,h}$.

  * •

Either $W\subseteq Q$ or $Q\cup W\setminus\\{x_{w}\\}$ is $d$-independent.

  * •

For $i=1,\ldots,d$, $M_{i}$ is an $i$-matching.

  * •

$M_{d}$ is $(d-1)$-independent.

For $i=1,\ldots,d-1$,

  * •

$M_{i}\setminus\\{e_{i}\\}$ is $(i-1)$-independent.

  * •

The submatching $L_{i}$ is $i$-zero (implying that $Z_{i}=\bigcup L_{i}$ is an
$i$-zero set).

When a hash function $h$ satisfies the above conditions, we say that it
_confirms_ an obstruction. We now need to argue two things. We need (1) to
verify that our construction of an obstruction from Section 3.2 satisfies
these conditions on $h$, and (2) that, given a fixed obstruction, the
probability that a random $h$ confirms the obstruction is very small. This is
captured by the two lemmas below.

######  Lemma 13.

The obstruction constructed in Section 3.2 satisfies the conditions on
$h=\widehat{h}\circ\widetilde{h}$.

###### Proof.

Since $W\setminus\\{x_{w}\\}\subseteq Z\setminus\\{x^{*}\\}$, the choice of
$Z$ implies that either $W\subseteq Q$ or $Q\cup W\setminus\\{x_{w}\\}$ is
$d$-independent.

The matchings $M_{i}$ were all submatchings of perfect $i$-matchings. We also
picked $M_{i}$ is minimally $i$-dependent, but for an $i$-matching $M_{i}$
this also implies that $M_{i}$ is minimally $(i-1)$-dependent, and therefore
$M_{i}\setminus\\{e_{i}\\}$ is $(i-1)$-independent. Finally, we constructed
$L_{i}$ and $Z_{i}$ to be $i$-zero. ∎

######  Lemma 14.

Given the objects of an obstruction, the probability that
$h=\widehat{h}\circ\widetilde{h}$ confirms the obstruction is at most

$\left(\prod_{x\in
W\setminus\\{x_{w}\\}}p_{x}\right)\bigg{/}|\Sigma|^{w-2+\sum_{i=1}^{d-2}(|M_{i}|-1)}.$

###### Proof.

For simplicity, we group the conditions above in the following events: we
define the event $\mathcal{C}_{S}$ to be the event that
$W\setminus\\{x_{w}\\}\subseteq X^{f,h}$ given that the set
$W\setminus\\{x_{w}\\}$ is $d$-independent. Then, for each
$i\in\left\\{1,\ldots,d-1\right\\}$, we define $\mathcal{C}^{(i)}$ to be the
event that $M_{i}\setminus e_{i}$ is an $i$-matching conditioned on the fact
that it is $(i-1)$-independent. Finally, we define the last event
$\mathcal{C}^{(d)}$ to be the event that $M_{d}$ is a $d$-matching conditioned
on the fact that it is $(d-1)$-independent. It is then sufficient to show
that:

$\Pr\left(\mathcal{C}_{S}\wedge\bigwedge_{i=1}^{d}\mathcal{C}^{(i)}\right)\leq\left(\prod_{x\in
W\setminus\\{x_{w}\\}}p_{x}\right)\bigg{/}|\Sigma|^{w-2+\sum_{i=1}^{d-2}(|M_{i}|-1)}.$

We proceed from the bottom up, in the following sense. For every
$i\in\left\\{1,\ldots,d-1\right\\}$, the randomness of the event
$\mathcal{C}^{(i)}$ conditioned on $\bigwedge_{j=1}^{i-1}\mathcal{C}^{(j)}$
depends solely on $\widetilde{h}_{i}$. We invoke Lemma 10 for $M_{i}\setminus
e_{i}$ and get that

$\Pr\left(\mathcal{C}^{(i)}\text{ }\Big{|}\text{
}\bigwedge_{j=1}^{i-1}\mathcal{C}^{(j)}\right)\leq
1/\left|\Sigma\right|^{\left|M_{i}\right|-1}\;.$

When it comes to level $d$, from Lemma 10 applied to $M_{d}$, we get that the
probability of $\mathcal{C}^{(d)}$ conditioned on
$\bigwedge_{j=1}^{d-1}\mathcal{C}^{(j)}$ is at most
$1/\left|\Sigma\right|^{\left|M_{d}\right|}$. We now notice that
$\left|M_{d-1}\right|+\left|M_{d}\right|=w-1$ by construction, and so:

$\displaystyle\Pr\left(\bigwedge_{j=1}^{d}\mathcal{C}^{(j)}\right)$
$\displaystyle\leq
1/\left|\Sigma\right|^{w-2+\sum_{i=1}^{d-2}(\left|M_{i}\right|-1)}\;.$

Finally, we know that either $W\subseteq Q$ or $Q\cup W\setminus\\{x_{w}\\}$
is $d$-independent. If $W\subseteq Q$, then $p_{x}=1$ for all $x\in W$, and
therefore, trivially,

$\Pr\left(\mathcal{C}_{S}\text{ }\Big{|}\text{
}\bigwedge_{j=1}^{d}\mathcal{C}^{(j)}\right)\leq\prod_{x\in
W\setminus\left\\{x_{w}\right\\}}p_{x}=1\;.$

Otherwise $Q\cup W\setminus\\{x_{w}\\}$ is $d$-independent. This means that
the derived keys $\widetilde{h}(Q\cup W\setminus\\{x_{w}\\})$ are linearly
independent. We can then apply Lemma 9 to this set of derived keys and the
final simple tabulation hash function $\widehat{h}$. We get that the final
hash values $h(Q\cup W\setminus\\{x_{w}\\})$ are chosen independently and
uniformly at random. For any one element $x$, by definition, $\Pr\left(x\in
X^{f,h}\right)\leq p_{x}$ and so:

$\Pr\left(\mathcal{C}_{S}\text{ }\Big{|}\text{
}\bigwedge_{j=1}^{d}\mathcal{C}^{(j)}\right)\leq\prod_{x\in
W\setminus\left\\{x_{w}\right\\}}p_{x}\;.$

This completes the claim. ∎

##  4 Simplified analysis

In this section, we present a simplified analysis showing that, under the
hypotheses of our theorem, $\widetilde{h}(X^{f,h})$ is linearly dependent with
probability at most $\Theta(\mu^{3}(17/|\Sigma|)^{d})+2^{-|\Sigma|/8}$. Later,
we will replace $(17/|\Sigma|)^{d}$ with $(3/|\Sigma|)^{d}$, which essentially
matches the growth in our lower bound.

For now we use a fixed limit $w_{0}=|\Sigma|/2^{5/2}$ on the set size $w=|W|$.
With this limited set size, we will derive the
$\Theta(\mu^{3}(17/|\Sigma|)^{d})$ bound. The $2^{-|\Sigma|/8}$ bound will
stem for sets of bigger size and will be derived in a quite different way.

Our goal is to study the probability that there exists a combinatorial
obstruction agreeing with a random tornado hash function $h$; if not,
$\widetilde{h}(X^{f,h})$ is linearly independent. To do this, we consider a
union bound over all combinatorial obstructions as such:

$\sum_{W,x_{w},M_{d},M_{d-1},e_{d-1},L_{d-1},Z_{d-1},\ldots
M_{1},e_{1},L_{1},Z_{1}}\Pr_{h}[h\textnormal{ confirms the obstruction}]$ (4)

The above sum is informally written in that we assume that each element
respects the previous elements of the obstruction, e.g., for $i<d-2$, $M_{i}$
is a greedy matching over $Z_{i+1}$. Likewise, in the probability term, it is
understood that $h$ is supposed to confirm the obstruction whose combinatorial
description is $({W,x_{w},M_{d},M_{d-1},e_{d-1},L_{d-1},Z_{d-1},\ldots
M_{1},e_{1},L_{1},Z_{1}})$ .

Using Lemma 14, we bound (4) by

$\displaystyle\sum_{W,x_{w},M_{d},M_{d-1},e_{d-1},L_{d-1},Z_{d-1},\ldots
M_{1},e_{1},L_{1},Z_{1}}\left(\prod_{x\in
W\setminus\\{x_{w}\\}}p_{x}\right)\bigg{/}|\Sigma|^{w-2+\sum_{i=1}^{d-2}(|M_{i}|-1)}$
$\displaystyle\rule{28.45274pt}{0.0pt}\leq\left(\sum_{W,x_{w},M_{d},M_{d-1},e_{d-1},L_{d-1},Z_{d-1}}\left(\prod_{x\in
W\setminus\\{x_{w}\\}}p_{x}\right)|\Sigma|^{2-w}2^{w/4-1}\right)$ (5)
$\displaystyle\rule{56.9055pt}{0.0pt}{{\times}}\prod_{i=1}^{d-2}\max_{Z_{i+1}}\left(\sum_{M_{i},e_{i},L_{i},Z_{i}}|\Sigma|^{1-|M_{i}|}\bigg{/}2^{(|Z_{i+1}|-|Z_{i}|)/4}\right).$
(6)

Above , $W,x_{w},M_{d},M_{d-1},e_{d-1},L_{d-1},Z_{d-1}$ are all the elements
from the top two levels and we refer to (5) as the ‘‘top’’ factor. We refer to
Equation (6) as the ‘‘bottom’’ factor which is the product of ‘‘level’’
factors.

For each lower level $i\leq d-2$, the elements $M_{i},e_{i},L_{i},Z_{i}$ are
only limited by $Z_{i+1}$, so for a uniform bound, we just consider the
maximizing choice of $Z_{i+1}$. For this to be meaningful, we divided the
level factor (6) by $2^{(|Z_{i+1}|-|Z_{i}|)/4}$ and multiplied (5) by
$2^{w/4-1}\geq\prod_{i=1}^{d-2}2^{(|Z_{i+1}|-|Z_{i}|)/4}$. This inequality
follows because $|Z_{d-1}|\leq w$ and $|Z_{1}|\geq 4$. The exponential
decrease in $|Z_{i+1}|$ helps ensuring that the maximizing choice of $Z_{i+1}$
has bounded size (and is not infinite). We note here that our bound $|W|\leq
w_{0}=|\Sigma|/2^{5/2}$ is only needed when bounding the level factors, where
it implies that $|Z_{i+1}|\leq w_{0}$.

###  4.1 The top two levels and special indexing for matchings and zero sets

We now wish to bound the top factor (5) from the two top levels. Below, we
will first consider $w$ fixed. Later we will sum over all relevant values of
$w$.

We want to specify the $w$ keys in $W$ using the fact that the keys from
$W\setminus\\{x_{w}\\}$ hash independently. Thus, we claim that we only have
to specify the set $V=W\setminus\\{x_{w}\\}$, getting $x_{w}$ for free. By
construction, we have $x_{w}$ in the zero-set $Z_{d-1}$, so

$x_{w}=\operatorname*{\scalerel*{\triangle}{\sum}}(Z_{d-1}\setminus\\{x_{w}\\}).$
(7)

To benefit from this zero-set equality, we need the special ordering $\preceq$
from the construction. It uses the standard ordering $\leq$ of $V$ since all
these keys are known, and then it just places the yet unknown key $x_{w}$
last. The special ordering yields and indexing $x_{1}\prec
x_{2}\prec\cdots\prec x_{w}$ (this is not the order in which we traversed the
cycles in the construction except that $x_{w}$ is last in $W$ in both cases).
Formally, we can now specify all the $M_{i},L_{i},Z_{i}$ over the index set
$\\{1,\ldots,w\\}$. For $i<w$, we directly identify $x_{i}$ as the $i$th
element in $V$. This way we identify all $x_{i}\in
Z_{d-1}\setminus\\{x_{w}\\}$, and then we can finally compute the special last
key $x_{w}$; meaning that we completely resolve the correspondance between
indices and keys in $W$. As a result, we can bound (5) by

$\sum_{V:|V|=w-1}\left(\prod_{x\in
V}p_{x}\right)\times\sum_{M_{d},M_{d-1},e_{d-1},L_{d-1},Z_{d-1}}|\Sigma|^{2-w}2^{w/4-1}.$

For the first part, with $v=w-1$, we have

$\sum_{V:\,|V|=v}\left(\prod_{x\in
V}p_{x}\right)=\frac{1}{v!}\sum_{(x_{1},\ldots,x_{v})}\prod_{i=1}^{v}p_{x_{i}}\leq\frac{1}{v!}\prod_{i=1}^{v}(\sum_{x}p_{x})=\frac{\mu^{v}}{v!}.$
(8)

For the second part, we note $M_{d-1}$ and $M_{d}$ can both be chosen in
$(w-1)!!$ ways and we know that $e_{d-1}$ is the edge in $M_{d-1}$ incident to
$w$. Since the submatching $L_{d-1}$ of $M_{d-1}$ contains the known
$e_{d-1}$, it can be chosen in at most $2^{|M_{d-1}|-1}=2^{w/2-1}$ ways.
Putting this together, we bound (5) by

$\displaystyle\frac{\mu^{w-1}}{(w-1)!}((w-1)!!)^{2}\,2^{w/2-1}|\Sigma|^{-w+2}2^{w/4-1}=\frac{\mu^{w-1}}{|\Sigma|^{w-2}}\cdot\frac{(w-1)!!}{(w-2)!!}\cdot
2^{3w/4-2}$
$\displaystyle\leq\frac{\mu^{3}}{|\Sigma|^{2}}2^{4-w}\cdot\frac{(w-1)!!}{(w-2)!!}\cdot
2^{3w/4-2}=\frac{\mu^{3}}{|\Sigma|^{2}}\cdot\frac{(w-1)!!}{(w-2)!!}\cdot
2^{2-w/4}$ (9)

Above we got to the second line using our assumption that $\mu\leq|\Sigma|/2$.
This covers our top factor (5), including specifying the set $Z_{d-1}$ that we
need for lower levels.

#### Union bound over all relevant sizes.

We will now sum our bound (9) for a fixed set size $w$ over all relevant set
sizes $w\leq w_{0}$, that is, $w=4,6,\ldots,w_{0}$. The factor that depends on
$w$ is

$f(w)=\frac{(w-1)!!}{(w-2)!!}/2^{w/4}.$

We note that $f(w+2)=f(w)\frac{w+1}{\sqrt{2}w}$ and
$\frac{w+1}{\sqrt{2}w}<4/5$ for $w\geq 8$, so

$\sum_{\textnormal{Even }w=4}^{w_{0}}f(w)<f(4)+f(6)+5f(8)<4.15.$

Thus we bound the top factor (5) over all sets $W$ of size up to $w_{0}$ by

$\sum_{\textnormal{Even
}w=4}^{w_{0}}\left(\frac{\mu^{3}}{|\Sigma|^{2}}\cdot\frac{(w-1)!!}{(w-2)!!}\cdot
2^{2-w/4}\right)<16.6(\mu^{3}/|\Sigma|^{2}).$ (10)

###  4.2 Lower levels with greedy matchings

We now focus on a lower level $i\leq d-2$ where we will bound the level factor

$\max_{Z_{i+1}}\left(\sum_{M_{i},e_{i},L_{i},Z_{i}}|\Sigma|^{1-|M_{i}|}\bigg{/}2^{(|Z_{i+1}|-|Z_{i}|)/4}\right).$
(11)

We want a bound of $O(1/|\Sigma|)$, implying a bound of $O(1/|\Sigma|)^{d-2}$
for all the lower levels in (6).

All that matters for our bounds is the cardinalities of the different sets,
and we set $m_{i}=|M_{i}|$ and $z_{i}=|Z_{i}|$. For now we assume that
$z_{i+1}\leq w_{0}$ and $m_{i}$ are given.

######  Lemma 15.

With a given linear ordering over a set $S$ of size $n$, the number of greedy
matchings of size $k$ over $S$ is $(n-1)^{\underline{\underline{k}}}$.

###### Proof.

We specify the edges one at the time. For greedy matchings, when we pick the
$j$th edge, the first end-point is the smallest free point in $S$ and then
there are $n-2j-1$ choices for its match, so the number of possible greedy
matchings of size $k$ is $(n-1)^{\underline{\underline{k}}}$. ∎

Recall that $e_{i}$ denotes the last edge in our greedy matching $M_{i}$ and
that $e_{i}\in L_{i}$. In our case, we are only going to specify
$M_{i}^{\prime}=M_{i}\setminus\\{e_{i}\\}$ and
$L_{i}^{\prime}=L_{i}\setminus\\{e_{i}\\}$. The point is that if we know
$M_{i}^{\prime}$ and $L_{i}^{\prime}$, then we can compute $e_{i}$. More
precisely, we know that $e_{i}$ is the next greedy edge to be added to
$M^{\prime}_{i}$, so we know its first end-point $x$. We also know that
$Z_{i}=\bigcup L_{i}$ is a zero-set, so the other end-point can be computed as
key

$y=\operatorname*{\scalerel*{\triangle}{\sum}}(\\{x\\}\cup\bigcup
L_{i}^{\prime})$ (12)

Above we note that even though the keys in $x$ and $L^{\prime}_{i}$ are only
specified as indices, we know how to translate between keys and indices, so we
can compute the key $y$ and then translate it back to an index.

By Lemma 15, we have $(z_{i+1}-1)^{\underline{\underline{m_{i}-1}}}$ choices
for $M^{\prime}_{i}$, and then there are $2^{m_{i}-1}$ possible submatchings
$L^{\prime}_{i}\subset M_{i}^{\prime}$. The number of combinations for
$M_{i},e_{i},L_{i}$ is thus bounded by

$(z_{i+1}-1)^{\underline{\underline{m_{i}-1}}}\cdot 2^{m_{i}-1}.$

We want to multiply this by

$|\Sigma|^{1-m_{i}}/2^{(z_{i+1}-z_{i})/4}.$

Here $z_{i}=2|L_{i}|\leq 2m_{i}$, so we get a bound of

$(z_{i+1}-1)^{\underline{\underline{m_{i}-1}}}\cdot(2^{3/2}/|\Sigma|)^{m_{i}-1}/2^{z_{i+1}/4-1/2}\leq
2^{1/2}(2^{3/2}z_{i+1}/|\Sigma|)^{m_{i}-1}/2^{z_{i+1}/4}.$ (13)

We now note that

$(2^{3/2}z_{i+1}/|\Sigma|)\leq 1/2.$

since $z_{i+1}\leq w\leq w_{0}=|\Sigma|/2^{5/2}$. Having this factor bounded
below 1 is critical because it implies that the term decreases as $m_{i}$
grows.

Still keeping $z_{i+1}$ fixed, we will now sum over all possible values of
$m_{i}$. Since $M_{i}$ contains a zero-matching $L_{i}$ of size at least 2,
that is 2 edges covering 4 keys, we have that $m_{i}\geq 2$. Moreover, the
terms of the summation are halving, hence they sum to at most twice the
initial bound, so we get

$\sum_{m_{i}\geq
2}2^{1/2}(2^{3/2}z_{i+1}/|\Sigma|)^{m_{i}-1}/2^{z_{i+1}/4}\leq
2^{3/2}(2^{3/2}z_{i+1}/|\Sigma|)/2^{z_{i+1}/4}.$ (14)

The maximizing real value of $z_{i+1}$ is $4/\ln 2=5.77$, but $z_{i+1}$ also
has to be an even number, that is, either 4 or 6, and 6 yeilds the maximum
bound leading to the overall bound of $16.98/|\Sigma|$ for (6). Together with
our bound (10), we get a total bound of

$16.6(\mu^{3}/|\Sigma|^{2})\cdot(17/|\Sigma|)^{d-2}.$ (15)

###  4.3 Large set sizes

We now consider sets $W$ of sizes $w>w_{0}$. In this case, we will only
consider the two top levels of the obstructions. Recall that we have a cycle
traversal $x_{1},\ldots,x_{w}$. If $w>w_{0}$, we only use the prefix
$x_{1},\ldots,x_{w_{0}}$, where we require that $w_{0}$ is even. The two
matchings $M_{d}$ and $M_{d-1}$ are reduced accordingly. Then $M_{d-1}$ is a
perfect matching on $W_{0}=\\{x_{1},\ldots,x_{w_{0}}\\}$ while $M_{d}$ is
maximal excluding $x_{w_{0}}$. Each of these matchings can be chosen in
$(w_{0}-1)!!$ ways.

This time we know that we have full independence. We know that
$\widetilde{W}_{0}$ is a strict subset of the original minimimal zero set
$\widetilde{Z}$ of derived keys, so the keys in $W_{0}$ all hash
independently. Therefore the probability that they are all selected is bounded
by $\prod_{x\in W_{0}}p_{x}$.

Also, since we terminate the traversal early, we know that $M_{d-1}$ is
$(d-2)$-linearly independent, and $M_{d}$ must be $d-2$-linearly independent,
so the probability that these two matchings are satisfied is
$1/|\Sigma|^{|M_{d-1}|+|M_{d}|}\leq 1/|\Sigma|^{w_{0}-1}$.

The total bound for all $w>w_{0}=|\Sigma|/2^{5/2}$ is now

$\displaystyle\sum_{W_{0}:\,|W_{0}|=w_{0},M_{d},M_{d-1}}\left(\prod_{x\in
W_{0}}p_{x}\right)/|\Sigma|^{w_{0}-1}$
$\displaystyle\leq\frac{\mu^{w_{0}}}{w_{0}!}((w_{0}-1)!!)^{2}/|\Sigma|^{w_{0}-1}\leq
w_{0}|\Sigma|/2^{w_{0}}$ (16) $\displaystyle\leq 1/2^{|\Sigma|/8}.$ (17)

The last step holds easily for $|\Sigma|\geq 256$. We note that (16) holds for
any choice of $w_{0}$, limiting the probability of any obstruction with
$|W|<w$.

##  5 Tighter analysis

We will now tighten the analysis to prove that

See 5

###  5.1 Bottom analysis revisited

We first tigthen the analysis of the bottom factor (6) so as to get a bound of
$O((3/\Sigma)^{d-2})$ and, together with our top bound (10), obtain an overall
bound of $O(\mu^{3}(3/\Sigma)^{d})$ matching our lower bound within a constant
factor. We are still using our assumption that $w\leq
w_{0}\leq|\Sigma|/2^{5/2}$ implying that $z_{i+1}\leq|\Sigma|/2^{5/2}$.

First we look at a single level $i$. For a tighter analysis of the level
factor (11), we partition into cases depending on $z_{i+1}$ and to some degree
on $z_{i}=2m_{i}$. Recall that $z_{i+1}$ is given from the level above.

If $z_{i+1}\leq 6$, then we must have $z_{i}=z_{i+1}$, since we cannot split
into two zero sets each of size at least 4. This implies that the factor
$2^{|Z_{i+1}|-|Z_{i}|}$ is just one. Also, in this case, $M_{i}=L_{i}$ must be
a perfect matching on $Z_{i+1}=Z_{i}$, and such a perfect matching can be in
$(z_{i+1}-1)!!$ ways. Thus, for given $z_{i+1}\leq 6$, we bound the level
factor by

$(z_{i+1}-1)!!/|\Sigma|^{z_{i+1}/2-1}\leq 3/|\Sigma|.$ (18)

with equality for $z_{i+1}=4$. As a result, if $z_{d-1}\leq 6$, then we have
already achieved a bound of $(3/|\Sigma|)^{d-2}$ for the bottom factor.

#### Split levels.

We now consider $z_{i+1}\geq 8$. Now it is possible that $Z_{i+1}$ can split
into two sets so that $z_{i}<z_{i+1}$. For a given $m_{i}$ and $z_{i+1}$, we
already had the bound (13)

$2^{1/2}(2^{3/2}z_{i+1}/|\Sigma|)^{m_{i}-1}/2^{z_{i+1}/4}.$

Since $(2^{3/2}z_{i+1}/|\Sigma|)\leq 1/2$, the worst case is achieved when
$m_{i}=2$, but here we can do a bit better. In (13) we had a factor
$2^{m_{i}-1}$ to specify the subset $L_{i}$ of $M_{i}$ containing $e_{i}$, but
since $L_{i}$ should have size at least $4$, we have $L_{i}=M_{i}$. Thus, for
$m_{i}=2$ and given $z_{i+1}$, we improve (13) to

$2(z_{i+1}/|\Sigma|)/2^{z_{i+1}/4}.$

For $z_{i+1}\geq 8$, this is maximized with $z_{i+1}=8$. Thus for $m_{i}=2$
and $z_{i+1}\geq 8$, the level factor (11) is bounded by

$(2\cdot 8/|\Sigma|)/2^{2}=4/|\Sigma|.$

Now, for $m_{i}\geq 3$, we just use the bound (13). As in (14), we get

$\sum_{m_{i}\geq
3}2^{1/2}(2^{3/2}z_{i+1}/|\Sigma|)^{m_{i}-1}/2^{z_{i+1}/4}\leq 2\cdot
2^{1/2}(2^{3/2}z_{i+1}/|\Sigma|)^{2}/2^{z_{i+1}/4}$

Over the reals, this is maximized with $z_{i+1}=2\cdot 4/\ln 2\approx 11.52$,
but we want the maximizing even $z_{i+1}$ which is $12$, and then we get a
bound of $1.6/|\Sigma|$.

We now want to bound the whole bottom factor in the case where $z_{d-1}\geq
8$. Let $j$ be the lowest level with $z_{j+1}\geq 8$. For all lower levels, if
any, the level factor is bounded by $(3/|\Sigma|)$. Also, for all higher
levels $i>j$, we have $2m_{i}=z_{i}\geq 8$, hence $m_{i}\geq 4$, so the level
factor for higher levels is bounded by our last $1.6/|\Sigma|$. The worst case
is the level $j$, where we could get any $m_{s}$ (note that if $s=1$, we have
no guarantee that $m_{i}\leq 2$), hence we have to add the bound $4/|\Sigma|$
for $m_{s}=2$ with the bound $1.6|\Sigma|$ for $m_{s}\geq 3$, for a total
bound of $5.6/|\Sigma|$.

Thus, for a given $j$, the bottom factor is bounded by

$(3/|\Sigma|)^{j-1}(5.6/|\Sigma)(1.6/|\Sigma|)^{d-2-j}=(3/|\Sigma|)^{d-2}*(5.6/3)*(1.6/3)^{d-2-j}.$

Summing, this over $j=1,\ldots,d-2\geq 1$, we get a bound of at most

$(3/|\Sigma|)^{d-2}(5.6/3)(1/(1-1.6/3)-1)<4(3/|\Sigma|)^{d-2}\;.$ (19)

This is our bound for the whole bottom factor when we maximized with
$z_{d-1}\geq 8$. Since it is larger than our bound of $3/|\Sigma|)^{d-2}$ when
we maximized with $z_{d-1}\leq 6$, we conclude that it is also our bound if we
maximize over any value of $z_{d-1}$. In combination with our top factor,
$16.6(\mu^{3}/|\Sigma|^{2})$ from (10), we get a combined bound of

$16.6(\mu/|\Sigma|^{2})4(3/|\Sigma|)^{d-2}\leq 7\mu^{3}(3/|\Sigma|)^{d}.$ (20)

###  5.2 Increasing the maximization range

We will now show how to deal with larger sets up to size
$w_{0}^{+}=0.63|\Sigma|$. The level factor with a fixed $z_{i+1}$ and $m_{i}$
has the following tight version from (13)

$\displaystyle(z_{i+1}-1)^{\underline{\underline{m_{i}-1}}}\cdot(2^{3/2}/|\Sigma|)^{m_{i}-1}/2^{z_{i+1}/4-1/2}$
$\displaystyle=2^{1/4}f(m_{i}-1,z_{i+1}-1)\textnormal{ where
}f(x,y)=y^{\underline{\underline{x}}}\cdot(2^{3/2}/|\Sigma|)^{x}/2^{y/4}.$

We want to find the sum over relevant $m_{i}$ with the maximizing $z_{i}$.
However, we already considered all even $z_{i+1}\leq|\Sigma|/2^{5/2}$, so it
suffices to consider $z_{i+1}\in(|\Sigma|/2^{5/2},\,|\Sigma|/2]$. Also, for a
given $z_{i+1}$, we have to sum over all $m_{i}\in[2,z_{i+1}/2]$. Thus we want
to bound

$\max_{\textnormal{odd
}y\in[|\Sigma|/2^{5/2},\,|\Sigma|/2)}\sum_{x=1}^{\lfloor y/2\rfloor}f(x,y).$

Note that $f(x+1,y)=f(x,y)\cdot(y-2x)(2^{3/2}/|\Sigma|)$. Hence
$f(x+1,y)<f(x,y)\iff y-2x<|\Sigma|/2^{3/2}$.

Assume that $y\geq|\Sigma|/2^{3/2}$ and consider the smallest integer $x_{y}$
such that $y-2x_{y}<|\Sigma|/2^{3/2}$. For a given value of $y$ this $x_{y}$
maximizes $f(x_{y},y)$.

To bound $f(x_{y},y)$, we note that

$y^{\underline{\underline{x}}}<(y-x+1)^{x}$

We have $y<w_{0}^{+}=0.63|\Sigma|$ and $y-2x_{y}<|\Sigma|/2^{3/2}$, so

$y-x_{y}+1\leq(0.63+1/2^{3/2})|\Sigma|/2+1\leq|\Sigma|/2.$

Therefore

$f(x_{y},y)\leq
y^{\underline{\underline{x_{y}}}}\cdot(2^{3/2}/|\Sigma|)^{x_{y}}/2^{y/4}\leq((y-x_{y}+1)2^{3/2}/|\Sigma|)^{x_{y}}/2^{y/4}\leq
1/2^{(y-2x_{y})/4}.$

We also have $y-2(x_{y}-1)\geq|\Sigma|/2^{3/2}$, so we get

$f(x_{y},y)\leq 1/2^{(|\Sigma|/2^{3/2}-2)/4}=1/2^{|\Sigma|/2^{7/2}-1/2}.$

For $|\Sigma|\geq 256$, this is below $0.015/|\Sigma|^{2}$, so even if we sum
over all $x\leq y/2\leq|\Sigma|/2$, we get a bound below $0.008/|\Sigma|$,
that is,

$\max_{y\in[|\Sigma|/2^{3/2},\,w_{0}^{+}]}\sum_{x=1}^{\lfloor
y/2\rfloor}f(x,y)\leq 0.08/|\Sigma|.$

Now consider $y<|\Sigma|/2^{3/2}$. Then $f(x,y)$ is decreasing in $x$ starting
$f(0,y)=1/2^{y/4}$. Summing over all $x\leq y/2$, we get $(y/2)/2^{y/4}$. This
expression is maximized with $y=4/\ln 2$, so for $y\geq|\Sigma|/4$, we get a
maximum of $(|\Sigma|/8)/2^{|\Sigma|/16}$. Now
$2^{|\Sigma|/16}\geq|\Sigma|^{2}$ for $|\Sigma|\geq 256$, so we end up with

$\max_{y\in[|\Sigma|/4|,|\Sigma|/2^{3/2}]}\sum_{x=1}^{\lfloor
y/2\rfloor}f(x,y)\leq 1/(8|\Sigma|).$

Finally we consider $y\in[|\Sigma|/2^{5/2},\,|\Sigma|/4]$. Then $f(x+1,y)\leq
f(x,y)(y\,2^{3/2}/|\Sigma|)\leq f(x,y)/2^{1/2}$, so

$\sum_{x=0}^{\infty}f(x,y)\leq f(0,y)/(1-2^{-1/2})\leq
1/((1-2^{-1/2})2^{y/4}).$

With $y\geq|\Sigma|/2^{5/2}$, this is maximized with $y=|\Sigma|/2^{5/2}$, so
we get the bound

$\max_{y\in[|\Sigma|/2^{5/2},\,|\Sigma|/4]}\sum_{x=0}^{\infty}f(x,y)\leq
1/((1-2^{-1/2})2^{(|\Sigma|/2^{9/2})})\leq 0.344/|\Sigma|.$

Putting all our bounds together, we conclude that

$\max_{\textnormal{odd }y\in[|\Sigma|/2^{5/2},\,w^{+}_{0})}\sum_{x=1}^{\lfloor
y/2\rfloor}f(x,y)\leq 0.344/|\Sigma|.$

Our bound for the level factor with $z_{i+1}<(|\Sigma|/2^{5/2},|\Sigma|/2]$ is
$2^{1/2}$ times bigger, but this is still much smaller than all the bounds
from Section 5.1 based on smaller $z_{i+1}$. Thus we conclude that the
analysis from Section 5.1 is valid even if allow $z_{i+1}$ to go the whole way
up to $w_{0}^{+}=0.63|\Sigma|$. Therefore (20) bounds the probability of any
obstruction with set size $|W|\leq w_{0}^{+}$.

However, for the probability of obstructions with sets sizes $|W|>w_{0}^{+}$,
we can apply (16), concluding that they happen with probability bounded by

$w_{0}^{+}|\Sigma|/2^{w_{0}^{+}}=0.63|\Sigma|^{2}/2^{0.63|\Sigma|}<1/2^{|\Sigma|/2}.$

The last step used $|\Sigma|\geq 256$. Together with (20) we have thus proved
that the probability of any obstruction is bounded by

$7\mu^{3}(3/|\Sigma|)^{d}+1/2^{|\Sigma|/2}.$ (21)

This is for simple tornado hashing without the twist.

###  5.3 Tornado hashing including the twist

We will now return to the original tornado hashing with the twisted character

$\widetilde{x}[c]=x[c]\oplus\widetilde{h}_{0}(x[<c]).$

This twist does not increase the number of lookups: it is still $c+d$ with $c$
input characters and $d$ derived characters, so the speed should be almost the
same, but we will gain a factor $3/|\Sigma|$ in the probability, like getting
an extra derived character for free.

The obstruction is constructed exactly as before except that we continue down
to level $0$ rather than stopping at level $1$. All definitions for level $i$
are now just applied for $i=0$ as well. However, we need to reconsider some
parts of the analysis. First, we need to prove that Lemma 10 also holds for
$i=0$:

#### Lemma 10

Let $M$ be a partial matching on $\Sigma^{c}$. Conditioning on $M$ being
$(i-1)$-independent, $M$ is an $i$-matching with probability
$1/|\Sigma|^{|M|}$.

###### Proof.

Since $M$ is $(-1)$-independent, we know that

$\textnormal{DiffKeys}(M,-1)=\left\\{(\widetilde{x}\triangle\;\widetilde{y})[<c]\mid\\{x,y\\}\in
M\right\\}$

is linearly independent. We note here that
$(\widetilde{x}\;\triangle\;\widetilde{y})[<c]=(x\;\triangle\;y)[<c]$. We want
to know the probability that $M$ is a 0-matching, that is, the probability
that $\tilde{x}[c]=\tilde{y}[c]$ for each $\\{x,y\\}\in M$. For $i>0$, we had

$\tilde{x}[c+i]=\tilde{y}[c+i]\iff\widetilde{h}_{i}((\widetilde{x}\triangle\;\widetilde{y})[<c+i])=0.$

However, for $i=0$, we have

$\tilde{x}[c]=\tilde{y}[c]\iff\tilde{h}_{0}((\widetilde{x}\triangle\;\widetilde{y})[<c])=x[c]\oplus
y[c].$

However, Lemma 9 states that the simple tabulation hash function
$\tilde{h}_{0}$ is fully random on the linearly indepedent
$\textnormal{DiffKeys}(M,-1)$, so we still conclude that $M$ is a 0-matching
with probability $1/\Sigma^{|M|}$. ∎

There is one more thing to consider. We have generally used that if $Z$ is an
$i$-zero set, that is, if $\widetilde{Z}[\leq c+i]$ is a zero-set, then $Z$ is
also a zero-set. However, this may no longer be the case. All we know is that
$\widetilde{Z}[\leq c]$ is a zero-set. This also implies that
$Z[<c]=\widetilde{Z}[<c]$ is a zero-set. However, we claim that

$\bigoplus Z=0$ (22)

Here $\bigoplus Z$ is xoring that keys in $Z$ viewed as bit-strings. Note that
$\operatorname*{\scalerel*{\triangle}{\sum}}Z=\emptyset$ implies $\bigoplus
Z=0$. Since $Z[<c]$ is a zero set, we know that
$\\{\widetilde{h}_{0}(x[<c])\mid x\in Z\\}$ is a zero set. We also know that
$\widetilde{Z}[c]$ is a zero set and it is equal to
$\\{\widetilde{h}_{0}(x[<c])\oplus x[c]\mid x\in Z\\}$. Thus we have

$\bigoplus\\{\widetilde{h}_{0}(x[<c])\oplus x[c]\mid x\in
Z\\}=0=\bigoplus\\{\widetilde{h}_{0}(x[<c])\mid x\in Z\\}$

implying $\bigoplus\\{x[c]\mid x\in Z\\}=0$. Together with $Z[<c]$ being a
zero set, this settles (22). As a result, for the coding key coding in (7) and
(12), we just have to replace $\operatorname*{\scalerel*{\triangle}{\sum}}$
with $\bigoplus$.

No other changes are needed. Level $0$ gives exactly the same level factor
(11) as the levels $i>0$, so it is like getting an extra level for free.
Therefore with tornado hashing we improve the bottom factor for simple tornado
hashing (19) to $4(3/|\Sigma|)^{d-1}$ and the probability of any small
obstruction from (20) to $7\mu^{3}(3/|\Sigma|)^{d+1}$. The probability of any
obstruction is thus improved from (21) to

$7\mu^{3}(3/|\Sigma|)^{d+1}+1/2^{|\Sigma|/2}.$ (23)

###  5.4 Full randomness for large sets of selected keys

While implementing tabulation hashing we often want to set the character size
so that all tables fit in cache. Indeed, this is the main reason why
tabulation-based hashing schemes are extremely fast in practice. However,
restricting the size of $\Sigma$ constrains how many keys we can expect to be
hashed fully randomly: in particular, Theorem 5 states that a set of
characters $\Sigma$ allows for up to $|\Sigma|/2$ selected keys to hash fully
randomly with high probability. Most experiments on tabulation-based hashing
[1, 2], though, use 8-bit characters (namely $|\Sigma|=2^{8}$). This implies
that whenever the selected keys are $s\leq 2^{7}$ then they hash uniformly at
random with high probability. However, we may want local full randomness for
$s$ keys, where $s\gg 2^{7}$. A trade-off between memory usage and number of
keys hashed uniformly is of course unavoidable, however we can improve over
the one in Theorem 5 with a clever observation.

More precisely, Theorem 5 states that given a set $X^{f,h}$ of query-selected
keys with $\mu^{f}\leq|\Sigma|/2$ their derived keys are linearly dependent
with probability at most
$\textsf{DependenceProb}(\mu,d,\Sigma)=7\mu^{3}(3/|\Sigma|)^{d+1}+1/2^{|\Sigma|/2}$
while tornado is using $O(c|\Sigma|)$ words of memory and exactly $c+d$
lookups in tables of size $|\Sigma|$. Recall that $\mu^{f}$ here is the
expected size of $X^{f,h}$ for a fully random $h$, when the queries are chosen
by an adaptive adversary. If we want to handle larger sets of selected keys
with $\mu^{f}\gg|\Sigma|/2$ using Theorem 5, then we need to use $O(c+d)$
larger tables of size roughly $2\mu^{f}$. The clever observation we make here
is that, in order to obtain a meaningful probability bound, it is not
necessary at all to employ $O(c+d)$ of such larger tables. Indeed, we just
need the tables in the top two levels to have size $|\Psi|\geq 2\mu^{f}$ to
obtain that the derived keys are linearly dependent with probability at most

$14|X|^{3}(3/|\Psi|)^{2}(3/|\Sigma|)^{d-1}+1/2^{\left|\Sigma\right|/2}\;$

losing a factor two with respect to Theorem 5. We name this variant of tornado
tabulation tornado-mix tabulation, because the last two derived characters can
be evaluated in parallel as in mixed tabulation hashing [10].

#### Formal definition of tornado-mix.

For each $i=0,\ldots,d-2$ we let
$\widetilde{h}_{i}:\Sigma^{c+i-1}\longrightarrow\Sigma$ be a simple tabulation
hash function. For $i=d-1,d$ we let
$\widetilde{h}_{i}:\Sigma^{c+d-2}\longrightarrow\Psi$ be a simple tabulation
hash function. Given a key $x\in\Sigma^{c}$, we define its _derived key_
$\widetilde{x}\in\Sigma^{c+d-2}\times\Psi^{2}$ as
$\widetilde{x}=\widetilde{x}_{1}\cdots\widetilde{x}_{c+d}$, where

$\widetilde{x}_{i}=\begin{cases}x_{i}&\text{if $i=1,\ldots,c-1$}\\\
x_{c}\oplus\widetilde{h}_{0}(\widetilde{x}_{1}\dots\widetilde{x}_{c-1})&\text{if
$i=c$}\\\
\widetilde{h}_{i-c}(\widetilde{x}_{1}\dots\widetilde{x}_{i-1})&\text{if
$i=c+1,\ldots,c+d-2$}.\\\
\widetilde{h}_{i-c}(\widetilde{x}_{1}\dots\widetilde{x}_{c+d-2})&\text{if
$i=c+d-1,c+d$}.\end{cases}$

Finally, we have a simple tabulation hash function
$\widehat{h}:\Sigma^{c+d-2}\times\Psi^{2}\longrightarrow\mathcal{R}$, that we
apply to the derived key. The _tornado-mix tabulation_ hash function
$h:\Sigma^{c}\longrightarrow\mathcal{R}$ is then defined as
$h(x)=\widehat{h}(\widetilde{x})$.

#### Cache efficiency.

It is worth to notice that such construction allows us to store in cache all
$|\Sigma|$-sized tables while the two $|\Psi|$-sized tables might overflow
cache. However, these larger tables are accessed only once while evaluating
tornado and they can be accessed in parallel.

#### Local uniformity theorem.

Now we are ready to state an analogous of Theorem 4 for larger sets of
selected keys. In what follows we use $f$, $\mu^{f}$ and $X^{f,h}$ as defined
in Section 1.2.

######  Theorem 16.

Let $h=\widehat{h}\circ\widetilde{h}:\Sigma^{c}\to\mathcal{R}$ be a random
tornado-mix tabulation hash function with $d$ derived characters, the last two
from $\Psi$, and select function $f$. If $\mu=\mu^{f}\leq\left|\Psi\right|/2$
then the derived selected keys $\widetilde{h}(X^{f,h})$ are linearly dependent
with probability at most

$14\mu^{3}(3/|\Psi|)^{2}(3/|\Sigma|)^{d-1}+1/2^{\left|\Sigma\right|/2}\;.$

###### Proof.

This proof works exactly as the proof of Theorem 4, except for a few slight
differences. We limit ourselves to listing such small differences. In Section
3.2 we define $Z$ as the smallest $d$-zero set among those $d$-zero sets
minimizing the number of elements not in $Q$. This definition implies that
there exists $x^{*}\in Z$ such that $Z\setminus\\{x^{*}\\}$ is
$d$-independent. Moreover, either $Z\subseteq Q$ or we can choose $x^{*}\in
Z\setminus Q$. In the original proof, we considered the alternating-cycle
structure induced by the top level matchings $M_{d-1}^{*}$ and $M_{d}^{*}$ and
traversed these cycles leaving $x^{*}$ last. This ensured that the edges from
$M^{*}_{d}$ were always “surprising” in the sense that the probability of any
such edge being realised by our random choice of $h$ was $1/|\Sigma|$, even
after conditioning on all previously discovered edges (these events were,
indeed, independent). This observation allowed us to bound the probability of
our obstruction being realised by $h$. In fact, we wanted our obstruction to
be constituted by edges which realisations were independent, exluding the last
edge. This is exactly what we did in Section 3.2, where all edges but the last
edge $e_{d-1}\in M^{*}_{d-1}$ were realised by $h$ independently.

In the current scenario, it is not obvious that the realisations of traversed
edges from $M^{*}_{d}$ are all independent and the first edge introducing a
dependence belongs to $M_{d-1}^{*}$. Here, instead, we traverse the
alternating-cycle graph until we find a prefix $W=\\{x_{1}\dots x_{w}\\}$ such
that either (i) $M^{*}_{d-1}$ restricted to $W$ or (ii) $M^{*}_{d}$ restricted
to $W$ is $(d-2)$-dependent. Case (i) is identical to the case already
analysed, but in case (ii) we need some small changes, essentially swapping
the roles of $M_{d}$ and $M_{d-1}$.

To understand the interplay between the two cases, note that every time we add
a vertex $x_{w}$, we add an edge to $M_{d-1}^{*}|_{W}$ if $w$ is odd, and to
$M_{d}^{*}|_{W}$ if $w$ is even. Case (i) can only happen if $w$ is even while
Case (ii) can only happen if $w$ is odd. If we get to $x_{w}=x^{*}$, then we
have have $W=Z$ and then we are in case (i) since $Z$ is even. Thus, if we end
in case (ii), then $x^{*}\not\in W$.

We now consider the slightly reduced traversal sequence where we simply drop
the first vertex in the last cycle considered in the traversal. The point is
that this vertex was not matched in $M_{d}^{*}|W$, but if we skip it then
$M_{d}^{*}|W$ is a perfect $d-2$-dependent matching while $M_{d-1}^{*}|W$ is a
maximal matching. Since we did not have $x^{*}$ in $W$, we have $W\subseteq
Z\setminus\left\\{x^{*}\right\\}$ implying full independence of the hash
values over $W$. Thus, using this reduced traversal sequence, we have swapped
the roles of the two top levels. Since we now have two cases, our union based
probability bounds are doubled (increasing the leading constant from 7 to 14).

The rest of the analysis is unchanged except that two top levels use the
different alphabet $\Psi$. This means $\Psi$ replaces $\Sigma$ in our bound
(9) for the two top levels. This implies that our overall bound is multiplied
by $\left|\Sigma\right|^{2}/\left|\Psi\right|^{2}$. Combined with the
doubling, we get an overall probability bound of

$14|X|^{3}(3/|\Psi|)^{2}(3/|\Sigma|)^{d-1}+1/2^{\left|\Sigma\right|/2}\;.$

∎

From Theorem 16, using Lemma 2, we derive the following analogous of Theorem 5
which was already stated in the introduction. Here we use the same notation as
in Theorem 5, where $h^{(s)}$ are the selection bits and $h^{(t)}$ are the
free bits.

See 8

##  6 Upper Tail Chernoff

In this section, we show a Chernoff-style bound on the number of the selected
keys $X^{f,h}$.

See 6

###### Proof.

We follow the proof of the Chernoff bound for the upper tail. Mainly, we let
$\mathcal{J}_{x}$ denote the indicator random variable for whether the key $x$
gets selected in $X^{f,h}$. Then
$\left|X^{f,h}\right|=\sum_{x\in\Sigma^{c}}\mathcal{J}_{x}$. For simplicity,
we let $a=1+\delta$. Then for any $s>0$:

$\displaystyle\Pr\\!\left[{\left|X^{f,h}\right|\geq
a\cdot\mu^{f}\wedge\mathcal{I}_{X^{f,h}}}\right]$
$\displaystyle=\Pr\\!\left[{\left|X^{f,h}\right|\cdot\left[{\mathcal{I}_{X^{f,h}}}\right]\geq
a\cdot\mu^{f}}\right]$
$\displaystyle=\Pr\\!\left[{e^{s\left|X^{f,h}\right|\cdot\left[{\mathcal{I}_{X^{f,h}}}\right]}\geq
e^{sa\cdot\mu^{f}}}\right]$
$\displaystyle\leq\frac{\textnormal{E}\\!\left[{M_{\left|X^{f,h}\right|\cdot\left[{\mathcal{I}_{X^{f,h}}}\right]}(s)}\right]}{e^{sa\cdot\mu^{f}}}\;,$

where $M_{\left|X^{f,h}\right|\cdot\left[{\mathcal{I}_{X^{f,h}}}\right]}(s)$
is the moment generating function of the random variable
$(\left|X^{f,h}\right|\cdot\left[{\mathcal{I}_{X^{f,h}}}\right])$, and is
equal to:

$M_{\left|X^{f,h}\right|\cdot\left[{\mathcal{I}_{X^{f,h}}}\right]}(s)=\textnormal{E}\\!\left[{e^{s\cdot\left|X^{f,h}\right|\cdot\left[{\mathcal{I}_{X^{f,h}}}\right]}}\right]=\sum_{i=0}^{\infty}{\frac{s^{i}}{i!}\cdot\textnormal{E}\\!\left[{\left|X^{f,h}\right|^{i}\cdot\left[{\mathcal{I}_{X^{f,h}}}\right]}\right]}\;.$

Since $\left|X^{f,h}\right|=\sum_{x\in\Sigma^{c}}\mathcal{J}_{x}$, each moment
$\textnormal{E}\\!\left[{\left|X^{f,h}\right|^{i}\cdot\left[{\mathcal{I}_{X^{f,h}}}\right]}\right]$
can be written as the sum of expectations of the form
$\textnormal{E}\\!\left[{\prod_{x\in
S}\mathcal{J}_{x}\cdot\left[{\mathcal{I}_{X^{f,h}}}\right]}\right]$, where
$S\subseteq\Sigma^{c}$ is a fixed subset of size $\leq i$. In general, the
moment generating function can be written as a sum, with positive
coefficients, of terms of the form $\textnormal{E}\\!\left[{\prod_{x\in
S}\mathcal{J}_{x}\cdot\left[{\mathcal{I}_{X^{f,h}}}\right]}\right]$ for some
fixed subset $S$. Moreover, each such term amounts to

$\textnormal{E}\\!\left[{\prod_{x\in
S}\mathcal{J}_{x}\cdot\left[{\mathcal{I}_{X^{f,h}}}\right]}\right]=\Pr\\!\left[{S\subseteq
X^{f,h}\wedge\mathcal{I}_{X^{f,h}}}\right]\;.$

We now condition on the hash values of the query keys $h|_{Q}$. For any set
$S\subseteq\Sigma^{c}$, we let $\mathcal{I}_{S\cup Q}$ denote the event that
the derived keys in $\widetilde{h}(S\cup Q)$ are linearly independent. Note
that $\mathcal{I}_{X^{f,h}}$ being true implies that $\mathcal{I}_{S\cup Q}$
is true. Moreover, since $S\cup Q$ is a fixed (deterministic) set, the event
$\mathcal{I}_{S\cup Q}$ only depends on the randomness of $\widetilde{h}$. We
get the following:

$\displaystyle\Pr\\!\left[{S\subseteq X^{f,h}\wedge\mathcal{I}_{X^{f,h}}\text{
}\Big{|}\text{ }h|_{Q}}\right]$ $\displaystyle\leq\Pr\\!\left[{S\subseteq
X^{f,h}\wedge\mathcal{I}_{S\cup Q}\text{ }\Big{|}\text{ }h|_{Q}}\right]$
$\displaystyle=E\Big{[}\left[{\mathcal{I}_{S\cup
Q}}\right]\cdot\Pr\left(S\subseteq X^{f,h}\text{ }\Big{|}\text{
}\widetilde{h},h|_{Q}\right)\text{ }\Big{|}\text{ }h|_{Q}\Big{]}$
$\displaystyle=E\Big{[}\prod_{x\in S}\mathcal{J^{*}}_{x}\text{ }\Big{|}\text{
}h|_{Q}\Big{]}\;,$

where $\left\\{\mathcal{J^{*}}_{x}\right\\}_{x\in X}$ denotes the indicator
random variables for choosing to select the keys in $S$ independently and
uniformly at random when we fix the hash values of the query keys. This last
step is due to the fact that the event if $\mathcal{I}_{S\cup Q}$ is true
then, then $(h|_{S},h|_{Q})$ is fully random and it has the same distribution
as $(h^{*}|_{S},h|_{Q})$, where $h^{*}$ is a fully-random hash function. If
$\mathcal{I}_{S\cup Q}$ is false, then the entire expression is $0$. We can
thus continue the proof of Chernoff’s as if $\left|X^{f,h}\right|$ were a sum
of independent random variables. The claim follows by noticing that, when
$\mathcal{I}_{X^{f,h}}$ is true, we have that
$E\left[X^{f,h}\right]\leq\mu^{f}$.

∎

###  6.1 Upper Tail Chernoff for larger $\mu^{f}$

We now consider the case in which we have a selector function for which
$\mu^{f}>\left|\Sigma\right|/2$. In this case, even though we cannot guarantee
that the set of derived selected keys is linearly independent whp, we show
that, whp, its size still cannot be much larger than $\mu^{f}$. This
particular case will be useful in the analysis of linear probing from Section
7.

######  Lemma 17.

Let $h=\widehat{h}\circ\widetilde{h}:\Sigma^{c}\to\mathcal{R}$ be a random
tornado tabulation hash function with $d$ derived characters, query key $Q$
with $\left|Q\right|<\left|\Sigma\right|/2$, and selector function $f$ such
that $\mu^{f}>\left|\Sigma\right|/2$. Then, for any $\delta>0$, the set of
selected derived keys $X^{f,h}$ satisfies the following:

$\Pr\left[{\left|X^{f,h}\right|\geq(1+\delta)\cdot\mu^{f}}\right]\leq
4\cdot\left(\frac{e^{\delta_{0}}}{(1+\delta_{0})^{1+\delta_{0}}}\right)^{\left|\Sigma\right|/2}+4\cdot\textsf{DependenceProb}(\left|\Sigma\right|/2,d,\Sigma)\;,$

where

$\delta_{0}=\frac{\mu^{f}}{\mu^{f}-\left|Q\right|}\cdot\frac{\left|\Sigma\right|/2-\left|Q\right|}{\left|\Sigma\right|/2}\cdot\delta\geq\left(1-\frac{\left|Q\right|}{\left|\Sigma\right|/2}\right)\cdot\delta\;.$

###### Proof.

We modify the given selector function $f$ to get another selector function
$f_{p}$ with the same set of query keys $Q$ but with a much smaller
$\mu^{f_{p}}$. Selection according to $f_{p}$ is done such that, once $f$
selects a key in $\Sigma^{c}\setminus Q$, $f_{p}$ further sub-selects it with
some probability $p$. This sub-selection is done independently for every
selected key. It follows that, for all $x\in\Sigma^{c}\setminus Q$,
$p_{x}^{f_{p}}=p_{x}^{f}\cdot p$. Taking into account query keys, we also get
that $\mu^{f_{p}}=(\mu^{f}-\left|Q\right|)\cdot
p+\left|Q\right|=p\mu^{f}+(1-p)\left|Q\right|$.

Moreover, one can show that, as long as
$\mu^{f_{p}}\leq\left|\Sigma\right|/2$, all our results about linear
independence also hold for such sub-sampled select function. In particular,
the only aspect of the proof of Theorem 4 that depends on the probabilities
$p_{x}^{f_{p}}$ is the proof of Lemma 14. There, we invoke Lemma 9 to get an
upper bound on the probability that the set $W\setminus\\{x_{w}\\}$ is
selected, given that it is $d$-independent. Notice that, if, additionally, we
sub-sample elements from $W\setminus\\{x_{w}\\}$ each independently with
probability $p$, we obtain the same bounds as if we initially selected
elements with probability $p_{x}^{f_{p}}$. Therefore, when
$\mu^{f}>\left|\Sigma\right|/2$, we can pick any
$p\leq(\left|\Sigma\right|/2-\left|Q\right|)/(\mu^{f}-\left|Q\right|)$ to get
that the set of derived keys for the sampled selection
$\widetilde{X}^{f_{p},h}$ is indeed linearly independent with probability at
least $1-\textsf{DependenceProb}(\mu^{f_{p}},d,\Sigma)$. We use
$I_{X^{f_{p},h}}$ to denote this event.

The next step is to notice that, conditioned on
$\left|X^{f,h}\right|-\left|Q\right|$, the distribution of
$\left|X^{f_{p},h}\right|-\left|Q\right|$ is exactly the binomial distribution
$B(\left|X^{f,h}\right|-\left|Q\right|,p)$. Then, for
$p>1/(\left|X^{f,h}\right|-\left|Q\right|)$, we have from [20] that

$\Pr\\!\left[{\left|X^{f_{p},h}\right|\geq\textnormal{E}\\!\left[{\left|X^{f_{p},h}\right|}\mid{\left|X^{f,h}\right|}\right]}\mid{\left|X^{f,h}\right|}\right]>1/4\;.$

Therefore, for any $t>0$:

$\Pr\\!\left[{\left|X^{f_{p},h}\right|\geq p\cdot t+(1-p)\left|Q\right|\text{
}\Big{|}\text{ }\left|X^{f,h}\right|\geq t}\right]>1/4\;.$

We now use this to derive an upper bound on $\Pr\left(\left|X^{f,h}\right|\geq
t\right)$ as such:

$\displaystyle\Pr\left(\left|X^{f,h}\right|\geq t\right)$
$\displaystyle<4\cdot\Pr\left(\left|X^{f_{p},h}\right|\geq p\cdot
t+(1-p)\left|Q\right|\text{ }\Big{|}\text{ }\left|X^{f,h}\right|\geq
t\right)\cdot\Pr\left(\left|X^{f,h}\right|\geq t\right)$ $\displaystyle\leq
4\cdot\Pr\left(\left|X^{f_{p},h}\right|\geq p\cdot
t+(1-p)\left|Q\right|\right)$ $\displaystyle\leq
4\cdot\Pr\left(\left|X^{f_{p},h}\right|\geq p\cdot t+(1-p)\left|Q\right|\wedge
I_{X^{f_{p},h}}\right)+$
$\displaystyle+4\cdot\textsf{DependenceProb}(\mu^{f_{p}},d,\left|\Sigma\right|)\;.$

We now plug in $t=(1+\delta)\cdot\mu^{f}$, and get that $p\cdot
t+(1-p)\left|Q\right|\geq(1+\delta_{0})\cdot\mu^{f_{p}}$ for

$\delta_{0}\leq\frac{p\mu^{f}}{\mu^{f_{p}}}\cdot\delta\;.$

We then invoke Lemma 6 to get that

$\displaystyle\Pr\left(\left|X^{f_{p},h}\right|\geq(1+\delta_{0})\cdot\mu^{f_{p}}\wedge
I_{X^{f_{p},h}}\right)$
$\displaystyle\leq\left(\frac{e^{\delta}_{0}}{(1+\delta_{0})^{1+\delta_{0}}}\right)^{\mu^{f_{p}}}\;.$

Finally, we instantiate
$p=(\left|\Sigma\right|/2-\left|Q\right|)/(\mu^{f}-\left|Q\right|)$ such that
$\mu^{f_{p}}=\left|\Sigma\right|/2$. and notice that indeed,
$p>1/(\left|X^{f,h}\right|-\left|Q\right|)$ when
$\left|X^{f,h}\right|\geq(1+\delta)\cdot\mu^{f}$ and
$\left|Q\right|<\left|\Sigma\right|/2$. We notice that, in this case,

$\delta_{0}=\frac{\mu^{f}}{\mu^{f}-\left|Q\right|}\cdot\frac{\left|\Sigma\right|/2-\left|Q\right|}{\left|\Sigma\right|/2}\cdot\delta\geq\left(1-\frac{\left|Q\right|}{\left|\Sigma\right|/2}\right)\cdot\delta\;.$

The argument follows.

∎

##  7 Linear Probing with Tornado Tabulation

In this section we show how to formally apply our framework to obtain results
on linear probing with tornado tabulation. We present the following main
result comparing the performance of linear probing with tornado tabulation to
that of linear probing using fully random hashing on a slightly larger keyset.

######  Theorem 18.

Let $S,S^{*}\subseteq\Sigma^{c}$ be sets of keys of size $n$ and
$n^{*}=(1+15\sqrt{\log(1/\delta)/|\Sigma|})n$, respectively, for some
$\delta\in(0,1/6)$. Let $T$, $T^{*}$ be arrays of size $m$, a power of two.
Now consider inserting the keys in $S$ ($S^{*}$) into $T$ ($T^{*}$) with
linear probing using tornado tabulation (fully random hashing). Let $X$ and
$X^{*}$ be the number of comparisons performed when inserting a new key $x$ in
each of $T$ and $T^{*}$ (i.e., $x\notin S\cup S^{*}$). Given the restrictions
listed below there exists an event $\mathcal{E}$ with $\Pr(\mathcal{E})\geq
1-\left(1/|\Sigma|+6\delta+61\log
n\cdot\textsf{DependenceProb}(|\Sigma|/2,d,\Sigma)\right)$ such that,
conditioned on $\mathcal{E}$, $X$ is stochastically dominated by $X^{*}$.
Restrictions:

  * •

$n/m\leq 4/5$

  * •

$|\Sigma|\geq 2^{16}$

  * •

$|\Sigma|\geq 30\cdot\log n$

  * •

$\sqrt{\log(1/\delta)/|\Sigma|}\leq 1/18$

From Theorem 18, it follows that linear probing using tornado tabulation
achieves the same expected number of comparison as in the fully random
setting, a proof is given in Section 7.4.

######  Corollary 19.

Setting $\delta=\Theta(1/|\Sigma|)$, $d\geq 5$, $\log n\leq o(|\Sigma|)$ in
Theorem 18 we have

$\textnormal{E}\\!\left[{X}\right]\leq\textnormal{E}\\!\left[{X^{*}}\right]+o(1)\,.$

The result of Corollary 19 is to be contrasted with previous work on practical
implementations of linear probing. While Knuth’s analysis serves as evidence
of linear probing’s efficieny in terms of the number of comparisons performed,
the advantage of linear probing (over other hash table implementations) is
that each sequential memory access is much faster than the random memory
access we do for the first probe at $T[h(x)]$. How much faster depends on the
computer system as does the cost of increasing the memory to reduce the load.
Some experimental studies [7, 21, 34] have found linear probing to be the
fastest hash table organization for moderate load factors (30-70%). If the
load is higher, we could double the table size.

However, using experimental benchmarks to decide the hash table organization
is only meaningful if the experiments are representative of the key sets on
which linear probing would be employed. Since fully random hashing cannot be
efficiently implemented, we might resort to weaker hash functions for which
there could be inputs leading to much worse performance than in the
benchmarks. The sensitivity to a bad choice of the hash function led [21] to
advice _against_ linear probing for general-purpose use. Indeed, Mitzenmacher
and Vadhan [27] have proved that 2-independent hashing performs as well as
fully random hashing if the input has enough entropy. However, [36, 30] have
shown that with the standard 2-independent linear hashing scheme, if the input
is a dense set (or more generally, a dense subset of an arithmetic sequence),
then linear probing becomes extremely unreliable and the expected probe length
increases from Knuth’s $\frac{1+1/\varepsilon^{2}}{2}$ to $\Omega(\log n)$,
while the best known upper bound in this case is $n^{o(1)}$ [24].888We note
that if we only know that the hash function is $2$-independent, then the lower
bound for the expected probe length is $\Omega(\sqrt{n})$ and this is tight.
[36, 30]

In a breakthrough result, Pagh, Pagh and Ružić [29] showed that if we use
5-independent hashing and the load gap $\varepsilon=\Omega(1)$, then the
expected probe length is constant. Pǎtraşcu and Thorup [31] generalized this
to an $O(1/\varepsilon^{2})$ bound for arbitrary $\varepsilon$, and showed
that this also holds for simple tabulation hashing. However, in both cases,
the analysis hides unspecified large constants in the $O$-notation. Thus, with
these hashing schemes, there could still be inputs for which linear probing
performs, say, 10 times worse in expectation, and then we would be better off
using chaining.

Our result is of a very different nature. We show that whp, for any given
query key $x$, the probe length corresponding to $h(x)$ when we use tornado
tabulation hashing is stochastically dominated by the probe length in a linear
probing table that hashes slightly more keys but uses fully random hashing. In
particular, this implies that whp, the expected probe length with tornado
tabulation hashing is only a factor $1+o(1)$ away from Knuth’s
$\frac{1+1/\varepsilon^{2}}{2}$. We get this result without having to revisit
Knuth’s analysis from [25], but simply because we know that we are almost as
good as fully random hashing, in a local sense that is sufficient for bounding
the probe length (see Section 7.1).

As a further consequence of our results, we get that any benchmarking with
random keys that we do in order to set system parameters will be
representative for all possible sets of input keys. Moreover, the fact that
tornado tabulation hashing only needs locality to perform almost as well as
fully random hashing means that our arguments also work for other variants of
linear probing. For instance, ones where the maintenance of the hash table
prioritizes the keys depending on when they were inserted, as first suggested
in [4]. Examples of this include Robin hood hashing where keys with the lowest
hash value come first [8] or time-reversed linear probing [34] where the
latest arrival comes first. In all these cases, tornado tabulation hashing
performs almost as well as with fully-random hashing.

###  7.1 Proof of Theorem 18

We let $\alpha=n/m$ denote the fill of the hash table and
$\varepsilon=1-\alpha$. The basic combinatorial measure that we study and
employ is the _run length_ : If cells $T[a]$, $T[a+1],\dots,T[b-1]$ are all
occupied by elements from $S$ but both $T[a-1]$ and $T[b]$ are freem these
$b-a$ cells are called a run of length $b-a$. Let $R(x,S)$ be the length of
the run intersecting $T[h(x)]$ and note that $R(x,S)+1$ is an upper bound on
the number of comparisons needed to insert some element $y$ into the table
when $y$ hashes to the same location as $x$.

Let $\Delta$ be the largest power of two such that
$3\alpha\Delta+1\leq|\Sigma|/2$. The following lemma, proven in Section 7.3,
gives an upper bound on the probability that $h(x)$ intersects a long run.

######  Lemma 20.

$\Pr\\!\left[{R(x,S)\geq\Delta}\right]\leq\frac{1}{|\Sigma|}+60\log
n\cdot\textsf{DependenceProb}(|\Sigma|/2,d,\Sigma)\,.$

Let $\mathcal{A}$ be the event $\left(R(x,S)\geq\Delta\right)$. Assuming
$\mathcal{A}$, there exists at least one unoccupied cell in table $T$ between
$T[h(x)-\Delta]$ and $T[h(x)]$ and likewise between $T[h(x)]$ and
$T[h(x)+\Delta]$. Hence the insertion of $x$ only depends on the distribution
of the much smaller key-set $\left\\{s\in
S\,\big{|}\,\left|h(s)-h(x)\right|\leq\Delta\right\\}$.

The second step of our proof bounds the probability that tornado tabulation
behaves like a fully random hash function when restricted to this small set of
keys. As Theorem 5 doesn’t apply for arbitrary intervals we will instead cover
the necessary interval with three dyadic intervals. Recall that a dyadic
interval is an interval of the form $[j2^{i},(j+1)2^{i})$, where $i,j$ are
integers. In the following we will exclusively consider a number of dyadic
intervals all of length $\Delta$. Let $I_{C}$ denote the dyadic interval that
contains $h(x)$, and similarly let $I_{R}$ and $I_{L}$ denote the dyadic
intervals to the left and right, respectively, of $I_{C}$. We further let
$X_{C}$ be the set of keys in $S$ that hash into the interval $I_{C}$, i.e.,
$X_{C}=\left\\{x\in S\mid h(x)\in I_{C}\right\\}$, and similarly, $X_{R}$ and
$X_{L}$ are the pre-image of $h$ in $I_{R}$ and $I_{L}$, respectively. Given
$\mathcal{A}$, the distribution of $X$ is completely determined by the
distribution of the keys in $X_{L}\cup X_{C}\cup X_{R}$ and $h(x)$.

The expected size of each preimage is $\alpha\Delta$ and our choice of
$\Delta$ thus allows us to apply Theorem 5 to all three intervals at once. Let
$\mathcal{B}$ be the event that the keys hashing into these intervals are
distributed independently:

######  Corollary 21.

With probability at least $1-\textsf{DependenceProb}(|\Sigma|/2,d,\Sigma)$,
$\tilde{h}(X_{R}\cup X_{C}\cup X_{L}\cup\left\\{x\right\\})$ is linearly
independent, such that $h$ hashes the keys in $X_{R}\cup X_{C}\cup
X_{L}\cup\left\\{x\right\\}$ independently and uniformly in their respective
intervals.

We now define the analogous terms in the fully random setting. We let
$I^{*}_{C}$ denote the dyadic interval in $T^{*}$ that contains $h^{*}(x)$ and
$I^{*}_{R}$ and $I^{*}_{L}$ the right and left neighboring dyadic intervals.
Similarly, we let $X^{*}_{C}$, $X^{*}_{R}$ and $X^{*}_{L}$ denote their
preimages under $h^{*}$. The following lemma compares the two experiments in
terms of the sizes of these preimages, and is proven in Section 7.2.

######  Lemma 22.

Let $\mathcal{C}$ be the event
$\left|X_{L}\right|\leq\left|X^{*}_{L}\right|\land\left|X_{C}\right|\leq\left|X^{*}_{C}\right|\land\left|X_{R}\right|\leq\left|X^{*}_{R}\right|$,
then

$\Pr\\!\left[{\mathcal{B}\land\bar{\mathcal{C}}}\right]\leq 6\delta$

Let $\mathcal{C}$ be the event that each of the preimages $X_{i}$ contain at
most as many elements as the corresponding preimage $X_{i}^{*}$. Finally,
define $\mathcal{E}=\mathcal{A}\cap\mathcal{B}\cap\mathcal{C}$. We will now
present a coupling $\tilde{X}$ of $X$ which, when conditioned on
$\mathcal{E}$, satisfies $\tilde{X}\leq X^{*}$.

For every realization of $\left|X_{L}\right|$, $\left|X_{C}\right|$ and
$\left|X_{R}\right|$, we consider the following random process: starting from
an emtpy table of size $m$ and using the fully random $h^{*}$, insert the
first $\left|X_{L}\right|$ elements from $X^{*}_{L}$, then the first
$\left|X_{R}\right|$ elements from $X^{*}_{R}$ and finally, the first
$\left|X_{C}\right|$ elements from $X^{*}_{C}$ (we do not insert any more
elements after this). Note that, conditioned on $\mathcal{C}$, we have that it
is possible to choose such elements (i.e.,
$\left|X_{R}\right|\leq\left|X^{*}_{R}\right|$ etc.). Now let $\tilde{X}$
denote the number of comparisons performed when inserting $x$ into the table
at this point in time.

We now have that $X$ (defined for the tornado tabulation) is identically
distributed as $\tilde{X}$ (defined for a fully random hash function). This is
because event $\mathcal{A}$ implies that the distribution of $X$ only depends
on $X_{R}$, $X_{C}$ and $X_{L}$. Event $\mathcal{B}$ further implies that, on
these intervals, $h$ behaves like a fully random hash function. Now note that
$\tilde{X}\leq X^{*}$, since we can continue the random process and add the
remaining keys in $S^{*}$ and this can only increase the number of comparisons
required to insert $x$ (i.e., ‘‘more is worse’’).

Left is to compute the total probability that any of our required events fail:

$\displaystyle\Pr\\!\left[{\bar{\mathcal{E}}}\right]$
$\displaystyle=\Pr\\!\left[{\bar{\mathcal{A}}\lor\bar{\mathcal{B}}\lor\bar{\mathcal{C}}}\right]$
$\displaystyle=\Pr\\!\left[{(\bar{\mathcal{A}}\lor\bar{\mathcal{C}})\land\mathcal{B}}\right]+\Pr\\!\left[{\bar{\mathcal{B}}}\right]$
$\displaystyle\leq\Pr\\!\left[{\bar{\mathcal{A}}}\right]+\Pr\\!\left[{\mathcal{B}\land\bar{\mathcal{C}}}\right]+\Pr\\!\left[{\bar{\mathcal{B}}}\right]$
$\displaystyle\leq 1/|\Sigma|+6\delta+61\cdot\log
n\cdot\textsf{DependenceProb}(|\Sigma|/2,d,\Sigma)\,.$

This concludes the proof.

###  7.2 Proof of Lemma 22

As $\Delta$ is chosen to be the largest power of two such that
$3\alpha\Delta\leq|\Sigma|/2$ we get $\frac{|\Sigma|}{12\alpha}\leq\Delta$.
Let $t$ be a constant, to be decided later. For each
$i\in\left\\{L,C,R\right\\}$ let $\mathcal{E}_{i}$ be the event
($\left|X_{i}\right|\leq t$) and $\mathcal{E}_{i}^{*}$ be the event
($t\leq\left|X_{i}^{*}\right|$).

$\displaystyle\Pr\\!\left[{\mathcal{B}\land\bar{\mathcal{C}}}\right]$
$\displaystyle=\Pr\\!\left[{\mathcal{B}\land\exists
i\in\left\\{L,C,R\right\\}:\left|X_{i}\right|>\left|X_{i}^{*}\right|}\right]$
$\displaystyle\leq\Pr\\!\left[{\mathcal{B}\land\exists
i\in\left\\{L,C,R\right\\}:\bar{\mathcal{E}}_{i}\lor\bar{\mathcal{E}}_{i}^{*}}\right]$
$\displaystyle\leq\sum_{i\in\left\\{L,C,R\right\\}}\left(\Pr\\!\left[{\mathcal{B}\land\left|X_{i}\right|>t}\right]+\Pr\\!\left[{\mathcal{B}\land\left|X_{i}^{*}\right|<t}\right]\right)$
$\displaystyle\leq\sum_{i\in\left\\{L,C,R\right\\}}\left(\Pr\\!\left[{\mathcal{B}\land\left|X_{i}\right|>t}\right]+\Pr\\!\left[{\left|X_{i}^{*}\right|<t}\right]\right)$

Let $\mu=\textnormal{E}\\!\left[{\left|X_{i}\right|}\right]=\Delta\alpha$,
$k=\sqrt{3\log(1/\delta)/\mu}$ and $t=(1+k)\mu$. Applying the tail-bound of
Lemma 6 we have

$\displaystyle\Pr\\!\left[{\mathcal{B}\land\left|X_{i}\right|>t}\right]$
$\displaystyle=\Pr\\!\left[{\mathcal{B}\land\left|X_{i}\right|>(1+k)\mu}\right]$
$\displaystyle\leq\exp\left(-k^{2}\mu/3\right)$ $\displaystyle=\delta\,.$

As $\mu=\alpha\Delta\geq|\Sigma|/12$ we have

$\displaystyle k$ $\displaystyle=\sqrt{3\log(1/\delta)/(\alpha\Delta)}$
$\displaystyle\leq\sqrt{36\log(1/\delta)/|\Sigma|}$ $\displaystyle\leq 1/3\,.$

As $n^{*}=(1+15\sqrt{\log(1/\delta)/|\Sigma|})n\geq(1+2.5k)n$,
$\mu^{*}=\textnormal{E}\\!\left[{\left|X_{i}^{*}\right|}\right]\geq(1+2.5k)\mu$.
Next, let $k^{*}=k\cdot\sqrt{2/3}$. Then

$\displaystyle\mu^{*}\cdot(1-k^{*})$
$\displaystyle\geq(1+2.5k)\cdot\mu\cdot(1-k^{*})$
$\displaystyle=(1+2.5k)\cdot\mu\cdot(1-\sqrt{2/3}\cdot k)$
$\displaystyle\geq\mu\cdot(1+k)$ $\displaystyle=t\,.$

Hence

$\displaystyle\Pr\\!\left[{\left|X_{i}^{*}\right|<t}\right]$
$\displaystyle\leq\Pr\\!\left[{\left|X_{i}^{*}\right|<(1-k^{*})\mu^{*}}\right]$
$\displaystyle\leq\exp(-(k^{*})^{2}\mu^{*}/2)$
$\displaystyle=\exp(-k^{2}\mu^{*}/3)$ $\displaystyle\leq\exp(-k^{2}\mu/3)$
$\displaystyle=\delta\,.$

Summing over the six cases we see $\Pr\\!\left[{\mathcal{B}\land\exists
i\in\left\\{L,C,R\right\\}:\left|X_{i}\right|>\left|X_{i}^{*}\right|}\right]\leq
6\delta$.

###  7.3 Proof of Lemma 20

Our proof relies on the simple observation that if $T[a]$ through $T[b]$ are
all occupied and the run _starts_ in $T[a]$ (i.e. $T[a-1]$ is free which
excludes the possibility of prior positions spilling over), then the preimage
$h^{-1}([a,b])=\left\\{s\in S\,|\,h(x)\in[a,b]\right\\}$ must have size at
least $\left|b-a\right|$. It must also be the case that either (1) the
preimage $h^{-1}([a+1,b])$ has size at least $(b-a)\cdot(1-\gamma)$ or (2) the
preimage $h^{-1}([a,a])$ is of size at least $(b-a)\cdot\gamma$, for any
parameter $\gamma\geq 0$.

We can generalize this to consider a run starting in any position $T[b]$
within some interval $b\in[a,c]$ which continues through $T[d]$, then either
(1) $\left|h^{-1}([c,d])\right|\geq(d-c)\cdot(1-\gamma)$ or (2)
$\left|h^{-1}([a,c])\right|\geq(d-c)\cdot\gamma$. We will refer to $[a,c]$ as
the start-interval and to $[c,d]$ as the long interval.

Our strategy is to make both of these events unlikely by balancing the size of
the start-interval with the number of keys needed to fill up the long
interval. Larger difference $(d-c)$ allows for a larger start-interval. With a