Re: Efficient way to store an isomorphism?

Hi,

> Yes, but it takes O(n) space to store the hash function. It's still
> advantageous if you have time to compute the hash function beforehand,
> because lookups are actually O(1) worst case.
>
> Google for "minimal perfect hashing". Many minimal perfect hashing
> algorithms let you choose the mapping precisely. This one is my favourite:
>
> http://citeseer.ist.psu.edu/czech92optimal.html

Thank you for your reply. I did not realise that these minimal perfect
hashing schemes allowed one to choose the mapping (it's been a while
I've studied this stuff :-)

I've read the paper you recommended and it indeed does what I need, so
thank you for that. However, I'm wondering, is it possible to better
than the method in the paper, in terms of the space required to store
the hash function? Or can it be shown that such an improvement is not
possible?

Thanks again,

Edsko

.

Relevant Pages

  • Re: Efficient way to store an isomorphism?
    ... we should be able to store the hash function in less than ... because lookups are actually Oworst case. ... Google for "minimal perfect hashing". ...
    (comp.theory)
  • Efficient way to store an isomorphism?
    ... if "n" is the size of both sets, it takes Ospace to store the array ... Now we can do lookups in Otime, but we still need Ospace ... to store the array (assuming that storing the hash function takes less ...
    (comp.theory)
  • Re: Is "identify" really good for the game?
    ... Use the 2-3 bytes you store as the seed for an RNG. ... a hash function from your object space down to the 2-3 bytes you want ... POWDER does something very similar to this. ...
    (rec.games.roguelike.development)