diff options
| author | Eric Anholt <eric@anholt.net> | 2011-08-18 08:58:34 -0700 |
|---|---|---|
| committer | Eric Anholt <eric@anholt.net> | 2011-08-18 09:00:40 -0700 |
| commit | 1bb8bdb4653e9b05706901fe01012eb170ee0500 (patch) | |
| tree | 3aaeefbffaf3089271102882819b02fa335d605a | |
| parent | c2ede6fb0872286244cc2bf08b2159ec348e3300 (diff) | |
Improve double hashing.
Because of the double_hash == 0 check, the step size of 1 would have
twice the frequency of any other. With the table size being prime
numbers, any integer is co-prime with the table size, so any nonzero
step number will end up hitting every element of the hash table.
Based on a patch by Andrea Canciani to the X Server.
| -rw-r--r-- | hash_table.c | 8 |
1 files changed, 2 insertions, 6 deletions
diff --git a/hash_table.c b/hash_table.c index e0e44a0..6367ea3 100644 --- a/hash_table.c +++ b/hash_table.c @@ -179,9 +179,7 @@ hash_table_search(struct hash_table *ht, uint32_t hash, const void *key) } } - double_hash = hash % ht->rehash; - if (double_hash == 0) - double_hash = 1; + double_hash = 1 + hash % ht->rehash; hash_address = (hash_address + double_hash) % ht->size; } while (hash_address != hash % ht->size); @@ -257,9 +255,7 @@ hash_table_insert(struct hash_table *ht, uint32_t hash, return entry; } - double_hash = hash % ht->rehash; - if (double_hash == 0) - double_hash = 1; + double_hash = 1 + hash % ht->rehash; hash_address = (hash_address + double_hash) % ht->size; } while (hash_address != hash % ht->size); |