Key Hashing
- From: Daniel Rudy <spamthis@xxxxxxxxxxxx>
- Date: Thu, 22 Mar 2007 09:30:36 GMT
Hello Group,
What is the best function to perform a key hash?
I'm current using this:
#include <machine/param.h>
/* computes hash value from pointer */
uint32 psm_hashkey(void *p)
{
uint32 hash;
uint32 x;
/* XXX converting a pointer to an uint32 may not
always work on a non-IA32 platform. platform
specific code may be required when doing this.
*/
#if _MACHINE_ARCH==i386
x = (uint32)p;
#else
#error Machine type not supported
#endif
hash = x % PSM_TABLESIZE;
return(hash);
}
I have tried other types of formulas, include math problems out of
textbooks like:
hash = ((5 * x * x) + (3 * x) - 5) % PSM_TABLESIZE;
hash = ((2 * x * x * x * x) + (4 * x * x * x) - (8 * x * x)
+ (3 * x) - 11) % PSM_TABLESIZE;
The results were mixed...I also tried adding a boolean/exponent pair to
the formula like this:
hash = ((x * x) ^ x) % PSM_TABLESIZE;
PSM_TABLESIZE is 2441 which is a prime number between 2^11 and 2^12.
The data sets are generated using malloc with random sizes of the range
128 <= x < 4096 bytes. Any ideas? Below are some run results for my
current hash function. The clustering is computed as 100 * (cluster /
(table size - empty entries)) where cluster is the number of buckets
that has that number of entries in it.
strata:/home/dr2867/c/modules 1124 $$$ ->./psmalloc.test
First Collision Data
orders: 262
table size: 2441
collisions: 1
blank entries: 2180
load factor: 10.69234%
collision factor: 0.38314%
Final Collision Data
orders: 4096
table size: 2441
collisions: 1675
blank entries: 20
load factor: 99.18066%
collision factor: 69.18629%
clustering data:
max cluster size: 6
count 1129; size 1; cluster 46.63362%
count 960; size 2; cluster 39.65303%
count 287; size 3; cluster 11.85461%
count 40; size 4; cluster 1.65221%
count 4; size 5; cluster 0.16522%
count 1; size 6; cluster 0.04131%
strata:/home/dr2867/c/modules 1125 $$$ ->./psmalloc.test
First Collision Data
orders: 256
table size: 2441
collisions: 1
blank entries: 2186
load factor: 10.44654%
collision factor: 0.39216%
Final Collision Data
orders: 4096
table size: 2441
collisions: 1670
blank entries: 15
load factor: 99.38550%
collision factor: 68.83759%
clustering data:
max cluster size: 5
count 1123; size 1; cluster 46.29019%
count 984; size 2; cluster 40.56059%
count 276; size 3; cluster 11.37675%
count 38; size 4; cluster 1.56636%
count 5; size 5; cluster 0.20610%
strata:/home/dr2867/c/modules 1126 $$$ ->./psmalloc.test
First Collision Data
orders: 248
table size: 2441
collisions: 1
blank entries: 2194
load factor: 10.11880%
collision factor: 0.40486%
Final Collision Data
orders: 4096
table size: 2441
collisions: 1669
blank entries: 14
load factor: 99.42647%
collision factor: 68.76803%
clustering data:
max cluster size: 5
count 1136; size 1; cluster 46.80676%
count 963; size 2; cluster 39.67862%
count 280; size 3; cluster 11.53688%
count 46; size 4; cluster 1.89534%
count 2; size 5; cluster 0.08241%
--
Daniel Rudy
Email address has been base64 encoded to reduce spam
Decode email address using b64decode or uudecode -m
Why geeks like computers: look chat date touch grep make unzip
strip view finger mount fcsk more fcsk yes spray umount sleep
.
- Follow-Ups:
- Re: Key Hashing
- From: Rob Thorpe
- Re: Key Hashing
- From: user923005
- Re: Key Hashing
- From: W Karas
- Re: Key Hashing
- From: bytebro
- Re: Key Hashing
- Prev by Date: Re: counting nodes in BST
- Next by Date: Re: Key Hashing
- Previous by thread: Re: which shoild i learn 1st learn procedural or modular programming OOD
- Next by thread: Re: Key Hashing
- Index(es):
Relevant Pages
|
