---

提示：以下是本篇文章正文内容，Java系列学习将会持续更新

一、什么是哈希表？

 哈希表实际上是通过数组衍生出来的，哈希表高效查找的奥秘就在于数组的随机访问特性。查找 = O(1)
 通过哈希函数使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。通过这种方式构造出来的结构称为哈希表(HashTable)(或者称散列表)

例如：
 数据集合{1，7，6，4，5，9}；
 哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小。

回到目录…

二、哈希函数

2-1 常见哈希函数

1. 直接定制法 – (常用)
   取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

2. 除留余数法 – (常用)
   设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key % p(p<=m)

3. 平方取中法 – (了解)
   假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址

4. 折叠法 – (了解)
   折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和， 并按散列表表长，取后几位作为散列地址。

5. 数学分析法 – (了解)
   设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某 些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据 散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址

回到目录…

2-2 JDK中的hashCode()

// Object类中有计算哈希值的方法
public native int hashCode();
1
2

任何数据类型都可以通过 hashCode() 方法计算出 int 类型的哈希值。我们也可以在自定义类中，重写 hashCode() 方法自己设计哈希算法。

问答：
 在两个对象作比较时，
 hashCode() 相等的对象 equals 一定相等吗？ false
 equals 相等的对象 hashCode() 一定相等吗？ true

2-3 MD5哈希函数

MD5，MD4，MD3，SHA1，SHA256，这些都是被广泛使用的密码散列函数。
MD5在线加密

MD5的特点：

1. 定长，无论输入的数据有多长，得到的MD5值是长度固定的 (16位 / 32位)。
2. 分散，如果输入的数据稍微有点变化，得到的md5值相差非常大。
3. 不可逆,根据任意值计算出的MD5值很容易，但是MD5值不可能还原为原数据 (用在加密领域)。

MD5的应用：

1. 作为Hash值
2. 作为加密
3. 对比文件内容：一般大文件都会有一个MD5值，大文件在传输过程中有可能由于网络问题有的片段丢失了，要想知道下载后的文件内容是正确的，我们就拿着下载后的文件计算MD5值和源文件的MD5值作比较。

回到目录…

三、避免哈希冲突

 如上述例子，当表中再插入一个值为11的元素，此时hash(11) = hash(1) = 0。不同的元素通过相同哈希函数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

 我们需要明确一点，我们哈希表底层数组的容量往往是小于要存储的元素数量的，这就导致一个问题，冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率。

 避免哈希冲突两种常见的策略是：哈希函数的设计 和 负载因子的调节

3-1 哈希函数的设计

哈希函数的设计原则：

1. 哈希函数计算出来的地址能均匀分布在整个地址空间中，避免出现大量的空间没有元素 或 大量元素挤在一个空间内。
2. 稳定性：相同的 / 同一个元素不管做几次哈希运算，哈希值都不能改变。
3. 哈希函数的运算尽可能的简单。

最常用的哈希算法就是 取模法。

3-2 负载因子的调节

散列表的载荷因子定义为: α = 填入表中的元素个数 / 散列表的长度

负载因子越大，发生哈希冲突的概率越大，数组的长度就会偏小，节省空间。
负载因子越小，发生哈希冲突的概率越小，数组的长度就会偏大，浪费空间。

负载因子和冲突率的关系

已知哈希表中已有的关键字个数是不可变的，那我们只能通过调整哈希表中数组的长度来降低负载因子。

• JDK中的HashMap的负载因子为0.75，默认哈希表的长度为16。当元素个数>=12 的时候就会发生扩容。
• 阿里内部，对于负载因子的建议取值为10，允许每个链表的平均长度为10以内可以接受，在一定程度上节省了空间。

回到目录…

四、解决哈希冲突

 解决哈希冲突两种常见的方法是：闭散列 和 开散列

4-1 闭散列

 闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以 把key存放到冲突位置中的“下一个空位置” 中去。

那如何寻找下一个空位置呢？

1. 线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。若数组结束还没有找到空位置，则绕回 0 的位置往后探测。

2. 二次探测： 再次设计一种哈希算法，以之前Hash(x)对元素的关键码 key 计算出的位置为参数，算出不重复的地址。

闭散列的缺点：
 存放不难，但是查找和删除比较难。

闭散列最大的问题：
 若整个哈希表冲突比较严重,此时查找元素过程就相当于遍历数组,查找效率退化为O(N)

4-2 开散列 (常用)

 开散列又叫链地址法(开链法)，当发生哈希冲突时，让冲突位置变成链表。每一个子链表称为一个桶，各链表的头节点存储在哈希表中。

 开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。

冲突严重时的解决办法：
 如果冲突特别严重，就意味着小集合的搜索性能也是不佳的。我们就需要继续优化：

1. 针对整个哈希表进行扩容，假设以前%7(数组长度为7) -》扩容一倍，现在 % 14(数组长度变为14)， 就可大大降低冲突的概率,减少链表的长度。

2. 把单个链表再转为 哈希表 或者 搜索树。(JDK8的HashMap就采用此方案，当某个链表的长度> 6且整个哈希表的元素个数> 64,把此链表转为红黑树。

回到目录…

五、手撕哈希表

/**
 * 基于开散列的哈希表实现
 */
public class MyHashMap {

    private class Node {
        int key;
        int value;
        Node next;

        Node(int key, int value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    // 当前哈希表中实际存储元素的个数
    private int size;
    // 默认哈希表的长度
    private static final int DEFAULT_CAPACITY = 16;
    // 默认负载因子
    private static final double LOAD_FACTOR = 0.75;
    // 实际存储 key-value 的数组
    private Node[] data;
    // 哈希运算：取模
    private int M;

    public MyHashMap() {
        this(DEFAULT_CAPACITY);
    }
    public MyHashMap(int initCap) {
        data = new Node[initCap];
        this.M = initCap;
    }

    // 添加操作
    public int put(int key, int value) {
        // 计算索引
        int index = hash(key);
        // 查找是否存在 key
        for(Node node = data[index]; node != null; node = node.next) {
            if(node.key == key) {
                // 说明 key 已存在，那就更新 value 的值
                int oldValue = node.value;
                node.value = value;
                return oldValue;
            }
        }
        // 不存在 key,那就新增
        Node newNode = new Node(key, value, data[index]);
        data[index] = newNode;
        size ++;
        // 判断是否需要扩容
        if(size >= LOAD_FACTOR * data.length) {
            // TODO 扩容
            resize();
        }
        return value;
    }

    // 哈希表扩容
    private void resize() {
        // 建立新的哈希表，长度为原来的二倍
        this.M = M * 2;
        Node[] newData = new Node[M];
        // 遍历原表中的所有 key, 重新插入新表的位置；之前不同的key对应同一个位置，但在新表中不一定位置相同
        for (int i = 0; i < data.length; i++) {
            for (Node j = data[i]; j != null;) {
                int newIndex = hash(j.key);
                // 暂存 j 的后继节点
                Node next = j.next;
                // 将 j 插入 newData 中的 newIndex 处
                j.next = newData[newIndex];
                newData[newIndex] = j;
                // 再搬移原来桶中的下一个节点
                j = next;
            }
        }
        // 结束后，更新引用
        this.data = newData;
    }

    // 删除操作
    public int remove(int key) {
        int index = hash(key);
        // 查找是否存在 key
        Node prev = data[index];
        // 先看看是不是头节点
        if(prev.key == key) {
            // 删除 prev
            int val = prev.value;
            data[index] = prev.next;
            prev.next = prev = null;
            size --;
            return val;
        }
        while(prev.next != null) {
            if(prev.next.key == key) {
                // 删除 prev 的后继节点
                Node node = prev.next;
                int val = node.value;
                prev.next = node.next;
                node.next = node = null;
                size --;
                return val;
            }
            prev = prev.next;
        }
        // 不存在 key
        throw new NoSuchElementException("没有该 key 值！");
    }

    // 查找操作
    public int get(int key) {
        int index = hash(key);
        for(Node x = data[index]; x != null; x = x.next) {
            if(x.key == key) {
                return x.value;
            }
        }
        throw new NoSuchElementException("没有该 key 值！");
    }
    public boolean containsKey(int key) {
        int index = hash(key);
        for(Node x = data[index]; x != null; x = x.next) {
            if(x.key == key) {
                return true;
            }
        }
        return false;
    }
    public boolean containsValue(int value) {
        // 因为无法通过 value 值计算出key值，所以只能遍历全表查询
        // 先遍历每个桶的位置
        for (int i = 0; i < data.length; i++) {
            // 再遍历每个桶中的 value 值
            for (Node j = data[i]; j != null; j = j.next) {
                if(j.value == value) {
                    return true;
                }
            }
        }
        return false;
    }

    // 哈希函数
    private int hash(int key) {
        return Math.abs(key) % M;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151

回到目录…

---

总结:
提示：这里对文章进行总结：
以上就是今天的学习内容，本文是Java数据结构的学习，学习哈希表的底层原理，解决哈希冲突的方法，以及负载因子的作用。之后的学习内容将持续更新！！！