diff options
| author | Justus Winter <4winter@informatik.uni-hamburg.de> | 2014-05-08 18:33:57 +0200 |
|---|---|---|
| committer | Justus Winter <4winter@informatik.uni-hamburg.de> | 2014-05-13 21:36:18 +0200 |
| commit | 57341e5be12f79ee1916369679bb6507a10fcac9 (patch) | |
| tree | bbdbcb1e17aef48410a9ea2140a4783e34570459 /libihash/ihash.h | |
| parent | 2d898893815a980f1b821fcec267eb8e7ded678e (diff) | |
libihash: use linear probing and fast modulo operation
libihash uses open addressing. Previously, quadratic probing in both
directions was used to resolve collisions. Quadratic probing might
result in a less efficient use of caches.
Also, prime numbers of the form 4 * i + 3 were used as array sizes.
This was used in combination with the integer modulo operation for
hashing. It has been known for some time that libihash suffers from
collisions, so a integer hash function is now applied to the keys to
derive the index.
Use linear probing instead. Also, use powers of two for the array
sizes, so a bit mask can be used for the modulo operation.
* libihash/ihash.c (ihash_sizes, ihash_nsizes): Remove.
(find_index): Use linear probing and fast modulo operation.
(add_one): Likewise.
* libihash/ihash.h (HURD_IHASH_MIN_SIZE): New macro.
Diffstat (limited to 'libihash/ihash.h')
| -rw-r--r-- | libihash/ihash.h | 4 |
1 files changed, 4 insertions, 0 deletions
diff --git a/libihash/ihash.h b/libihash/ihash.h index a24f384d..8829e51e 100644 --- a/libihash/ihash.h +++ b/libihash/ihash.h @@ -93,6 +93,10 @@ typedef struct hurd_ihash *hurd_ihash_t; /* Construction and destruction of hash tables. */ +/* The size of the initial allocation in number of items. This must + be a power of two. */ +#define HURD_IHASH_MIN_SIZE 32 + /* The default value for the maximum load factor in percent. */ #define HURD_IHASH_MAX_LOAD_DEFAULT 75 |