[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [PATCH 2/7] libihash: use an integer hash function on the keys
From: |
Samuel Thibault |
Subject: |
Re: [PATCH 2/7] libihash: use an integer hash function on the keys |
Date: |
Tue, 13 May 2014 23:11:23 +0200 |
User-agent: |
Mutt/1.5.21+34 (58baf7c9f32f) (2010-12-30) |
Justus Winter, le Tue 13 May 2014 21:02:51 +0200, a écrit :
> Use an integer hash function to derive the index from the key. This
> should reduce the number of collisions.
Ack.
> * libihash/ihash.c (hash_int32): New function.
> (find_index): Use hash_int32 on the key to derive the index.
> (add_one): Likewise.
> ---
> libihash/ihash.c | 17 +++++++++++++++--
> 1 file changed, 15 insertions(+), 2 deletions(-)
>
> diff --git a/libihash/ihash.c b/libihash/ihash.c
> index d670fee..71ddc26 100644
> --- a/libihash/ihash.c
> +++ b/libihash/ihash.c
> @@ -81,6 +81,19 @@ static const unsigned int ihash_nsizes = (sizeof
> ihash_sizes
> / sizeof ihash_sizes[0]);
>
>
> +/* This is the integer finalizer from MurmurHash3. */
> +static inline uint32_t
> +murmur3_mix32 (uint32_t h, unsigned int bits)
> +{
> + h ^= h >> 16;
> + h *= 0x85ebca6b;
> + h ^= h >> 13;
> + h *= 0xc2b2ae35;
> + h ^= h >> 16;
> +
> + return h >> (32 - bits);
> +}
> +
> /* Return 1 if the slot with the index IDX in the hash table HT is
> empty, and 0 otherwise. */
> static inline int
> @@ -111,7 +124,7 @@ find_index (hurd_ihash_t ht, hurd_ihash_key_t key)
> unsigned int up_idx;
> unsigned int down_idx;
>
> - idx = key % ht->size;
> + idx = murmur3_mix32 (key, 32) % ht->size;
>
> if (ht->items[idx].value == _HURD_IHASH_EMPTY || ht->items[idx].key == key)
> return idx;
> @@ -264,7 +277,7 @@ add_one (hurd_ihash_t ht, hurd_ihash_key_t key,
> hurd_ihash_value_t value)
> unsigned int idx;
> unsigned int first_free;
>
> - idx = key % ht->size;
> + idx = murmur3_mix32 (key, 32) % ht->size;
> first_free = idx;
>
> if (ht->items[idx].value != _HURD_IHASH_EMPTY && ht->items[idx].key != key)
> --
> 2.0.0.rc0
>
--
Samuel
PS> Salut ! J'ai un sujet de philo à vous soumettre : "Suffit-il
PS> d'observer pour connaître" Idées + plan Merçi
Oui, ya qu'a t'observer pour connaître le fait que tu es une feignasse.
-+- FF in: Guide du Neuneu d'Usenet - Neuneu fait de la philo -+-
- [PATCH 1/7] libihash: fix type of max_load, Justus Winter, 2014/05/13
- [PATCH 3/7] libihash: use linear probing and fast modulo operation, Justus Winter, 2014/05/13
- [PATCH 2/7] libihash: use an integer hash function on the keys, Justus Winter, 2014/05/13
- Re: [PATCH 2/7] libihash: use an integer hash function on the keys,
Samuel Thibault <=
- [PATCH 4/7] libihash: use fast binary scaling to determine the load, Justus Winter, 2014/05/13
- [PATCH 5/7] include: add lock-less reference counting primitives, Justus Winter, 2014/05/13
- [PATCH 7/7] libtrivfs: lock-less reference counting for trivfs_peropen objects, Justus Winter, 2014/05/13