Sign in to follow this  
OleKaiwalker

Hashing pointers

Recommended Posts

Hey, Any good way to hash memory pointers without making any collision and without enormous waste of space? The allocations are normally allocated as => 32 bytes

Share this post


Link to post
Share on other sites
Why are you worrying about collisions? Any good hashtable class will resize itself to have at most C elements in the same bucket, where C is a fixed constant, so you still have constant time operations.

Share this post


Link to post
Share on other sites
Quote:
Any good way to hash memory pointers without making any collision and without enormous waste of space?


First I dont know any other pointers than "memory pointers".

Second I bet you want to hash the data pointed by the pointer, not the pointer itself, don't you? You're question should be "Any good way to hash some datas without making any collision and without enormous waste of space".

Answer to this question:
What is a hash algorithm ? a function that takes some data and output an int (well, it could output something else, but let start with an int). An int can take 2^32 values (let say). There is NO hash algorithm that takes data that can be in more than 2^32 different states, and that doesnt make any collision. It is mathematically IMPOSSIBLE.

Share this post


Link to post
Share on other sites
Do you use a fixed power of 2 hash table size?
If so I recommend using a multiplicative hash function,
assuming your pointers are 32 bit wide do
(address * 2654435769) >> SHIFT_BITS

where SHIFT_BITS is 32 - log2(hash table size)

2654435769 is recommended by Knuth and it is the golden ratio given by 2^32 * (sqrt(5)-1)/2

You can try to shift off some bits of the address (rightshift) because most addresses will be allocated on 8 byte boundaries and see if this gives you better results.

You can't have no collisions and a small hash table unless you have a small address space that you're going to cover, maybe you can get more specific about the memory pointers you want to hash?
Also the function above is said to work well for small address values only. This means you could subtract the lowest address of your applications address space.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this