> For the complete documentation index, see [llms.txt](https://jun-wang.gitbook.io/learnjava/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jun-wang.gitbook.io/learnjava/ji-shu-xue-xi/suan-fa/hash-suan-fa.md).

# Hash算法

## 一、Hash表

Hash表也叫散列表，它是基于告诉存取的角度设计的，也是一种典型的“空间换时间”的做法。该数据结构是一个线性表，但是其中的元素不是紧密排列的，而是可能存在空隙。访问数据是根据key-value来访问，它通过关键码key映射到表中的一个位置来访问记录，以加快查找的速度。

几个关键词：

* hash函数：也叫散列函数，用于通过key计算位置的函数。
* 负载因子：散列表的空间占有率，比如100个元素的空间存储了70个元素，70/100=0.7就是负载因子。
* 桶：每个存储单位成为桶。设一个散列表有M个桶，那么散列函数的值域应该是\[0,M-1]。
* 散列冲突：当两个不同的key通过散列函数计算的结果相同时，我们称这个叫做冲突。

## 二、Hash冲突

产生冲突主要取决于：

* 散列函数，一个好的散列函数的值应该尽可能平均分布。
* 处理冲突的方法。
* 负载因子的大小，太大不一定就好，并且浪费空间严重，负载因子和散列函数式联动的。

解决冲突的办法：

* 开放定址法：从发生冲突的那一个单元起，按照一定的次序从哈希表找到一个空闲的单元存入，常用的开放定址法有：线性探查法，平方探查法，双散列函数探查法。
* 拉链法：将hash相同的值构成一个单链表，jdk7的hashmap就是这么解决hash冲突的。
* 再哈希法：同时构造多个不同的哈希函数，当第一个哈希函数产生冲突时，用第二个哈市函数计算，知道不再产生冲突，这样不易产生聚集，但是增加了计算时间。
* 建立公共溢出区：将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。

## 三、常用Hash算法

Hash函数能够简单的划分为如下几类：

* 加法Hash
* 位运算Hash
* 乘法Hash
* 除法Hash
* 查表Hash
* 混合Hash

### 3.1 加法Hash

```java
    /*
     * 加法hash
     */
    static int additiveHash(String key, int prime) {
        int hash = 0;
        for(int i = 0; i < key.length(); i++) {
            hash += key.charAt(i);
        }
        hash = hash < 0? -hash: hash;
        hash %= prime;
        return hash;
    }
```

### 3.2 位运算Hash

```java
    /*
     * 位运算hash
     */
    static int rotatingHash(String key, int prime) {
        int hash = key.length();
        for(int i = 0; i < key.length(); i++) {
            hash = hash ^ key.charAt(i);//如何位运算可以自己定，这只是一个例子
        }
        hash = hash < 0? -hash: hash;
        hash %= prime;
        return hash;
    }
```

### 3.3 乘法Hash

```java
    /*
     * 乘运算hash
     */
    static int bernstein(String key, int prime) {
        int hash = 0;
        for(int i = 0; i < key.length(); i++) {
            hash = 33 * hash + key.charAt(i);
        }
        hash = hash < 0? -hash: hash;
        hash %= prime;
        return hash;
    }
```

### 3.4 除法Hash

除法运算hash与乘法类似，但是除法运算太耗时，一般不使用

### 3.5查表Hash

```java
/*
     * 查表hash，查表hash最有名的就是CRC系列算法
     */
    static int crc32(String key, int prime) {
        int crctab[] = { 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
                0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988, 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
                0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
                0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
                0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172, 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
                0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
                0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
                0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
                0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
                0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
                0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
                0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
                0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
                0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0, 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
                0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
                0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
                0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
                0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
                0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
                0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc, 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
                0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
                0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
                0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
                0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
                0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
                0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
                0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
                0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
                0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
                0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
                0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
                0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94, 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d };

        int hash = key.length();
        for(int i = 0; i < key.length(); i++) {
            hash = (hash >> 8) ^ crctab[(hash & 0xff)] ^ key.charAt(i);
        }

        hash = hash < 0? -hash: hash;
        hash %= prime;
        return hash;
    }
```

### 3.6 混合Hash

混合hash，就是利用了以上对种方式，各种常见的hash算法比如md5等属于这个范畴

> 参考：
>
> 解决哈希冲突的常用方法分析：<https://www.jianshu.com/p/4d3cb99d7580>
>
> 常见Hash算法的原理：<http://blog.jobbole.com/106733/>


---

# 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:

```
GET https://jun-wang.gitbook.io/learnjava/ji-shu-xue-xi/suan-fa/hash-suan-fa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
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.