Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!usenet.stanford.edu!not-for-mail From: blp@cs.stanford.edu (Ben Pfaff) Newsgroups: comp.programming,comp.unix.programmer Subject: Re: hash function over IP address Date: Thu, 05 Apr 2012 07:42:50 -0700 Lines: 45 Message-ID: <877gxukzo5.fsf@blp.benpfaff.org> References: <87hawzyy3z.fsf@blp.benpfaff.org> <87398jw4ep.fsf@sapphire.mobileactivedefense.com> <87d37nyvjw.fsf@blp.benpfaff.org> <87k41uo2ph.fsf@sapphire.mobileactivedefense.com> Reply-To: blp@cs.stanford.edu Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: usenet.stanford.edu 1333636905 467 127.0.0.1 (5 Apr 2012 14:41:45 GMT) X-Complaints-To: action@cs.stanford.edu User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.2 (gnu/linux) Cancel-Lock: sha1:3g6eEA0tYKGV7KOo63/MdEF+N78= Xref: csiph.com comp.programming:1428 comp.unix.programmer:2369 Rainer Weikusat writes: > blp@cs.stanford.edu (Ben Pfaff) writes: >> Rainer Weikusat writes: >> >>> Ben Pfaff writes: >>>> "Mark" 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