2

I'm working on converting a website using php. Part of my process is verify that image paths don't point to non-existant images (i.e. there are no broken images). Since many pages share certain images, I set up a cache array to see if I've already checked for the existence of an image file for a given path.

Using raw path string as the array index didn't work, so I used md5(), and that does the trick. However, the conversion script is taking a long time, and it seems clear that that's because of the md5 calculation ( I've been running the conversion frequently over the past few days, and I noticed right away that as soon as my caching started working, the script took much longer to run.)

So I'm wondering if there is a faster hash algorithm that I can use in my cache, and of course I need one that won't produce collisions. Since this is a one-off script, I don't need a super-secure unbreakable algorithm, just one that gets the job done a little faster.

This comment apparently is a list of all the hashing functions that php has available to it.

Edit I didn't draw a lot of attention to this in my comment, but when I use the plain string of the path as the index for the cache array, it didn't work. As soon as I changed it to md5 hash, it worked. If I had more time I would troubleshoot this, but this is a one-off project that I can't spend more time than I absolutely must one.

Post Edit Okay, apparently I'm doing something way wrong with my caching; I must have changed something when I changed the indexes to hashes that caused the cache to start working, irrespective of the hashing. People are saying my hash should be okay with file path strings, and that md5s don't take that long anyway. So, I don't know what I'm doing wrong and I don't have time to figure it out in this project. I would delete this question but it already has answers.

user151841
  • 17,377
  • 29
  • 109
  • 171
  • 3
    There's no such thing as a collisionless hash. Hashing essentially involves taking an infinite number of inputs, and mapping them to a finite number of outputs. Even on a finite data set (size > 1, of course), there's no way to guarantee that *any* hash algorithm will avoid collisions without actually hashing all of them and checking for collisions. – Michael Madsen Sep 07 '11 at 21:20
  • 2
    If MD5 is too slow, you're doing something terribly wrong. Any machine built in the last 5 years should be able to hash millions of paths per second. It's much more likely that something about the way you're managing your array is slow; the problem simply cannot be MD5. – user229044 Sep 07 '11 at 21:23
  • @Michael Madsen It just has to be collisionless *enough*. – user151841 Sep 07 '11 at 22:16
  • @user151841: Now you just have to define when a hashing algorithm is "collisionless enough". :) If that means something like "at most X collisions in my data set" - well, it's highly likely that any hash algorithm still worth using (and probably a number of algorithms *not* worth using!) will meet that demand, but without testing, you can't know that. – Michael Madsen Sep 07 '11 at 22:51
  • Have you considered a bloom filter (it seems quite suited to your expressed task)? – Slartibartfast Sep 08 '11 at 04:43

4 Answers4

5

If these hashes are used only inside PHP and are built dynamically as this script works, why not simply use an array?

if (isset($path_cache['/some/weird/ugly/long/path'])) { 
   ...
}

would work just as well without the MD5 calculation overhead.

Marc B
  • 356,200
  • 43
  • 426
  • 500
  • I would double check if I had more time, but for whatever reason, using the raw path string as the array index didn't work (which I stated in my question). It worked when I used hashed strings as indexes. – user151841 Sep 07 '11 at 21:32
  • how did it not work? PHP couldn't care less if the string being used as a key is a path or is an md5 hash - they're both just strings. – Marc B Sep 07 '11 at 21:34
  • Here's how it didn't work: I had it set to throw a message when it pulled a value from the cache array. For the past week I haven't seen the message, even though the cache was full of paths. I changed the index to hashes, and all of a sudden, almost everything is coming out of cache. Unfortunately I don't have time to figure out what I'm doing wrong :P – user151841 Sep 07 '11 at 21:37
1
foreach (hash_algos() as $value) {
    print hash($value, 'some random') . ' - ' . $value . '<br />';
}

It will print the string hashed in all hashing algorithms that php supports.

user2226755
  • 12,494
  • 5
  • 50
  • 73
azuneca
  • 1,053
  • 13
  • 15
1

I suggest you use plain paths for this - no need to hash it. However, crc32 seems to be a fast one. Keep in mind - you're sacrificing collision rate to speed.

Community
  • 1
  • 1
kgilden
  • 10,336
  • 3
  • 50
  • 48
0

The fastest hash function appears to be

hash('adler32', $string);

However just md5() works nearly as fast as the function above.

There is the benchamrk of all hashes available in PHP.
http://l.garygolden.me/fastest-hash-php

Max Tsepkov
  • 466
  • 6
  • 15