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

Groups > comp.programming > #1438

Re: hash function over IP address

Cross-posted to 2 groups.

Show all headers | View raw

Daniel Pitts <newsgroup.nospam@virtualinfinity.net> writes:
>On 4/5/12 4:08 AM, Rainer Weikusat wrote:
>> blp@cs.stanford.edu (Ben Pfaff) writes:
>>> Rainer Weikusat<rweikusat@mssgmbh.com>  writes:
>>>
>>>> Ben Pfaff<blp@cs.stanford.edu>  writes:
>>>>> "Mark"<mark_cruzNOTFORSPAM@hotmail.com>  writes:
>>>>>
>>>>>> 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):
>>>>>
>>>>> Why not use one of many available high-quality hash functions?
>>>>> Three that come to mind without even going to a search engine:
>>>>> Jenkins lookup3, murmurhash, FNV.
>>>>
>>>> The simple answer is these hash functions are designed to be used for
>>>> large, variable length string keys NOT for small, fixed-size
>>>> quantities which can be compared with a single machine instruction.
>>>>
>>>> http://burtleburtle.net/bob/hash/integer.html
>>>> http://www.cris.com/~Ttwang/tech/inthash.htm
>>>
>>> He has a list of multiple IP addresses.  A hash function for
>>> variable length keys may well be appropriate.
>>
>> Calculating the hash value must be cheaper than the full comparisons
>> which will be needed for a linear search.
>Really? How do you hash a string then? The point of a hash function is 
>often (not always) used to determine a bucket to look into.  It needn't 
>be faster than a comparison, and actually is often slower. 

>Cryptographically strong hashes are significantly slower than that 
>usually.

This seems a bit of a non sequitur - crytpographic hashes aren't used
for bucket selection.

I'd be interested in more data about the original posters problem:

  - How many entries will his "AVL tree" contain over time?
  - What type of system does the software run on (embedded 1Ghz
    processor or core I7 at 3.5Ghz?)
  - What is the frequency (over time) of the various search, insert
    and delete operations?

>
>Often performance of the program is not dominated by the speed of the 
>hash-function, but the number of collisions created by it.  Having a 
>hash-function that is 10 times slower than a comparison, but creates an 
>even spread will generally outperform the "fastest" hash.  If you want a 
>fast hash, "return 0;"

  I think many people would be surprised that simple O(N) algorithms would
  be of suitable performance for many problems where more complicated data
  structures are designed (e.g. a linear table lookup instead of an AVL or R/B tree
  or hash buckets).

  Of course, if the OP is building a core router, then a hardware CAM may
  be the most appropriate solution.

scott

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