1
$\begingroup$

I need a perfect hash function that maps 2 integers into one integer twice the size (i.e. $(Int64, Int64) \rightarrow Int128$).

The function preserves sum of leading zero bits:

  • $(0, 0) \rightarrow 0$ - good mapping, as each argument has $64$ leading zeros and that transformed into $128$ leading zeros of the output
  • $(0, 0) \rightarrow 27$ - also good mapping, output 0x11011 still has $123$ leading zeros
  • $(2^{30}, 2^{15}) \rightarrow 2^{43}$ - good mapping, sum of arguments zeros is $33 + 48 = 81$ which is close enough to output's $84$
  • $(0, 0) \rightarrow 2^{50}$ - bad mapping, only $77$ zeros in the output
  • $f(a,b) = a × b$ preserves zero sum well but is not a perfect hash function
  1. It's fine if the function doesn't work well with a small subset of arguments: $1\%$ of all pairs violates weak zero sum preservation is acceptable, but the function still should be a perfect hash function.
  2. The function should not use additional memory like lookup tables.
  3. If $z(x)$ is the number of leading bits then zero sum is $N$-preserved if $| z(x) + z(y) - z(f(x,y))| \leq N$, I'm looking for $N \leq 3$, but $N \leq 6$ are good enough.
$\endgroup$
10
  • $\begingroup$ How is $27$ a good mapping for $(0, 0)$ since it does not have $128$ leading zeros? $\endgroup$
    – Nathaniel
    Commented Nov 25, 2022 at 13:27
  • $\begingroup$ I don't need a precise zero sum preservation $\endgroup$ Commented Nov 25, 2022 at 13:37
  • $\begingroup$ This is very unclear what you consider good or bad. Please be more precise in your post. $\endgroup$
    – Nathaniel
    Commented Nov 25, 2022 at 13:40
  • $\begingroup$ added exact requirement $\endgroup$ Commented Nov 25, 2022 at 13:44
  • $\begingroup$ What is $\text{bsr}$ ? $\endgroup$
    – user16034
    Commented Nov 25, 2022 at 17:18

1 Answer 1

1
$\begingroup$

Consider the sequence $S$ which enumerates pairs $\langle s,t \rangle$ of 64-bit strings, with the following ordering:

  • If $z(s)+z(t) < z(s')+z(t')$, then $\langle s,t \rangle$ is listed before $\langle s',t' \rangle$.

  • If $z(s)+z(t) = z(s')+z(t')$ and $z(s) < z(s')$, then $\langle s,t \rangle$ is listed before $\langle s',t' \rangle$.

  • If $z(s)=z(s')$ and $z(t)=z(t')$ and the concatenation $s\, t$ comes lexicographically before the concatenation $s' \, t'$, then $\langle s,t \rangle$ is listed before $\langle s',t' \rangle$.

Consider the sequence $T$ which enumerates 128-bit strings $u$, with the following ordering:

  • If $z(u) < z(u')$, then $u$ is listed before $u'$.

  • If $z(u)=z(u')$ and $u$ comes lexicographically before $u'$, then $u$ is listed before $u'$.

Now consider the mapping that maps from a pair $\langle s,t \rangle$ to its index in $S$, call the result $i$, then finds the $i$th item in $T$, and outputs the result. This then is a perfect hash function, and I believe it satisfies your desired property. Moreover, it is possible to compute both mappings (i.e., the ranking in $S$ and unranking in $T$) fairly efficiently. Therefore, the hash function can be computed fairly efficiently.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.