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?