Re: hash function over IP address

From	Eric Sosman <esosman@ieee-dot-org.invalid>
Newsgroups	comp.programming, comp.unix.programmer
Subject	Re: hash function over IP address
Date	2012-04-04 21:05 -0400
Organization	A noiseless patient Spider
Message-ID	<jlir5m$dd8$1@dont-email.me> (permalink)
References	<jliber$ocn$1@speranza.aioe.org>

Cross-posted to 2 groups.

Show all headers | View raw

On 4/4/2012 4:37 PM, 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);

     (Idle question: Why the backslashes?)

>      return res;

     Briefly, this calculation takes four chunks of the address
as numbers between 0..255 and adds them to produce a sum 0..1020.
So: You start with 32 bits of information and squash them down to
a smidgen less than 10 bits -- with a moderate central tendencey,
too.  Ponder, young one: Wise this is?

> }
>
> And then sum up hashes for every IP and store it.

     Not sure what you mean by this.  A given IP produces one and
only one hash value with this scheme (or any other sane scheme),
so what do you mean by "sum up the hashes?"

> Can somebody suggest some better approach for my task?

     You haven't explained what your task is, so I'll have to guess.
If the objective is to use a hash table keyed on IP addresses, there
are two likely possibilities:

     - The number of buckets in the table is a prime number (or at
       the very least an odd number): Just take `*addr % N', and the
       outcome is very likely to be better, especially if N > 1020.
       The remainder after division by a prime is likely to break up
       simple patterns.

     - The number of buckets is a power of two. Now `*addr % N' would
       just throw away the high-order bits -- which might not be Bad,
       but could easily be Less Than Good if there are patterns in the
       input keys.  One possibility is to use `f(*addr) % N', where f()
       is a suitable "scrambling" function: For example, implement a
       two-line linear congruential pseudo-random number generator, seed
       it with `*addr', and take its output as f().

     For further ideas, see TAOCP volume III.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

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