> For the complete documentation index, see [llms.txt](https://bing.gitbook.io/phper/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://bing.gitbook.io/phper/data/algorithm/ha-xi-suan-fa.md).

# 哈希算法

## 定义

1. 哈希算法并不是一个特定的算法而是一类算法的统称。哈希算法也叫散列算法，一般来说满足这样的关系：f(data)=key，输入任意长度的data数据，经过哈希算法处理后输出一个定长的数据key。同时这个过程是不可逆的，无法由key逆推出data。
2. 在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。 哈希函数就是一种映射，是从关键字到存储地址的映射。

## 哈希函数的分类

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)); // 14
```

2、位运算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)); // 22
```

3、乘法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)); // 38535462
```

4、除法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)); // 1431934233
```

6、 混合Hash； 混合Hash算法利用了以上各种方式。各种常见的Hash算法，比方MD5、Tiger都属于这个范围。它们一般非常少在面向查找的Hash函数里面使用。

## 加密哈希算法

#### 安全方面应用

1. 文件校验
2. 数字签名
3. 鉴权协议

#### 几种比较常用的加密哈希算法

## 查找哈希算法

## 参考资料

* [非加密哈希的性能比较](http://aras-p.info/blog/2016/08/09/More-Hash-Function-Tests/)
* [哈希函数介绍](http://www.alloyteam.com/2017/05/hash-functions-introduction/)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://bing.gitbook.io/phper/data/algorithm/ha-xi-suan-fa.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.