Teen Programmers Unite  


Return to forum top

minimal perfect hashing

Posted by ktprktpr [send private reply] at May 27, 2003, 09:28:51 PM


I'm trying to write a script that establishes a one to one relationship between points on two objects. If two points have the same value then they have a 1-1 relationship (fyi these are points in 3d space). I know before hand how many points there are on each object so I can create an array that can hold all the values.

Isn't there a way to perfectly hash these values to fit w/in the size of the array w/o collision. If so could some one kindly exlplain it to me.

thanks for your time

Posted by DragonWolf [send private reply] at May 28, 2003, 04:46:41 AM

dunno what language your doing this in, nor does what you say make much sense to me.

But it sounds like Linked Lists and Pointers could solve this.

Posted by Psion [send private reply] at May 28, 2003, 06:44:29 AM

Have you searched the web & USENET for "perfect hash"?

Posted by ktprktpr [send private reply] at May 29, 2003, 03:54:46 PM

thanks for the replies!

Actually I found a better way: all I need are dynamic variables. If i can create a dynamic variable for every interesting piece of data and store wahtever I want in it I would have O(1) insert, delete and retrieval. The only catch is that I need to store the names of these variables or else they are lost forever.

Basically, I just use the program stack as my data structure and create variables. The only catch is I could overflow teh stack if i had to many variables. heheh.

I did look around for perfect hashing and I was told that it was pretty hard to create such a hash function so its not worth my name.

All of this is useful for storing values that you don't know exist, like a data in a data set. For each commonality in data, create a dynamic variable that names it. Then attach whatever common data to the variable and you have the quick insert/delete/acccess times I talked about.


You must be logged in to post messages and see which you have already read.

Log on
Save for later automatic logon

Register as a new user
Copyright TPU 2002. See the Credits and About TPU for more information.