Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!news.musoftware.de!wum.musoftware.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: Rainer Weikusat Newsgroups: comp.programming,comp.unix.programmer Subject: Re: hash function over IP address Date: Thu, 05 Apr 2012 16:29:57 +0100 Lines: 45 Message-ID: <871uo25h8q.fsf@sapphire.mobileactivedefense.com> References: <87hawzyy3z.fsf@blp.benpfaff.org> <87398jw4ep.fsf@sapphire.mobileactivedefense.com> <87d37nyvjw.fsf@blp.benpfaff.org> <87k41uo2ph.fsf@sapphire.mobileactivedefense.com> <877gxukzo5.fsf@blp.benpfaff.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: individual.net iMXWR7mEwC3afwX1OX0XRg6Utrhpw1ZHsVJmXsEGFOBUzP7K0= Cancel-Lock: sha1:SXjNGvSJvLkwllwnM70zVnwh1II= sha1:R2hh49hUO9I4LjeSkAgvKLx6qGg= User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.2 (gnu/linux) Xref: csiph.com comp.programming:1430 comp.unix.programmer:2371 blp@cs.stanford.edu (Ben Pfaff) writes: > Rainer Weikusat 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.