# Linear and almost-linear perfect hashing

I am trying to understand the sentence from a paper by Patrascu:

Unfortunately, we do not have linear perfect hashing. Instead, we use a family of hash functions.... with almost-linearity

The context is a reduction between two variants of the 3-SUM problem:

• In the usual variant, 3SUM, given an array $A$ we have to find 3 indices $i,j,k$ such that: $A[i]+A[j]=A[k]$.
• In the other variant, Conv3SUM, we have to find 2 indices $i,j$ such that: $A[i]+A[j]=A[i+j]$.

Theoretically, we could reduce 3SUM to Conv3SUM if we had a linear hash function - a function $h$ such that: $h(x+y)=h(x)+h(y)$, and that maps all elements of $A$ to the range of indices $\{0,...,n-1\}$

The reduction is by sending every element of $A$ to an index determined by $h$, i.e. create an array $B$ such that for every $x\in A$: $B[h(x)]=x$

Then, if there is a solution to 3SUM on A, $x+y=z$, then on B we will have: $B[h(x)]+B[h(y)]=B[h(z)]$, and by the linearity of $h$ also $h(x)+h(y)=h(z)$, so this is a solution to Conv3SUM on B.

Conversely, every solution to Conv3SUM on B is trivially a solution to 3SUM on A, since every element of B is also an element of A.

Unfortunately, we do not have linear perfect hashing, so we have to use a family of almost-linear hash functions.

MY QUESTION IS: why do we have perfect almost-linear hash functions and not perfect linear hash functions? How does almost-linearity make it easier to find perfect hash functions?

• It is trivial to find perfect linear hash functions. The hash function $h(x)=x$ satisfies all of your constraints. If you want one whose output is much shorter than the input $h(x)=x \bmod p$ is linear. What are the additional constraints on your hash function that make those not a valid solution? – D.W. Feb 16 '15 at 19:32
• I think the problem is that the function $h(x)=x \mod p$ is not surjective (as you said in your previous answer). But, an almost-linear function is also not surjective. This is what I fail to understand. – Erel Segal-Halevi Feb 17 '15 at 13:33

I think there is a constraint that the domain of the hashing function must be {0...n-1}, where n means the number of elements to hash. Only defining in this way , the reduction from 3SUM to Conv3SUM works.

The is an almost-linearity function in wiki. And it is easy to figure out a counter example for the existence of perfect linear hashing function.

Consider the following questions:

Let A = {1,2,3,4}, B={0,1,2,3}

1. how many triples (x,y,z) satisfy x+y=z, where x,y,z are in A and distinct
2. what if x,y,z are in B

The answer of the first question is

1. 1+1=2
2. 1+2=3
3. 1+3=4
4. 2+2=4

But there are only two triples in the second question. You can find out a bijective function, satisfying that linearity property, mapping A onto B .