X-Git-Url: http://git.tuebingen.mpg.de/?p=adu.git;a=blobdiff_plain;f=adu.c;h=8068d205f2274dded3074158a105243bb4de1b11;hp=f8096fb8aade93fbbb4769df503c57efafc6cf3b;hb=6c043b44a1cec206f3b4f8063fb8383e66ae6d53;hpb=36c4bc7aee504a7d76471ca7bf5a0a49ed314e26

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)