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?
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}


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


The answer of the first question is 


1+1=2
1+2=3
1+3=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 .