diff options
| author | Andrea Canciani <ranma42@gmail.com> | 2011-08-01 18:18:31 +0200 |
|---|---|---|
| committer | Andrea Canciani <ranma42@gmail.com> | 2011-08-01 19:21:31 +0200 |
| commit | 02665975d3ef0204bc512de1be55f898637f2d21 (patch) | |
| tree | 0f91d1900a41e050d1892c59d948c1a46ae57cbb | |
| parent | c5405f732410fe851b8d4c73365336ec2490358b (diff) | |
hash: Improve double hashing
Instead of artificially introducing collisions in the step value by
replacing 0 with 1 (which causes the value 1 to have twice the
frequency of any other value), the step value can simply be computed
as an uniformly distributed value in the range [1, rehash], extremes
included.
This is safe because any step value smaller than the hash modulus is
co-prime with it, hence induces an orbit which includes every integer
in [0, table_size - 1].
| -rw-r--r-- | src/cairo-hash.c | 18 |
1 files changed, 5 insertions, 13 deletions
diff --git a/src/cairo-hash.c b/src/cairo-hash.c index 81a48a235..7cab89d90 100644 --- a/src/cairo-hash.c +++ b/src/cairo-hash.c @@ -72,7 +72,7 @@ * prime chosen to be a little more than double the high water mark for a * given arrangement, so the tables should remain < 50% full. The table * size makes for the "first" hash modulus; a second prime (2 less than the - * first prime) serves as the "second" hash modulus, which is co-prime and + * first prime) serves as the "second" hash modulus, which is smaller and * thus guarantees a complete permutation of table indices. * * This structure, and accompanying table, is borrowed/modified from the @@ -218,9 +218,7 @@ _cairo_hash_table_lookup_unique_key (cairo_hash_table_t *hash_table, return entry; i = 1; - step = key->hash % hash_table->arrangement->rehash; - if (step == 0) - step = 1; + step = 1 + key->hash % hash_table->arrangement->rehash; do { idx += step; if (idx >= table_size) @@ -324,9 +322,7 @@ _cairo_hash_table_lookup (cairo_hash_table_t *hash_table, return NULL; i = 1; - step = key->hash % hash_table->arrangement->rehash; - if (step == 0) - step = 1; + step = 1 + key->hash % hash_table->arrangement->rehash; do { idx += step; if (idx >= table_size) @@ -381,9 +377,7 @@ _cairo_hash_table_random_entry (cairo_hash_table_t *hash_table, return entry; i = 1; - step = hash % hash_table->arrangement->rehash; - if (step == 0) - step = 1; + step = 1 + hash % hash_table->arrangement->rehash; do { idx += step; if (idx >= table_size) @@ -455,9 +449,7 @@ _cairo_hash_table_lookup_exact_key (cairo_hash_table_t *hash_table, return entry; i = 1; - step = key->hash % hash_table->arrangement->rehash; - if (step == 0) - step = 1; + step = 1 + key->hash % hash_table->arrangement->rehash; do { idx += step; if (idx >= table_size) |