From 6c043b44a1cec206f3b4f8063fb8383e66ae6d53 Mon Sep 17 00:00:00 2001 From: Andre Noll Date: Mon, 26 May 2008 02:04:40 +0200 Subject: [PATCH] Add documentation for double_hash(). --- adu.c | 17 ++++++++++++++++- 1 file changed, 16 insertions(+), 1 deletion(-) diff --git a/adu.c b/adu.c index f8096fb..8068d20 100644 --- a/adu.c +++ b/adu.c @@ -299,7 +299,22 @@ static int create_tables(void) return 1; } - +/* + * We use a hash table of size s=2^uid_hash_bits to map the uids into the + * interval [0..s]. Hash collisions are treated by open addressing, i.e. + * unused slots in the table are used to store different uids that hash to the + * same slot. + * + * If a hash collision occurs, different slots are successively probed in order + * to find an unused slot for the new uid. Probing is implemented via a second + * hash function that maps the uid to h=(uid * PRIME2) | 1, which is always an + * odd number. + * + * An odd number is sufficient to make sure each entry of the hash table gets + * probed for probe_num between 0 and s-1 because s is a power of two, hence + * the second hash value never hash a common divisor with the hash table size. + * IOW: h is invertible in the ring [0..s]. + */ static uint32_t double_hash(uint32_t uid, uint32_t probe_num) { return (uid * PRIME1 + ((uid * PRIME2) | 1) * probe_num) -- 2.39.2