05
Jan
12

SDBM hash implementation in PHP

The SDBM hashing function is a simple and fast function that provides surprizingly uniform distributions of the hash value even when applied to a series of relatively short strings (3-7 characters). This makes it an excellent algorithm for organizing multiple files in sub-directories, for example, but the possible applications are, of course, endless.

Implementing the SDBM hashing in PHP is not an easy task, however. The SDBM hash function relies on a 32-bit overflow, which doesn’t work well in PHP due to its built-in overflow handling and automatic type conversion, which is also implemented differently on different platforms.

After much trial and error, the following cute piece of code has been found to perform correctly in PHP 5.2/5.3 on 32-bit as well as 64-bit systems.

function sdbmHash($str)
{
	$hash = 0; $n=strlen($str);
	for ($i=0; $i<$n; $i++) {
		$h1 = $hash << 6;
		if ($h1<0) $h1+=0x100000000;
		$h2 = $hash << 16;
		if ($h2<0) $h2+=0x100000000;
		$h3=($hash>=0x80000000?0x100000000-$hash:-$hash);
		$hash = (int)((int)ord($str[$i]) + $h1 + $h2 + $h3);
		if($hash<0) $hash=$hash+0x100000000;
	}
	return $hash;
}
Advertisements

0 Responses to “SDBM hash implementation in PHP”



  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: