Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!news.mixmin.net!news.musoftware.de!wum.musoftware.de!fu-berlin.de!uni-berlin.de!not-for-mail From: "M. Strobel" Newsgroups: comp.lang.php Subject: Re: FYI performance of hash algorithms Date: Mon, 23 Apr 2012 22:44:56 +0200 Lines: 58 Message-ID: <9vlta8Fa80U1@mid.uni-berlin.de> References: <9vlpk9Fd7cU1@mid.uni-berlin.de> Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 7bit X-Trace: news.uni-berlin.de GcCZIUVNbP2OvHNL2Oq2BQUXaE09FEW0INtXNQOg5yRK6ZPf8= User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; de; rv:1.9.2.28) Gecko/20120306 Thunderbird/3.1.20 In-Reply-To: Xref: csiph.com comp.lang.php:5690 Am 23.04.2012 22:16, schrieb Jerry Stuckle: > On 4/23/2012 3:42 PM, M. Strobel wrote: >> I am just asking myself which of the many hash algorithms performs best, so I can use >> it to index my translation strings. >> >> So I wrote a test script. It iterates over an array of 3.917.116 strings calculating >> the hash of each. >> >> Here you have the results, with run time, and run time relative to hash length >> (smaller is better). >> Interesting that the tiger hashes seem to perform well. >> >> There were only collisions with adler32 (many), crc32 and crc32b. >> >> /Str. >> > > > > Interesting, but only applicable on your system with your libraries and your data. A > different system could have different versions of the libraries and completely > different performance figures. Agreed. But it gives you hints. > As for collisions - completely dependent on your data. While you can say some things > with certainty (i.e. hashing 2^16+1 values with CRC-16 is guaranteed to have at least > one collision), by picking different strings to be hashed your collisions will come > out differently. > > For instance, it's not really surprising that adler32 had a lot of collisions. It > was designed for CRC and works better with binary data; it was never meant to be a > general purpose hashing algorithm. Rather it was designed for speed. It's also very > short. > > The same is true but to a lesser extent with the CRC-32 and CRC-32b algorithms, so > again I'm not surprised about the collisions. Neither am I. I just did not cut the list, they are listed by hash_algos(). > But the real question here is - how much does it matter if hashing a string takes 2 > microseconds or 2.5 microseconds? Unless you're doing millions of them at one time, > no one is going to notice the difference. Personally, when looking at such things I > always elect the fewest collisions over the fastest time. Even for this simple test I had to bump up memory_limit to 3G. And a real collision test is difficult. The problem is indeed that hashes are often used without collision detection, I am running the app without as well. I made this test to have an indication about how much longer one of the longer hashes takes to compute, for example md5 / sha1. For me the winner is ripemd256: a very long hash, running relatively fast. /Str.