Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #1420

Re: hash function over IP address

Show all headers | View raw

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

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

> I'm trying to find a way create a hash value over multiple IP addresses (I 
> keep a list of IP addresses and its number is variable. The simplest method 
> 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 integral. 
So you can use these points for your benefit to use a more better approach.

1st Approach : 
   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, Deletion and Searching. Plus it will save you a lot of time in creating your own hash data structure and making sure it is giving you best performance. 

2nd Approach :
  If you know the range of you IP addresses, lets say between 192.168.0.0 to 192.168.10.256. Then you can directly allocate an array of size of the number of IP Addresses in this range. And you can perform the constant searching by subtracting the minimum IP Address from your queried IP Address to get the index into the array. 

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

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

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

hash function over IP address "Mark" <mark_cruzNOTFORSPAM@hotmail.com> - 2012-04-04 16:37 -0400
  Re: hash function over IP address Barry Margolin <barmar@alum.mit.edu> - 2012-04-04 16:49 -0400
    Re: hash function over IP address China Blue Water Navy <chine.bleu@yahoo.com> - 2012-04-04 14:02 -0700
    Re: hash function over IP address "Mark" <mark_cruzNOTFORSPAM@hotmail.com> - 2012-04-04 17:21 -0400
      Re: hash function over IP address Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-04-04 14:47 -0700
  Re: hash function over IP address Ben Pfaff <blp@cs.stanford.edu> - 2012-04-04 14:40 -0700
    Re: hash function over IP address Rainer Weikusat <rweikusat@mssgmbh.com> - 2012-04-04 22:52 +0100
      Re: hash function over IP address blp@cs.stanford.edu (Ben Pfaff) - 2012-04-04 15:35 -0700
        Re: hash function over IP address Rainer Weikusat <rweikusat@mssgmbh.com> - 2012-04-05 12:08 +0100
          Re: hash function over IP address blp@cs.stanford.edu (Ben Pfaff) - 2012-04-05 07:42 -0700
            Re: hash function over IP address Rainer Weikusat <rweikusat@mssgmbh.com> - 2012-04-05 16:29 +0100
          Re: hash function over IP address Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-04-05 10:05 -0700
            Re: hash function over IP address Rainer Weikusat <rweikusat@mssgmbh.com> - 2012-04-05 18:12 +0100
              Re: hash function over IP address Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-04-05 10:23 -0700
                Re: hash function over IP address Rainer Weikusat <rweikusat@mssgmbh.com> - 2012-04-05 18:34 +0100
                Re: hash function over IP address Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-04-05 11:11 -0700
                Re: hash function over IP address Rainer Weikusat <rweikusat@mssgmbh.com> - 2012-04-05 19:34 +0100
                Re: hash function over IP address Rainer Weikusat <rweikusat@mssgmbh.com> - 2012-04-05 19:38 +0100
                Re: hash function over IP address Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-04-05 12:18 -0700
            Re: hash function over IP address scott@slp53.sl.home (Scott Lurndal) - 2012-04-05 18:45 +0000
              Re: hash function over IP address "Mark" <mark_cruzNOTFORSPAM@hotmail.com> - 2012-04-05 15:02 -0400
  Re: hash function over IP address Rick Jones <rick.jones2@hp.com> - 2012-04-04 23:18 +0000
  Re: hash function over IP address William Ahern <william@wilbur.25thandClement.com> - 2012-04-04 16:57 -0700
  Re: hash function over IP address Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-04-04 21:05 -0400
    Re: hash function over IP address Barry Margolin <barmar@alum.mit.edu> - 2012-04-04 22:52 -0400
      Re: hash function over IP address Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-04-05 08:46 -0400
    Re: hash function over IP address "Mark" <mark_cruzNOTFORSPAM@hotmail.com> - 2012-04-05 08:42 -0400
      Re: hash function over IP address Rainer Weikusat <rweikusat@mssgmbh.com> - 2012-04-05 15:04 +0100
        Re: hash function over IP address "Mark" <mark_cruzNOTFORSPAM@hotmail.com> - 2012-04-05 10:43 -0400
          Re: hash function over IP address Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-04-05 22:24 -0400
          Re: hash function over IP address Rainer Weikusat <rweikusat@mssgmbh.com> - 2012-04-06 17:13 +0100
            Re: hash function over IP address Rainer Weikusat <rweikusat@mssgmbh.com> - 2012-04-06 17:21 +0100
            Re: hash function over IP address "Mark" <mark_cruzNOTFORSPAM@hotmail.com> - 2012-04-09 10:04 -0400
              Re: hash function over IP address Rainer Weikusat <rweikusat@mssgmbh.com> - 2012-04-09 15:54 +0100
  Re: hash function over IP address BGB <cr88192@hotmail.com> - 2012-04-04 20:21 -0700
  Re: hash function over IP address Udit Gangwani <uditg22@gmail.com> - 2012-04-05 00:26 -0700
  Re: hash function over IP address Rainer Weikusat <rweikusat@mssgmbh.com> - 2012-04-05 12:15 +0100
    Re: hash function over IP address Barry Margolin <barmar@alum.mit.edu> - 2012-04-05 07:52 -0400

csiph-web