孤独求学人

一些经典字符串哈希函数算法的 PHP 实现(转)

2011-7-16 杜世伟 Php

<?php
/*
哈希算法 将任意长度的二进制值映射为 固定长度的较小二进制值，这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示 形式。如果散列一段明文而且哪怕只更 改该段落的一个字母，随后的哈希都将产生不同的值。要找到散列为同一 个值的两个不同的输入，在计算上是不可能的，所以数据的哈希值可以 检验数据的完整性。
哈希表是根据设定的哈希函数H(key)和处理冲突方法将一组关键 字映象到一个有限的地址区间上，并以关键字在地址区间中的象作为记录在表中的存储位置，这种表称为哈希表或散列，所得存储位置称为哈希地址或散列 地址。作为线性数据结构与表格和队列等相比，哈希表无疑是查找速度比较快的一种。
哈希
通过将单向数学函数（有时称为“哈希算法”）应用到任意数量的数据所得到的固定大小的结果。如 果输入数据中有变化，则哈希也会发生变化。哈希可用于许多操作，包括身份验证和数字签名。也称为“消息摘要”。
*/

//算法的一些说明：
//
//1. 函数后面注释中是我本地测试的执行1000次的速度（单位：s），可以看出来MD5Hash是最快的，而且要比其他函数快很多很多... 但是从这 个函数的算法也可以看出来，它仅仅是依赖于md5后字符串的前7个字符，也就是说如果前7个字符相同的话那么获得的hash值是完全一样的，所以实际来说 它的分布情况是不太令人信任的....如果按照32个字符来计算的话速度那就远远的慢于其他算法了...
//2. 除了MD5Hash，其他算法都会受到字符串长度的影响，越长越慢，我测试用的是10个字符的英文。
//3. 每个函数最后的 return $hash % 701819; 中 701819 表示是哈希的最大容积，也就是说这些哈希函数最后得到的数字范围是0~701819，这个数字是可以改的一般认为使用一个大的质数结果的分布会是比较均匀 的，在 701819 附近的几个建议的值是：175447, 350899, 1403641, 2807303, 5614657。


function DJBHash($str) // 0.22
{
$hash = 0;
$n = strlen($str);
for ($i = 0; $i <$n; $i++) {
$hash += ($hash <<5 ) + ord($str[$i]);
}
return $hash % 701819;
}

function ELFHash($str) // 0.35
{
$hash = $x = 0;
$n = strlen($str);

for ($i = 0; $i <$n; $i++) {
$hash = ($hash <<4) + ord($str[$i]);
if (($x = $hash & 0xf0000000) != 0) {
$hash ^= ($x>> 24);
$hash &= ~$x;
}
}
return $hash % 701819;
}

function JSHash($str) // 0.23
{
$hash = 0;
$n = strlen($str);

for ($i = 0; $i <$n; $i++) {
$hash ^= (($hash <<5) + ord($str[$i]) + ($hash>> 2));
}
return $hash % 701819;
}

function SDBMHash($str) // 0.23
{
$hash = 0 ;
$n = strlen($str);

for ($i = 0; $i <$n; $i++) {
$hash = ord($str[$i]) + ($hash <<6 ) + ($hash <<16 ) - $hash;
}
return $hash % 701819;
}

function APHash($str) // 0.30
{
$hash = 0 ;
$n = strlen($str);

for ($i = 0; $i <$n; $i++) {
if (($i & 1 ) == 0 ) {
$hash ^= (($hash <<7 ) ^ ord($str[$i]) ^ ($hash>> 3 ));
} else {
$hash ^= ( ~ (($hash <<11 ) ^ ord($str[$i]) ^ ($hash>> 5)));
}
}
return $hash % 701819;
}

function DEKHash($str) // 0.23
{
$n = strlen($str);
$hash = $n;

for ($i = 0; $i <$n; $i++) {
$hash = (($hash <<5) ^ ($hash>> 27)) ^ ord($str[$i]);
}
return $hash % 701819;
}

function FNVHash($str) // 0.31
{
$hash = 0;
$n = strlen($str);

for ($i = 0; $i <$n; $i++) {
$hash *= 0x811C9DC5;
$hash ^= ord($str[$i]);
}
return $hash % 701819;
}

function PJWHash($str) // 0.33
{
$hash = $test = 0;
$n = strlen($str);
for ($i = 0; $i <$n; $i++) {
$hash = ($hash <<4) + ord($str[$i]);

if(($test = $hash & -268435456)  != 0) {
$hash = (( $hash ^ ($test>> 24)) & (~-268435456));
}
}

return $hash % 701819;
}

function PHPHash($str) // 0.34
{
$hash = 0;
$n = strlen($str);

for ($i = 0; $i <$n; $i++) {
$hash = ($hash <<4) + ord($str[$i]);
if (($g = ($hash & 0xF0000000))) {
$hash = $hash ^ ($g>> 24);
$hash = $hash ^ $g;
}
}
return $hash % 701819;
}

function OpenSSLHash($str) // 0.22
{
$hash = 0;
$n = strlen($str);
for ($i = 0; $i <$n; $i++) {
$hash ^= (ord($str[$i]) <<($i & 0x0f));
}
return $hash % 701819;
}

function MD5Hash($str) // 0.050
{
$hash = md5($str);
$hash = $hash[0] | ($hash[1] <<8 ) | ($hash[2] <<16) | ($hash[3] <<24) | ($hash[4] <<32) | ($hash[5] <<40) | ($hash[6] <<48) | ($hash[7] <<56);
return $hash % 701819;
}
?>

 

来自:http://hi.baidu.com/zys1234/blog/item/9b249c270199340f918f9dea.html

标签: php hash

评论：