From owner-freebsd-hackers@FreeBSD.ORG Mon Jun 4 09:11:56 2012 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [69.147.83.52]) by hub.freebsd.org (Postfix) with ESMTP id 46B37106566B for ; Mon, 4 Jun 2012 09:11:56 +0000 (UTC) (envelope-from e.durso@live.com) Received: from dub0-omc2-s7.dub0.hotmail.com (dub0-omc2-s7.dub0.hotmail.com [157.55.1.146]) by mx1.freebsd.org (Postfix) with ESMTP id CE68B8FC12 for ; Mon, 4 Jun 2012 09:11:55 +0000 (UTC) Received: from DUB116-W108 ([157.55.1.138]) by dub0-omc2-s7.dub0.hotmail.com with Microsoft SMTPSVC(6.0.3790.4675); Mon, 4 Jun 2012 02:10:47 -0700 Message-ID: X-Originating-IP: [2.231.157.89] From: enrico d'urso To: Date: Mon, 4 Jun 2012 11:10:47 +0200 Importance: Normal In-Reply-To: <12212.1338663660@critter.freebsd.dk> References: Your message of "Sat, 02 Jun 2012 20:14:34 +0200." X-OriginalArrivalTime: 04 Jun 2012 09:10:47.0537 (UTC) FILETIME=[EDE0B610:01CD4231] Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable X-Content-Filtered-By: Mailman/MimeDel 2.1.5 Subject: RE: [Hash function Ipv4] X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 04 Jun 2012 09:11:56 -0000 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 =