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=2C
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:=20
Let x be the number of ip.
Y =3D x*2=2C then=20
size_table =3D 'The power of 2 closest to Y=2C and greater than or equal to=
Y'.
Hash Function:=20
return Ip_in_network_byte_order % size_table=3B
Collision's case:
In this case i have used research quadratic:
((unsigned int)( hash_function + 0.5*k + 0.5*k*k )) % size_table =3B
----------------------------------
on the other hand
When I have used Random Ip=2C that does not belong to the same subnet ip:
unsigned int HASH =3D 2039=3B
uint32_t h=3B=20
h =3D key % HASH=3B
key /=3D HASH=3B
h ^=3D key % HASH=3B
h ^=3D key / HASH=3B=20
Suggested to me by Poul-Henning Kamp (thanks) works much better.
That's all.
Bye
Enrico=20
=
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?DUB116-W108B9A850E297FAE2951543970F0>