简介
下面是 FNV Hash (Fowler-Noll-Vo hash 函数) 算法的 PHP 实现.
Fowler/Noll/Vo 是由 Glenn Fowler, Landon Curt Noll, 和 Phong Vo 创造的非加密哈希函数. 当前版本为 FNV-1 和 FNV-1a. FNV 目前有 32, 64, 128, 256, 512, 和 1024 位几种方式. 纯粹的 FNV 实现是完全由所需位数的可用的 FNV 素数决定的.
关于 Fowler-Noll-Vo 函数的更多信息可参见:
详细介绍
下面是一个非常简单的实现.
FNV 是非常简单的算法并且产生的结果相当不错.
我将以该算法的32位哈希版本开始.
根据 Noll 网站, FNV-1 哈希算法的核心思想如下:
hash = offset_basis
for each octet_of_data to be hashed
hash = hash * FNV_prime
hash = hash xor octet_of_data
return hash
我发现了一个非常好的 Java 实现片断 (参见 http://www.getopt.org/),:
long fnv(byte[] buf, int offset, int len, long seed) {
for (int i = offset; i < offset + len; i++) {
seed += (seed << 1) + (seed << 4) + (seed << 7) + (seed << 8) + (seed << 24);
seed ^= buf[i];
}
return seed;
}下面是 PHP 的实现片断:
$buf = str_split($txt);
$hash = FNV_offset_basis_32;
foreach ($buf as $chr) {
$hash += ($hash << 1) + ($hash << 4) + ($hash << 7) + ($hash << 8) + ($hash << 24);
$hash = $hash^ord($chr);
}
$hash = $hash & 0x0ffffffff;
请到源码库里查询最新代码.
挑战
PHP 好像并不擅长处理数字. 我花了好几个小时找出我的实现方法为什么不起作用, 如, 产生不了正确的结果, 最后发现大数乘法不是PHP能做到的 (但如果用Erlang, 再大的数都不会成为问题).
解决这些问题的方法是使用 "位移" 和 "加" 操作取代大数乘法:
$hash += ($hash << 1) + ($hash << 4) + ($hash << 7) + ($hash << 8) + ($hash << 24);
这应该也提高了性能.
<?php
/**
* FNV_PRIME:
* 32 bit FNV_prime = 224 + 28 + 0x93 = 16777619
* 64 bit FNV_prime = 240 + 28 + 0xb3 = 1099511628211
* 128 bit FNV_prime = 288 + 28 + 0x3b = 309485009821345068724781371
* OFFSET_BASIS:
* 32 bit offset_basis = 2166136261
* 64 bit offset_basis = 14695981039346656037
* 128 bit offset_basis = 144066263297769815596495629667062367629
*/
define ( "FNV_prime_32", 16777619 );
define ( "FNV_prime_64", 1099511628211 );
define ( "FNV_prime_128", 309485009821345068724781371 );
define ( "FNV_offset_basis_32", 2166136261 );
define ( "FNV_offset_basis_64", 14695981039346656037 );
define ( "FNV_offset_basis_128", 144066263297769815596495629667062367629 );
/**
* FNV-1 算法核心思想:
*
* hash = offset_basis
* for each octet_of_data to be hashed
* hash = hash * FNV_prime
* hash = hash xor octet_of_data
* return hash
*/
function fnvhash_fnv1( $txt ) {
/**
* Java 实现示例:
*
* long fnv(byte[] buf, int offset, int len, long seed) {
* for (int i = offset; i < offset + len; i++) {
* seed += (seed << 1) + (seed << 4) + (seed << 7) + (seed << 8) + (seed << 24);
* seed ^= buf[i];
* }
* return seed;
* }
*/
$buf = str_split($txt);
$hash = FNV_offset_basis_32;
foreach ( $buf as $chr ) {
$hash += ($hash << 1) + ($hash << 4) + ($hash << 7) + ($hash << 8) + ($hash << 24);
$hash = $hash ^ ord($chr);
}
$hash = $hash & 0x0ffffffff;
return $hash;
}
echo "<code>";
$text = "Hello. This is my first test.";
echo "text: $text<br />";
$hash = fnvhash_fnv1($text);
echo "hash: " . sprintf("%X", $hash) . " (" . sprintf("%u", $hash) . ")<br />";
echo "</code>";
?>
PHP 
