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

Groups > comp.programming > #1405 > unrolled thread

hash function over IP address

Back to article view | Back to comp.programming

Contents

  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

Page 1 of 2  [1] 2  Next page →

#1405 — hash function over IP address

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 

[toc] | [next] | [standalone]

#1406

In article <jliber$ocn$1@speranza.aioe.org>,
 "Mark" <mark_cruzNOTFORSPAM@hotmail.com> 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.

How about s_addr % modulus, where modulus is a large (> 2^16) prime 
number?

-- 
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

[toc] | [prev] | [next] | [standalone]

#1407

In article <barmar-B6E941.16490504042012@news.eternal-september.org>,
 Barry Margolin <barmar@alum.mit.edu> wrote:

> In article <jliber$ocn$1@speranza.aioe.org>,
>  "Mark" <mark_cruzNOTFORSPAM@hotmail.com> 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.
> 
> How about s_addr % modulus, where modulus is a large (> 2^16) prime 
> number?

If you want to avoid division, the center product includes all the bits:

    factor1 := (address>>16) & 0xFFFF;          16 bit factor
    factor2 := (address    ) & 0xFFFF;          16 bit factor
    product := factor1 * factor2;               32 bit product
    centerproduct := (product>>8) & 0xFFFF;     16 bits from the center

-- 
My name Indigo Montoya.      |    R'lyeh 38o57'6.5''S 102o51'16''E.
You flamed my father.        |       I'm whoever you want me to be.
Prepare to be spanked.       |  Annoying Usenet one post at a time.
Stop posting that!           |    At least I can stay in character.

[toc] | [prev] | [next] | [standalone]

#1408

"Barry Margolin" <barmar@alum.mit.edu> wrote in message 
news:barmar-B6E941.16490504042012@news.eternal-september.org...
[skip]
>> And then sum up hashes for every IP and store it.
>>
>> Can somebody suggest some better approach for my task?
>> Thanks.
>
> How about s_addr % modulus, where modulus is a large (> 2^16) prime
> number?
>

Thanks for suggestion. Is it common approach to sum up the produced hashes?

Mark 

[toc] | [prev] | [next] | [standalone]

#1410

On 4/4/12 2:21 PM, Mark wrote:
> "Barry Margolin"<barmar@alum.mit.edu>  wrote in message
> news:barmar-B6E941.16490504042012@news.eternal-september.org...
> [skip]
>>> And then sum up hashes for every IP and store it.
>>>
>>> Can somebody suggest some better approach for my task?
>>> Thanks.
>>
>> How about s_addr % modulus, where modulus is a large (>  2^16) prime
>> number?
>>
>
> Thanks for suggestion. Is it common approach to sum up the produced hashes?

If order matters, what I've seen is basically the following:

for each item in list:
    hash = hash * someSmallPrime + hashOf(item)

[toc] | [prev] | [next] | [standalone]

#1409

"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.
-- 
Ben Pfaff 
http://benpfaff.org

[toc] | [prev] | [next] | [standalone]

#1411

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

[toc] | [prev] | [next] | [standalone]

#1412

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.
-- 
Peter Seebach on managing engineers:
"It's like herding cats, only most of the engineers are already
 sick of laser pointers."

[toc] | [prev] | [next] | [standalone]

#1421

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. And performing extensive
byte-shuffling on machine words is not a good strategy to achieve
that.

[toc] | [prev] | [next] | [standalone]

#1428

Rainer Weikusat <rweikusat@mssgmbh.com> writes:

> 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. And performing extensive
> byte-shuffling on machine words is not a good strategy to achieve
> that.

You suggested http://burtleburtle.net/bob/hash/integer.html.
Take a look at the first suggested hash function for an integer
there.  GCC 4.4 with -O3 compiles this into 12 instructions.  And
then you have to figure out a way to combine multiple hashes for
subsequent integers.

Now look at, say, http://burtleburtle.net/bob/c/lookup3.c.  It
takes 12*3 instructions (according to the comments) to hash three
32-bit integers, which, per-integer, is the same rate, and you
don't have to invent a way to combine them.
-- 
"While the Melissa license is a bit unclear, Melissa aggressively
 encourages free distribution of its source code."
--Kevin Dalley <kevin@seti.org>

[toc] | [prev] | [next] | [standalone]

#1430

blp@cs.stanford.edu (Ben Pfaff) writes:
> Rainer Weikusat <rweikusat@mssgmbh.com> writes:
>> blp@cs.stanford.edu (Ben Pfaff) writes:

[...]

>>>>> 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. And performing extensive
>> byte-shuffling on machine words is not a good strategy to achieve
>> that.
>
> You suggested http://burtleburtle.net/bob/hash/integer.html.

That's a web page with some background explanations by an 'authority' you
were (indirectly) refering to and some examples of 'integer hash
functions' supposed to produce hash values with qualities Bob Jenkins
considered to be desirable. I wouldn't want to use them to hash IP
addresses, much as I also wouldn't want to use one of the 'monster
hashes' for string lookup.

> Now look at, say, http://burtleburtle.net/bob/c/lookup3.c.  It
> takes 12*3 instructions (according to the comments) to hash three
> 32-bit integers, which, per-integer, is the same rate, and you
> don't have to invent a way to combine them.

According to the table in

	http://burtleburtle.net/bob/hash/doobs.html

hashing 3 32-bit integers _byte by byte_ with lookup three is assumed
to take 80 instructions.

[toc] | [prev] | [next] | [standalone]

#1431

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.

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;"

> And performing extensive
> byte-shuffling on machine words is not a good strategy to achieve
> that.
True, but what else are you going to do?

The original posters problem, as I understand it, is that he has several 
IP addresses that need to be hashed together.  I would assume that means 
he has a table that is a map from a collection of IP addresses to some 
object.

First, an IPV4 address is basically 32 bits.  The entropy is low on the 
high-order bits and higher on the low order, which is fine for typical 
hash use-cases.

So, he has basically an integer bag (The OP hasn't specified whether the 
order of IPs matter, nor whether they may have duplicates)

If order doesn't matter, then the easiest correct approach is simply to 
sum up the integer value of each IP (not each octant, but the whole IP).

If order does matter, then you might want Σ(IP[i] * smallPrime^i). 
(where ^ is the exponent operator, not xor).  This can be implemented 
as: int hash=0; foreach(IP in theList) hash = hash * smallPrime + IP;

Duplicates will be handled correctly for both cases, but the hashes will 
only be equal if the same duplicates exist.

Either way, the actual speed of the hash function only matters if it 
because a bottleneck to the performance of the program.  The requires 
real-world measurement and profiling, and not a bunch of supposition 
from wiseguys on a newsgroup :-).

[toc] | [prev] | [next] | [standalone]

#1432

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?

Really. If calculating the hash value is more expensive than the
comparisons it is supposed to avoid, it obviously buys you nothing.

[toc] | [prev] | [next] | [standalone]

#1433

On 4/5/12 10:12 AM, Rainer Weikusat wrote:
> 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?
>
> Really. If calculating the hash value is more expensive than the
> comparisons it is supposed to avoid, it obviously buys you nothing.
A single hash is supposed to save you multiple comparisons, not a single 
comparison, so it can be many times more expensive than a single 
comparison and still improve performance.  A hash that is 10 times 
slower than a comparison, but allows you to find a bucket with only 3 
out of 3000 entries saves you an average cost of 1487 comparisons.

[toc] | [prev] | [next] | [standalone]

#1434

Daniel Pitts <newsgroup.nospam@virtualinfinity.net> writes:

> On 4/5/12 10:12 AM, Rainer Weikusat wrote:
>> 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?
>>
>> Really. If calculating the hash value is more expensive than the
>> comparisons it is supposed to avoid, it obviously buys you nothing.
> A single hash is supposed to save you multiple comparisons, not a
> single comparison,

An the letter 's' following a word, as in comparisonS, is supposed to
indicate a plural.

[toc] | [prev] | [next] | [standalone]

#1435

On 4/5/12 10:34 AM, Rainer Weikusat wrote:
> Daniel Pitts<newsgroup.nospam@virtualinfinity.net>  writes:
>
>> On 4/5/12 10:12 AM, Rainer Weikusat wrote:
>>> 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?
>>>
>>> Really. If calculating the hash value is more expensive than the
>>> comparisons it is supposed to avoid, it obviously buys you nothing.
>> A single hash is supposed to save you multiple comparisons, not a
>> single comparison,
>
> An the letter 's' following a word, as in comparisonS, is supposed to
> indicate a plural.
Yes, I single hash operation is used so that you can avoid multiple 
(meaning plural) comparisons. I said exactly what I meant, and meant 
exactly what I said. My point still stands.  A hash can be slower than a 
comparison, and still save you a significant amount of time.

[toc] | [prev] | [next] | [standalone]

#1436

Daniel Pitts <newsgroup.nospam@virtualinfinity.net> writes:
> On 4/5/12 10:34 AM, Rainer Weikusat wrote:
>> Daniel Pitts<newsgroup.nospam@virtualinfinity.net>  writes:
>>> On 4/5/12 10:12 AM, Rainer Weikusat wrote:
>>>> 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?
>>>>
>>>> Really. If calculating the hash value is more expensive than the
>>>> comparisons it is supposed to avoid, it obviously buys you nothing.
>>> A single hash is supposed to save you multiple comparisons, not a
>>> single comparison,
>>
>> An the letter 's' following a word, as in comparisonS, is supposed to
>> indicate a plural.
> Yes, I single hash operation is used so that you can avoid multiple
> (meaning plural) comparisons. I said exactly what I meant, and meant
> exactly what I said. My point still stands.  A hash can be slower than
> a comparison, and still save you a significant amount of time.

And so did I, superbrain. Please pester someone else in future.

[toc] | [prev] | [next] | [standalone]

#1437

Rainer Weikusat <rweikusat@mssgmbh.com> writes:

[...]

>>>>> Really. If calculating the hash value is more expensive than the
>>>>> comparisons it is supposed to avoid, it obviously buys you nothing.
>>>> A single hash is supposed to save you multiple comparisons, not a
>>>> single comparison,
>>>
>>> An the letter 's' following a word, as in comparisonS, is supposed to
>>> indicate a plural.
>> Yes, I single hash operation is used so that you can avoid multiple
>> (meaning plural) comparisons. I said exactly what I meant, and meant
>> exactly what I said. My point still stands.  A hash can be slower than
>> a comparison, and still save you a significant amount of time.
>
> And so did I, superbrain. Please pester someone else in future.

And just in case there are more 'Blitzmerkers' of this kind around
here: I was referring to the complete set of comparisons that would
need to be done for a search without hashing all the time.

[toc] | [prev] | [next] | [standalone]

#1440

On 4/5/12 11:38 AM, Rainer Weikusat wrote:
> Rainer Weikusat<rweikusat@mssgmbh.com>  writes:
>
> [...]
>
>>>>>> Really. If calculating the hash value is more expensive than the
>>>>>> comparisons it is supposed to avoid, it obviously buys you nothing.
>>>>> A single hash is supposed to save you multiple comparisons, not a
>>>>> single comparison,
>>>>
>>>> An the letter 's' following a word, as in comparisonS, is supposed to
>>>> indicate a plural.
>>> Yes, I single hash operation is used so that you can avoid multiple
>>> (meaning plural) comparisons. I said exactly what I meant, and meant
>>> exactly what I said. My point still stands.  A hash can be slower than
>>> a comparison, and still save you a significant amount of time.
>>
>> And so did I, superbrain. Please pester someone else in future.
>
> And just in case there are more 'Blitzmerkers' of this kind around
> here: I was referring to the complete set of comparisons that would
> need to be done for a search without hashing all the time.
Pointing out a flaw in your post is not pestering you.  The fact that 
you haven't chosen to respond to the actual point I made shows you are 
in fact the one who pesters.

Hash's are slower than comparisons, as a matter of course.

Good day to you sir.

[toc] | [prev] | [next] | [standalone]

#1438

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

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.programming

csiph-web