views:

113

answers:

4

I'm essentially preparing phrases to be put into the database, they may be malformed so I want to store a short hash of them instead (I will be simply comparing if they exist or not, so hash is ideal).

I assume MD5 is fairly slow on 100,000+ requests so I wanted to know what would be the best method to hash the phrases, maybe rolling out my own hash function or using hash('md4', '...' would be faster in the end?

I know MySQL has MD5(), so that would complement a bit of speed on the query end, but maybe there's further a faster hashing function in MySQL I don't know about that would work with PHP..

+1  A: 

CRC32 is faster, but less secure than MD5 and SHA1. There is not that much difference between MD5 and SHA1.

Sjoerd
+1  A: 

CRC32 is pretty fast and there's a function for it: http://www.php.net/manual/en/function.crc32.php

But you should be aware that CRC32 will have more collisions than MD5 or even SHA-1 hashes, simply because of the reduced length (32 bits compared to 128 bits respectively 160 bits). But if you just want to check whether a stored string is corrupted, you'll be fine with CRC32.

joschi
Wow, only required datatype is an unsigned integer, this will be SIGNIFICANLY faster than other hashing.
John
@John: or not. CRC32 turns out to be _slower_ than MD4, and not much faster than MD5, on ARM processors. Besides, CRC32 uses an unsigned 32-bit integer type, which is exactly all that MD5 needs...
Thomas Pornin
MD5 still spits out a 128-bit hash for me...
joschi
+2  A: 
fcn     time  generated hash
crc32:  0.03163  798740135
md5:    0.0731   0dbab6d0c841278d33be207f14eeab8b
sha1:   0.07331  417a9e5c9ac7c52e32727cfd25da99eca9339a80
xor:    0.65218  119
xor2:   0.29301  134217728
add:    0.57841  1105

And the code used to generate this is:

 $loops = 100000;
 $str = "ana are mere";

 echo "<pre>";

 $tss = microtime(true);
 for($i=0; $i<$loops; $i++){
  $x = crc32($str);
 }
 $tse = microtime(true);
 echo "\ncrc32: \t" . round($tse-$tss, 5) . " \t" . $x;

 $tss = microtime(true);
 for($i=0; $i<$loops; $i++){
  $x = md5($str);
 }
 $tse = microtime(true);
 echo "\nmd5: \t".round($tse-$tss, 5) . " \t" . $x;

 $tss = microtime(true);
 for($i=0; $i<$loops; $i++){
  $x = sha1($str);
 }
 $tse = microtime(true);
 echo "\nsha1: \t".round($tse-$tss, 5) . " \t" . $x;

 $tss = microtime(true);
 for($i=0; $i<$loops; $i++){
  $l = strlen($str);
  $x = 0x77;
  for($j=0;$j<$l;$j++){
   $x = $x xor ord($str[$j]);
  }
 }
 $tse = microtime(true);
 echo "\nxor: \t".round($tse-$tss, 5) . " \t" . $x;

 $tss = microtime(true);
 for($i=0; $i<$loops; $i++){
  $l = strlen($str);
  $x = 0x08;
  for($j=0;$j<$l;$j++){
   $x = ($x<<2) xor $str[$j];
  }
 }
 $tse = microtime(true);
 echo "\nxor2: \t".round($tse-$tss, 5) . " \t" . $x;

 $tss = microtime(true);
 for($i=0; $i<$loops; $i++){
  $l = strlen($str);
  $x = 0;
  for($j=0;$j<$l;$j++){
   $x = $x + ord($str[$j]);
  }
 }
 $tse = microtime(true);
 echo "\nadd: \t".round($tse-$tss, 5) . " \t" . $x;
Quamis
Ah, Thank you for this insight actually, just fortifies my use of CRC32 being fastest.
John
usual piece of crap. "let's run zillion iterations of nothing"
Col. Shrapnel
... how else you you do it then?
Quamis
A: 

Instead of assuming that MD5 is "fairly slow", try it. A simple C-based implementation of MD5 on a simple PC (mine, a 2.4 GHz Core2, using a single core) can hash 6 millions of small messages per second. A small message is here anything up to 55 bytes. For longer messages, MD5 hashing speed is linear with the message size, i.e. it crunches data at about 400 megabytes per second. You may note that this is four times the maximum speed of a good harddisk or a gigabit ethernet network card.

Since my PC has four cores, this means that hashing data as fast as my harddisk can provide or receive uses at most 6% of the available computing power. It takes a very special situation for hashing speed to become a bottleneck or even to induce a noticeable cost on a PC.

On much smaller architectures where hashing speed may become somewhat relevant, you may want to use MD4. MD4 is fine for non-cryptographic purposes (and for cryptographic purposes, you should not be using MD5 anyway). It has been reported that MD4 is even faster than CRC32 on ARM-based platforms.

Thomas Pornin