14
$\begingroup$

I'd like to know if there is a function $f$ from n-bit numbers to n-bit numbers that has the following characteristics:

  • $f$ should be bijective
  • Both $f$ and $f^{-1}$ should be calculable pretty fast
  • $f$ should return a number that has no significant correlation to its input.

The rationale is this:

I want to write a program that operates on data. Some information of the data is stored in a binary search tree where the search key is a symbol of an alphabet. With time, I add further symbols to the alphabet. New symbols simply get the next free number available. Hence, the tree will always have a small bias to smaller keys which causes more rebalancing than I think should be needed.

My idea is to mangle the symbol numbers with $f$ such that they are widely spread over the whole range of $[0,2^{64}-1]$. Since the symbol numbers only matter during input and output which happens only once, applying such a function should not be too expensive.

I thought about one iteration of the Xorshift random number generator, but I don't really know a way to undo it, although it should theoretically be possible.

Does anybody know such a function?
Is this a good idea?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ I'm not an expert, but perhaps you can use a pseudorandom permutation (see for example the Feistel cipher) $\endgroup$ – Vor Nov 14 '12 at 23:40
  • $\begingroup$ If you are essentially computing a hash function, why not use hashing? $\endgroup$ – vonbrand Jan 28 '13 at 23:18
  • $\begingroup$ @vonbrand Hashing is not reversible. See requirement number 2. $\endgroup$ – FUZxxl Jan 28 '13 at 23:31
  • $\begingroup$ Why does it have to be reversible? What is wrong with making it reversible by lookup? $\endgroup$ – vonbrand Jan 29 '13 at 1:25
  • 1
    $\begingroup$ You can store (f(x),x) as keys. $\endgroup$ – adrianN Mar 5 '13 at 16:57
6
$\begingroup$

You can use Fibonacci hashing, namely

$\qquad h_F(k) = k \cdot \frac{\sqrt{5} - 1}{2} - \left\lfloor k \cdot \frac{\sqrt{5} - 1}{2} \right\rfloor$.

For $k=1,\dots,n$ you get $n$ pairwise-distinct numbers (about) evenly spread in $[0,1]$. By scaling to $[1..M]$ and rounding (down), you get about evenly spread numbers in that interval.

For example, these are $h_F(1), \dots, h_F(200)$ scaled to $[0..10000]$ (left original sequence, right sorted):

enter image description here

This is an instance of what Knuth calls multiplicative hashing. For $w$ the computer's word size, $A$ some integer relatively prime to $w$ and $M$ the number of addresses needed, we use

$\qquad h(k) = \left\lfloor M \left( \bigl( k \cdot \frac{A}{w}\bigr) \mod 1 \right) \right\rfloor$

as hashing function. The above follows with $A/w = \phi^{-1} = \frac{\sqrt{5}-1}{2}$ (make sure you can compute it with a sufficient precision). While this also works with any other irrational number besides $\phi^{-1}$, it is one of only two numbers that lead to the "most uniformly distributed" numbers.

Find more in The Art of Computer Programming, Volume 3 by Donald Knuth (chapter 6.4 from page 513 in the second edition). In particular you'll find why the resulting numbers are pairwise distinct (at least if $n \ll M$) and how to compute the inverse function if you use natural $A$ and $w$ instead of $\phi^{-1}$.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ How to calculate $f^{-1}$ efficiently? $\endgroup$ – frafl Mar 5 '13 at 15:22
  • 1
    $\begingroup$ @frafl I hope my edit addresses your concern somewhat. It's clear, though, that these hashing techniques are nor particularly designed to be efficiently invertible. $\endgroup$ – Raphael♦ Mar 5 '13 at 17:13
  • $\begingroup$ Yes it does, I'll upvote it, however I would not recommend it as the accepted answer. $\endgroup$ – frafl Mar 6 '13 at 11:18
1
$\begingroup$

For $k$-bit inputs, this function works:

$\mathrm{hash}(n) = (n \bmod 2^{\lceil\frac{k}{2}\rceil})\cdot 2^{\lceil\frac{k}{2}\rceil} + n \,\mathrm{div}\, 2^{\lceil\frac{k}{2}\rceil}$

This is reversible, in that $\mathrm{hash}(\mathrm{hash}(n)) = n$, and has non-sequential pairs $\{n,m\}, n < m$, where $\mathrm{hash}(m) < \mathrm{hash}(n)$. Beware that output and input may correlate, especially if your input is in $\{1,\dots,2^{\lceil\frac{k}{2}\rceil}-1\}$.

Ref: Reversible hash function

|cite|improve this answer
$\endgroup$
  • $\begingroup$ This looks simple and nice. I'm going to test that one. $\endgroup$ – FUZxxl Jan 31 '13 at 8:03
  • 1
    $\begingroup$ 1. Depending on the input, it may produce heavy correlation (up to $1$ for Spearman's $\rho$) 2. This is for 32 bits, not for 64 bits 3. Could you please write this in a language-independent way? $\endgroup$ – frafl Mar 5 '13 at 15:19
  • $\begingroup$ it's pretty clear! for 64-bit (0x00000000FFFFFFFF) and you should shift(<<) 32 bits. This function is simple, practical and fast enough in practice. $\endgroup$ – Reza Mar 5 '13 at 18:36
  • 1
    $\begingroup$ But why don't you use a permutation of the bits, that does not map every $x \in \{1,\dots,2^{32}-1\}$ to $2^{32}x$? As stated above this clearly violates the correlation condition demanded by the OP. $\endgroup$ – frafl Mar 6 '13 at 11:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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