Date: Mon, 4 Jun 2012 11:10:47 +0200 From: enrico d'urso <e.durso@live.com> To: <freebsd-hackers@freebsd.org> Subject: RE: [Hash function Ipv4] Message-ID: <DUB116-W108B9A850E297FAE2951543970F0@phx.gbl> In-Reply-To: <12212.1338663660@critter.freebsd.dk> References: Your message of "Sat, 02 Jun 2012 20:14:34 %2B0200."
next in thread | previous in thread | raw e-mail | index | archive | help
Hi,
I did some tests with some subnets Ip /24 and I will share the results.
I got very good results with this configuration:
Hash table's size:
Let x be the number of ip.
Y = x*2, then
size_table = 'The power of 2 closest to Y, and greater than or equal to Y'.
Hash Function:
return Ip_in_network_byte_order % size_table;
Collision's case:
In this case i have used research quadratic:
((unsigned int)( hash_function + 0.5*k + 0.5*k*k )) % size_table ;
----------------------------------
on the other hand
When I have used Random Ip, that does not belong to the same subnet ip:
unsigned int HASH = 2039;
uint32_t h;
h = key % HASH;
key /= HASH;
h ^= key % HASH;
h ^= key / HASH;
Suggested to me by Poul-Henning Kamp (thanks) works much better.
That's all.
Bye
Enrico
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?DUB116-W108B9A850E297FAE2951543970F0>