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?

-
I'm not an expert, but perhaps you can use a pseudorandom permutation (see for example the Feistel cipher) –  Vor Nov 14 '12 at 23:40
If you are essentially computing a hash function, why not use hashing? –  vonbrand Jan 28 at 23:18
@vonbrand Hashing is not reversible. See requirement number 2. –  FUZxxl Jan 28 at 23:31
Why does it have to be reversible? What is wrong with making it reversible by lookup? –  vonbrand Jan 29 at 1:25