Subject: [core] hash clash probabilities

From: peter van der Stok <[email-masked]>
Date: Wed, 29 Jul 2015 11:51:58 +0200

Hi all,

Given the discussion about the use of bits in the URI for CoMI,
it is reasonable to look at the probability that a hash clash occurs,

In the attached table I set out the clash probability of the number of 
names in a server versus the hash size.
Currently the hash size is 30 bits and is proposed to be reduced to 29.

The table show that by removing a bit in the hash, the clash probability 
increases with a factor 2

with 5.000 names and a 30 bit hash, the clash probability in one server 
is 10%
With 30.000 names and a 32 bit hash value the clash probability in one 
server is also 10%

A higher probability than 10% looks unwanted to me and a probability of 
1% looks adequate to keep the client re-hash table size small.

To estimate the size of the hash, the number of names per server should 
be estimated.
A hash size of 29 seems reasonable when the expected number of names per 
server remains smaller than 3000.

Has anybody an idea about the number of names in a reduced resource 
server?

Looking forward to your reaction,

Peter

-- 
Peter van der Stok
vanderstok consultancy
mailto: [email-masked]
www: www.vanderstok.org
tel NL: +31(0)492474673     F: +33(0)966015248