| View previous topic :: View next topic |
| Author |
Message |
Bruza
Guest
|
 Posted: Tue Jul 29, 2008 8:20 am Post subject: Hash/permutation function for object ID creation |
 |
|
I need a system to generate a series of "semi-random-non-repeating"
32-bit object IDs. For this, I plan to create a sequence counter
(starting from 0), then feed the sequence number, s, to a permutation
function, F(s). And use F(s) as the generated object ID. F() needs to
have the following properties:
1. F(x) is semi-random so that if the ID is partitioned into any
number of "buckets" (by equal range, or MOD hashing), each bucket
has roughly same number of objects.
2. F() has an inverse F' s.t. F(F'(x)) = x
3. Both F() and F'() are computationally "inexpensive" to compute
I will appreciate any help or link for such algorithm. Thanks in
advance,
Bruza |
|
| |
|
 Back to top |
Kalle07
Guest
|
| Posted: Tue Jul 29, 2008 11:09 am Post subject: Re: Hash/permutation function for object ID creation |
|
|
On 29 Jul., 10:20, Bruza <benr...@gmail.com> wrote:
[quote]I need a system to generate a series of "semi-random-non-repeating"
32-bit object IDs. For this, I plan to create a sequence counter
(starting from 0), then feed the sequence number, s, to a permutation
function, F(s). And use F(s) as the generated object ID. F() needs to
have the following properties:
1. F(x) is semi-random so that if the ID is partitioned into any
number of "buckets" (by equal range, or MOD hashing), each bucket
has roughly same number of objects.
2. F() has an inverse F' s.t. F(F'(x)) = x
3. Both F() and F'() are computationally "inexpensive" to compute
Why not use the identity function? It is not semi-random at all, but[/quote]
using mod-based hash bucket assignment should work perfectly well. I
think giving a good answer to your question requires information why
identity won>t suffice. |
|
| |
|
| Back to top |
Guest
|
| Posted: Wed Jul 30, 2008 1:16 am Post subject: Re: Hash/permutation function for object ID creation |
|
|
On Jul 29, 4:20 am, Bruza <benr...@gmail.com> wrote:
[quote]I need a system to generate a series of "semi-random-non-repeating"
32-bit object IDs. For this, I plan to create a sequence counter
(starting from 0), then feed the sequence number, s, to a permutation
function, F(s). And use F(s) as the generated object ID. F() needs to
have the following properties:
1. F(x) is semi-random so that if the ID is partitioned into any
number of "buckets" (by equal range, or MOD hashing), each bucket
has roughly same number of objects.
2. F() has an inverse F' s.t. F(F'(x)) = x
3. Both F() and F'() are computationally "inexpensive" to compute
[/quote]
When I have to do this sort of thing for a simple hash table or
something, I usually do something simple like:
hash = ID+SOME_CONSTANT
hash *= SOME_ODD_CONSTANT
hash ^= (hash>>16)
hash ^= (hash>>8)
each line is reversible in modular arithmetic (mod 2^x), so the whole
function is reversible.
If you need something stronger, you can divide the ID into two halves
(L,R), and with a good hash function H(), do:
L' = L XOR H(R)
R' = R XOR H(L')
hash = (L',R')
This is called a Feistel network (googlable), and again each step is
obviously reversible.
Cheers,
Matt |
|
| |
|
| Back to top |
Bruza
Guest
|
| Posted: Wed Jul 30, 2008 1:51 am Post subject: Re: Hash/permutation function for object ID creation |
|
|
On Jul 29, 6:16 pm, matt.timmerm...@gmail.com wrote:
[quote]On Jul 29, 4:20 am, Bruza <benr...@gmail.com> wrote:
I need a system to generate a series of "semi-random-non-repeating"
32-bit object IDs. For this, I plan to create a sequence counter
(starting from 0), then feed the sequence number, s, to a permutation
function, F(s). And use F(s) as the generated object ID. F() needs to
have the following properties:
1. F(x) is semi-random so that if the ID is partitioned into any
number of "buckets" (by equal range, or MOD hashing), each bucket
has roughly same number of objects.
2. F() has an inverse F' s.t. F(F'(x)) = x
3. Both F() and F'() are computationally "inexpensive" to compute
When I have to do this sort of thing for a simple hash table or
something, I usually do something simple like:
hash = ID+SOME_CONSTANT
hash *= SOME_ODD_CONSTANT
hash ^= (hash>>16)
hash ^= (hash>>8)
each line is reversible in modular arithmetic (mod 2^x), so the whole
function is reversible.
If you need something stronger, you can divide the ID into two halves
(L,R), and with a good hash function H(), do:
L' = L XOR H(R)
R' = R XOR H(L')
hash = (L',R')
This is called a Feistel network (googlable), and again each step is
obviously reversible.
Cheers,
Matt
[/quote]
Matt,
Great! Feistel network seems to be what I want. Thanks for your help.
Bruza |
|
| |
|
| Back to top |
|
