哈希算法
Last updated
Last updated
哈希算法并不是一个特定的算法而是一类算法的统称。哈希算法也叫散列算法，一般来说满足这样的关系：f(data)=key，输入任意长度的data数据，经过哈希算法处理后输出一个定长的数据key。同时这个过程是不可逆的，无法由key逆推出data。
在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。 哈希函数就是一种映射，是从关键字到存储地址的映射。
1、加法Hash； 所谓的加法Hash就是把输入元素一个一个的加起来构成最后的结果，prime是素数。
function addictiveHash(key = '', prime){
let hash = 0;
for(let i = 0; i < key.length; ++i){
hash += key.charCodeAt(i);
}
return hash % prime;
}
console.log(addictiveHash('test', 31)); // 14
console.log(addictiveHash('abc', 31)); // 15
console.log(addictiveHash('abb', 31)); // 142、位运算Hash； 这类型Hash函数通过利用各种位运算（常见的是移位和异或）来充分的混合输入元素。
function rotatingHash(key = '', prime) {
let hash = 0;
for (let i = 0; i < key.length; ++i) {
hash = (hash << 4) ^ (hash >> 28) ^ key.charCodeAt(i);
}
return (hash % prime);
}
console.log(rotatingHash('test', 31)); // 13
console.log(rotatingHash('abc', 31)); // 23
console.log(rotatingHash('abb', 31)); // 223、乘法Hash； 这样的类型的哈希函数利用了乘法的不相关性.乘法哈希里最有名的就是adler32，reactJS的checksum校验就是使用的adler32的改良版。
function adler32(str) {
var a = 1, b = 0, L = str.length, M = 0, c = 0, d = 0;
for (var i = 0; i < L;) {
M = Math.min(L - i, 3850);
while (M > 0) {
c = str.charCodeAt(i++);
if (c < 0x80) { a += c; }
else if (c < 0x800) {
a += 192 | ((c >> 6) & 31); b += a; --M;
a += 128 | (c & 63);
} else if (c >= 0xD800 && c < 0xE000) {
c = (c & 1023) + 64; d = str.charCodeAt(i++) & 1023;
a += 240 | ((c >> 8) & 7); b += a; --M;
a += 128 | ((c >> 2) & 63); b += a; --M;
a += 128 | ((d >> 6) & 15) | ((c & 3) << 4); b += a; --M;
a += 128 | (d & 63);
} else {
a += 224 | ((c >> 12) & 15); b += a; --M;
a += 128 | ((c >> 6) & 63); b += a; --M;
a += 128 | (c & 63);
}
b += a; --M;
}
a = (15 * (a >>> 16) + (a & 65535));
b = (15 * (b >>> 16) + (b & 65535));
}
return ((b % 65521) << 16) | (a % 65521);
}
console.log(adler32('test', 31)); // 73204161
console.log(adler32('abc', 31)); // 38600999
console.log(adler32('abb', 31)); // 385354624、除法Hash； 和乘法一样用了不相关性，但性能不好。
5、查表Hash； 查表Hash最有名的样例莫过于CRC系列算法。尽管CRC系列算法本身并非查表，可是，查表是它的一种最快的实现方式。以下是CRC32的实现：
function signed_crc_table() {
var c = 0, table = new Array(256);
for(var n =0; n != 256; ++n){
c = n;
c = ((c&1) ? (-306674912 ^ (c >>> 1)) : (c >>> 1));
c = ((c&1) ? (-306674912 ^ (c >>> 1)) : (c >>> 1));
c = ((c&1) ? (-306674912 ^ (c >>> 1)) : (c >>> 1));
c = ((c&1) ? (-306674912 ^ (c >>> 1)) : (c >>> 1));
c = ((c&1) ? (-306674912 ^ (c >>> 1)) : (c >>> 1));
c = ((c&1) ? (-306674912 ^ (c >>> 1)) : (c >>> 1));
c = ((c&1) ? (-306674912 ^ (c >>> 1)) : (c >>> 1));
c = ((c&1) ? (-306674912 ^ (c >>> 1)) : (c >>> 1));
table[n] = c;
}
return typeof Int32Array !== 'undefined' ? new Int32Array(table) : table;
}
var T = signed_crc_table();
function crc32(str, seed) {
var C = seed ^ -1;
for(var i = 0, L=str.length, c, d; i < L;) {
c = str.charCodeAt(i++);
if(c < 0x80) {
C = (C>>>8) ^ T[(C ^ c)&0xFF];
} else if(c < 0x800) {
C = (C>>>8) ^ T[(C ^ (192|((c>>6)&31)))&0xFF];
C = (C>>>8) ^ T[(C ^ (128|(c&63)))&0xFF];
} else if(c >= 0xD800 && c < 0xE000) {
c = (c&1023)+64; d = str.charCodeAt(i++)&1023;
C = (C>>>8) ^ T[(C ^ (240|((c>>8)&7)))&0xFF];
C = (C>>>8) ^ T[(C ^ (128|((c>>2)&63)))&0xFF];
C = (C>>>8) ^ T[(C ^ (128|((d>>6)&15)|((c&3)<<4)))&0xFF];
C = (C>>>8) ^ T[(C ^ (128|(d&63)))&0xFF];
} else {
C = (C>>>8) ^ T[(C ^ (224|((c>>12)&15)))&0xFF];
C = (C>>>8) ^ T[(C ^ (128|((c>>6)&63)))&0xFF];
C = (C>>>8) ^ T[(C ^ (128|(c&63)))&0xFF];
}
}
return C ^ -1;
}
console.log(crc32('test', 31)); // -804963899
console.log(crc32('abc', 31)); // 576628111
console.log(crc32('abb', 31)); // 14319342336、 混合Hash； 混合Hash算法利用了以上各种方式。各种常见的Hash算法，比方MD5、Tiger都属于这个范围。它们一般非常少在面向查找的Hash函数里面使用。
文件校验
数字签名
鉴权协议