# Hashing pointers

This topic is 5227 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites
If you know all the pointers in advance, then yes, there is. If not, then no, there isn't.

##### Share on other sites
How about just casting them to an int and then hashing them?

##### 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 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".

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 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

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 on other sites
It's for a memory manager, where every piece of memory is hashed. Yes, I know, that I should shift off the low bits due to the boundaries.

1. 1
2. 2
3. 3
Rutin
22
4. 4
5. 5
khawk
14

• 9
• 11
• 11
• 23
• 10
• ### Forum Statistics

• Total Topics
633651
• Total Posts
3013135
×