hash算法,又称散列算法,杂凑算法
它可以将一个长度不固定的数据,通过算法,获取其特征值生成一个固定的,较短的数据,压缩其文件标识.
实现用一个较短的数据进行标识一个大数据标识.比如用32位字符串的md5,标识整个文件
我们可以自定义一个算法,将中文字符串,只获取拼音首字母的特征,转成hash:
"仙士可"=>'xsk'
"阿伟死了"=>'awsl'
如果使用中文表示,需要的字符串长度是字母缩写的2-4倍.
重复性
通过上面的例子,我们可能会发现一些问题,例如: "啊我死了" ,"阿王死了",都会对应 'awsl'
这时候,就发生了 哈希冲突, 不同的数据,可能会因为提取特征值,而产生相同的hash结果
逆推性
可以发现,我们可以通过 "sl","sb","nt"等字母,很容易隐隐约约的知道原来的中文意思
这就造成了如果我们中文的一句话如果都有这些意思,那生成的hash重复性将会非常大.
因此,一个优秀的hash算法,应该具备以下条件:
1:正向快速计算,能通过输入的数据,在有限的时间,利用有限的资源就能计算出hash值(比如说你要用数据 做1亿次加减乘除法计算,虽然很难重复了,但是每次都计算1亿次,非常不现实)
2:逆向困难,hash字符串不能直接被逆向推算出.
3:输入敏感,原始信息就算多了一个空格,也应该跟原来的字符串非常不一致
4:冲突避免,hash的数据应该尽可能避免冲突,均匀分布,否则将失去hash本身的特性
目前最经典的hash算法有md5,time33,sha
在实际使用中,md5是字符串hash,并且性能较差,php在hashtable中hash计算使用的是time33算法.
最后附带上使用php实现的各种流行hash算法
<?php class Hash { /** * 加法hash * additiveHash * @param string $key * @param int $mask * @return int * @author tioncico * Time: 11:38 上午 */ public static function additiveHash(string $key, $mask = 0x8765fed1) { for ($hash = strlen($key), $i = 0; $i < strlen($key); $i++) { $charIndex = ord($key\[$i\]); $hash += $charIndex; } return ($hash % $mask); } /** * 旋转hash * rotatingHash * @param string $key * @param int $mask * @return int * @author tioncico * Time: 11:38 上午 */ public static function rotatingHash(string $key, $mask = 0x8765fed1) { for ($hash = strlen($key), $i = 0; $i < strlen($key); $i++) { $charIndex = ord($key\[$i\]); $hash = ($hash << 4) ^ ($hash >> 28) ^ $charIndex; } // return ($hash % $prime); return ($hash ^ ($hash >> 10) ^ ($hash >> 20)) & $mask; } /** * 一次一个hash * oneByOneHash * @param $key * @param int $mask * @return int * @author tioncico * Time: 11:38 上午 */ public static function oneByOneHash(string $key, $mask = 0x8765fed1) { for ($hash = strlen($key), $i = 0; $i < strlen($key); $i++) { $charIndex = ord($key\[$i\]); $hash += $charIndex; $hash += $hash << 10; $hash ^= $hash >> 6; } $hash += ($hash << 3); $hash ^= ($hash >> 11); $hash += ($hash << 15); return $hash & $mask; } public static function time33(string $key) { // hash($i) = hash($i-1) * 33 + str\[$i\] $hash = 5381; for ($i = 0; $i < strlen($key); $i++) { // (hash << 5) + hash 相当于 hash * 33 //$hash = sprintf("%u", $hash * 33) + ord($s{$i}); //$hash = ($hash * 33 + ord($s{$i})) & 0x7FFFFFFF; $charIndex = ord($key\[$i\]); $hash = ($hash << 5) + $hash + $charIndex; } return $hash & 0x7FFFFFFF; } public static function fnvHash(string $key, $mask = 0x8765fed1, $mShift = 0) { $hash = 2166136261; $p = 16777619; for ($i = 0; $i < strlen($key); $i++) { $charIndex = ord($key\[$i\]); $hash = ($hash * $p) ^ $charIndex; } if ($mShift == 0) { return $hash; } return ($hash ^ ($hash >> $mShift)) & $mask; } public static function fnvHash1(string $key) { $p = 16777619; $hash = 2166136261; for ($i = 0; $i < strlen($key); $i++) { $charIndex = ord($key\[$i\]); $hash = ($hash * $p) ^ $charIndex; } $hash += $hash << 13; $hash ^= $hash >> 7; $hash += $hash << 3; $hash ^= $hash >> 17; $hash += $hash << 5; return $hash; } public static function intHash(int $key) { $key += ~($key << 15); $key ^= ~(self::uRight($key, 10)); $key += ~($key << 3); $key ^= ~(self::uRight($key, 6)); $key += ~($key << 11); $key ^= ~(self::uRight($key, 16)); return $key; } protected static function uRight($a, $n) { $c = 2147483647 >> ($n - 1); return $c & ($a >> $n); } public static function rsHash(string $key) { $b = 3787551; $a = 636789; $hash = 0; for ($i = 0; $i < strlen($key); $i++) { $charIndex = ord($key\[$i\]); $hash = ($hash * $a) + $charIndex; $a = $a * $b; } return ($hash & 0x7FFFFFFF); } public static function jsHash(string $key) { $hash = 1315423911; for ($i = 0; $i < strlen($key); $i++) { $charIndex = ord($key\[$i\]); $hash = (($hash << 5) + $charIndex + ($hash >> 2)); } return ($hash & 0x7FFFFFFF); } public static function pjwHash(string $key) { $bitsInUnsignedInt = 32; $threeQuarters = ($bitsInUnsignedInt * 3) / 4; $oneEighth = $bitsInUnsignedInt / 8; $highBits = 0xFFFFFFFF << ($bitsInUnsignedInt - $oneEighth); $hash = 0; $test = 0; for ($i = 0; $i < strlen($key); $i++) { $charIndex = ord($key\[$i\]); $hash = ($hash << $oneEighth) + $charIndex; if (($test = $hash & $highBits) != 0) { $hash = (($hash ^ ($test >> $threeQuarters)) & (~$highBits)); } } return ($hash & 0x7FFFFFFF); } public static function elfHash(string $key) { $hash = 0; $x = 0; for ($i = 0; $i < strlen($key); $i++) { $charIndex = ord($key\[$i\]); $hash = ($hash << 4) + $charIndex; if (($x = (int)$hash & 0xF0000000 != 0)) { $hash ^= ($x >> 24); $hash &= ~$x; } } return ($hash & 0x7FFFFFFF); } public static function bkdrHash(string $key) { $hash = 0; $seed = 131; //31 131 1313 13131 131313 for ($i = 0; $i < strlen($key); $i++) { $charIndex = ord($key\[$i\]); $hash = ($hash * $seed) + $charIndex; } return ($hash & 0x7FFFFFFF); } public static function sdbmHash(string $key) { $hash = 0; for ($i = 0; $i < strlen($key); $i++) { $charIndex = ord($key\[$i\]); $hash = $charIndex + ($hash << 6) + ($hash >> 15) - $hash; } return ($hash & 0x7FFFFFFF); } public static function dekHash(string $key) { $hash = strlen($key); for ($i = 0; $i < strlen($key); $i++) { $charIndex = ord($key\[$i\]); $hash = ($hash << 5) ^ ($hash >> 27) ^ $charIndex; } return ($hash & 0x7FFFFFFF); } public static function apHash(string $key) { $hash = 0; for ($i = 0; $i < strlen($key); $i++) { $charIndex = ord($key\[$i\]); $hash ^= (($i & 1) == 0) ? (($hash << 7) ^ $charIndex ^ ($hash >> 3)) : (~(($hash << 11) ^ $charIndex ^ ($hash >> 5))); } return ($hash & 0x7FFFFFFF); } public static function javaHash(string $key) { $hash = 0; for ($i = 0; $i < strlen($key); $i++) { $charIndex = ord($key\[$i\]); $hash = 31 * $hash + $charIndex; } return ($hash & 0x7FFFFFFF); } }
