Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
From: Udit Gangwani <uditg22@gmail.com>
Newsgroups: comp.programming
Subject: Re: hash function over IP address
Date: Thu, 5 Apr 2012 00:26:19 -0700 (PDT)
Organization: http://groups.google.com
Lines: 70
Message-ID: <29326752.3937.1333610779671.JavaMail.geo-discussion-forums@pbtd1>
References: <jliber$ocn$1@speranza.aioe.org>
NNTP-Posting-Host: 182.68.185.114
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-Trace: posting.google.com 1333610873 15918 127.0.0.1 (5 Apr 2012 07:27:53 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Thu, 5 Apr 2012 07:27:53 +0000 (UTC)
In-Reply-To: <jliber$ocn$1@speranza.aioe.org>
Complaints-To: groups-abuse@google.com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=182.68.185.114; posting-account=U0_gigoAAACv7D4JcWRQdSx-ike7j7tv
User-Agent: G2/1.0
Xref: csiph.com comp.programming:1420

On Thursday, 5 April 2012 02:07:50 UTC+5:30, Mark  wrote:
> Hello
>=20
> I'm trying to find a way create a hash value over multiple IP addresses (=
I=20
> keep a list of IP addresses and its number is variable. The simplest meth=
od=20
> I've found so far is (obviously not the most effective and collision free=
):
>=20
> unsigned long hash_ipaddr(struct in_addr *addr)
> {
>     unsigned long res;
>=20
>     if (addr =3D=3D NULL)
>         return 0UL;
>=20
>     res =3D (((addr->s_addr >> 24) & 0xff) * 256) + \
>           (((addr->s_addr >> 16) & 0xff) * 256) + \
>           (((addr->s_addr >>  8) & 0xff)* 256) + \
>           (addr->s_addr & 0xff);
>=20
>     return res;
> }
>=20
> And then sum up hashes for every IP and store it.
>=20
> Can somebody suggest some better approach for my task?
> Thanks.
>=20
> Mark

Hashing is preferable if you have large number of keys and you know the num=
ber of keys before hand. In that case hashing gives you the best results. M=
oreover, Hashing is more common data structure for the purpose of indexing =
non-integral keys.=20

> I'm trying to find a way create a hash value over multiple IP addresses (=
I=20
> keep a list of IP addresses and its number is variable. The simplest meth=
od=20
> I've found so far is (obviously not the most effective and collision free=
):

In your case the number of IPAddresses are variable and your keys are integ=
ral.=20
So you can use these points for your benefit to use a more better approach.

1st Approach :=20
   If the number of IPAddress will not exceed a very large value( < 100000)=
, then you can use AVL Trees/Red Black Trees. If you are using C++, you can=
 use std::map<> data structure directly for this purpose.
These will give you in worst case the order of O(15-17) for Insertion, Dele=
tion and Searching. Plus it will save you a lot of time in creating your ow=
n hash data structure and making sure it is giving you best performance.=20

2nd Approach :
  If you know the range of you IP addresses, lets say between 192.168.0.0 t=
o 192.168.10.256. Then you can directly allocate an array of size of the nu=
mber of IP Addresses in this range. And you can perform the constant search=
ing by subtracting the minimum IP Address from your queried IP Address to g=
et the index into the array.=20

But if the above two approaches doesnot suit your needs then you can always=
 use some libraries which provide hash datastructures already implemented i=
n them.=20

For c++ check out this link :=20
http://attractivechaos.wordpress.com/2008/08/28/comparison-of-hash-table-li=
braries/