自己动手实现 HashMap（上篇）——不看血亏！！！
# HashMap（Python字典）设计原理与实现（上篇）——哈希表的原理
在此前的[四篇长文](https://github.com/Chang-LeHung/CSCore)当中我们已经实现了我们自己的`ArrayList`和`LinkedList`，并且分析了`ArrayList`和`LinkedList`的`JDK`源代码。 本篇文章主要跟大家介绍我们非常常用的一种数据结构`HashMap`，在本篇文章当中主要介绍他的实现原理，下篇我们自己动手实现我们自己的`HashMap`，让他可以像`JDK`的`HashMap`一样工作。
如果有公式渲染不了，可查看这篇[内容相同且可渲染公式的文章](https://mp.weixin.qq.com/s?__biz=Mzg3ODgyNDgwNg==&mid=2247484145&idx=1&sn=362cf64866ace02ac95c0c1a970393e4&chksm=cf0c9ef8f87b17eebb61ea422f58e9e439632783e9faa5a3b2ce55712c1582b140904b60cb17&token=1155116583&lang=zh_CN#rd)
## HashMap初识
如果你使用过`HashMap`的话，那你肯定很熟悉`HashMap`给我们提供了一个非常方便的功能就是`键值(key, value)`查找。比如我们通过学生的姓名查找分数。
```java
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>();
map.put("学生A", 60);
map.put("学生B", 70);
map.put("学生C", 20);
map.put("学生D", 85);
map.put("学生E", 99);
System.out.println("学生B的分数是：" + map.get("学生B"));
}
```
我们知道`HashMap`给我们提供查询`get函数`功能的时间复杂度为`O(1)`，他在常数级别的时间复杂度就可以查询到结果。那它是如何做到的呢？
我们知道在计算机当中一个最基本也是唯一的，能够实现常数级别的查询的类型就是数组，数组的查询时间复杂度为`O(1)`，我们只需要通过下标就能访问对应的数据。比如我们想访问下标为`6`的数据，就可以这样：
```java
String[] strs = new String[10];
strs[6] = "一无是处的研究僧";
System.out.println(strs[6]);
```
因此我们要想实现`HashMap`给我们提供的`O(1)`级别查询的时间复杂度的话，就必须使用到数组，而在具体的`HashMap`实现当中，比如说`JDK`底层也是采用数组实现的。
## HashMap整体设计
我们实现的`HashMap`需要满足的最重要的功能是根据`键(key)`查询到对应的`值(value)`，比如上面提到的根据学生姓名查询成绩。
因此我们可以有一个这样的设计，我们可以根据数据的`键值`计算出一个数字（像这种可以将一个数据转化成一个数字的叫做`哈希函数`，计算出来的值叫做`哈希值`我们后续将会仔细说明），将这个哈希值作为数组的下标，这样的话`键值`和下标就有了对应关系了，我们可以在数组对应的哈希值为下标的位置存储具体的数据，比如上面谈到的`成绩`，整个流程如下图所示：
但是像这种哈希函数计算出来的数值一般是没有范围的，因此我们通常通过哈希函数计算出来的数值通常会经过一个求余数操作(`%`)，对数组的长度进行求余数，否则求出来的数值将超过数组的长度。比如数组的长度是16，计算出来的哈希值为186，那么求余数之后的结果为`186%16=10`，那么我们可以将数据存储在数组当中下标为10的位置，下次我们来取的时候就取出下标为10位置的数据即可。
## 如何设计一个哈希函数？
首先我们需要了解一个知识，那就是在计算机世界当中我们所含有的两种最基本的数据类型就是，整型(`short`, `int`, `long`)和字符串(`String`)，其他的数据类型可以由这些数据类型组合起来，下面我们来分析一下常见的数据类型的哈希函数设计。
### 整型的哈希函数
对于整型数据，他本来就是一个数值，因此我们可以直接将这个值返回作为他的哈希值，而`JDK`中也是这么实现的！`JDK`中实现整型的哈希函数的方法：
```java
/**
* Returns a hash code for a {@code int} value; compatible with
* {@code Integer.hashCode()}.
*
* @param value the value to hash
* @since 1.8
*
* @return a hash code value for a {@code int} value.
*/
public static int hashCode(int value) {
return value;
}
```
### 字符串的哈希函数
我们知道字符串底层存储的还是用整型数据存储的，比说说字符串`hello world`，就可以使用字符数组`['h', 'e', 'l', 'l', 'o' , 'w', 'o', 'r', 'l', 'd']`进行存储，因为我们计算出来的这个哈希值需要尽量不和别的数据计算出来的哈希值冲突（这种现象叫做`哈希冲突`，我们后面会仔细讨论这个问题），因此我们要尽可能的充分利用字符串里面的每个字符信息。我们来看一下`JDK`当中是怎么实现字符串的哈希函数的
```java
public int hashCode() {
// hash 是 String 类当中一个私有的 int 变量，主要作用即存储计算出来的哈希值
// 避免哈希值重复计算 节约时间
int h = hash; // 如果是第一次调用 hashCode 这个函数 hash 的值为0，也就是说 h 值为 0
// value 就是存储字符的字符数组
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
// 更新 hash 的值
hash = h;
}
return h;
}
```
上面的计算`hashCode`的代码，可以用下面这个公式表示：
- 其中`s`，表示存储字符串的字符数组
- `n`表示字符数组当中字符的个数
$$
s[0]*31^{(n-1)} + s[1]*31^{(n-2)} + ... + s[n-1]
$$
### 自定义类型的哈希函数
比如我们自己定义了一个学生类，我们改设计他的哈希函数，并且计算他的哈希值呢？
```java
class Student {
String name;
int grade;
}
```
我们可以根据上面提到的两种哈希函数，仿照他们的设计，设计我们自己的哈希函数，比如像下面这样。
```java
class Student {
String name;
int grade;
// 我们自己要实现的哈希函数
@Override
public int hashCode() {
return name.hashCode() * 31 + grade;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Student student = (Student) o;
return grade == student.grade &&
Objects.equals(name, student.name);
}
}
```
事实上`JDK`也贴心的为我们实现了一个类，去计算我们自定义类的哈希函数。
```java
// 下面这个函数是我们自己设计的类 Student 的哈希函数
@Override
public int hashCode() {
return Objects.hash(name, grade);
}
// 下面这个函数为 Objects.hash 函数
public static int hash(Object... values) {
return Arrays.hashCode(values);
}
// 下面这个函数为 Arrays.hashCode 函数
public static int hashCode(Object a[]) {
if (a == null)
return 0;
int result = 1;
for (Object element : a)
result = 31 * result + (element == null ? 0 : element.hashCode());
return result;
}
```
`JDK`帮助我们实现的哈希函数，本质上就是将类当中所有的字段封装成一个数组，然后像计算字符串的哈希值那样去计算我们自定义类的哈希值。
### 集合类型的哈希函数
其实集合类型的哈希函数也可以像字符串那样设计哈希函数，我们来看一下`JDK`内部是如何实现集合类的哈希函数的。
```java
public int hashCode() {
int hashCode = 1;
// 遍历集合当中的对象，进行哈希值的计算
for (E e : this)
hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
return hashCode;
}
```
上述代码也可以用之前的公式来表示，其中`s[i]`表示集合当中第`i`个数据对象：
$$
s[0]*31^{(n-1)} + s[1]*31^{(n-2)} + ... + s[n-1]
$$
## 哈希冲突
因为我们用的最终的数组的下标是通过哈希值取余数得到的，那么就有可能产生冲突。比如说我们的数组长度为`10`，有两个数据他们的哈希值分别为`8`和`28`，他们对`10`取余之后得到的结果都为`8`那么改如何解决这个问题呢？
### 开放地址法（再散列法）
#### 线性探测再散列
假设我们的哈希函数为`H`，我们的数组长度为`m`，我们的键为`key`，那么我计算出来的下标为：
$$
h_i = H(key) \% m
$$
当我们有哈希冲突的时候，我们计算下标的方法变为：
$$
h_i = (H(key) + d_i) \% m, d_i = i
$$
当我们第一次冲突的时候$d_1 = 1$，如果重新进行计算仍然冲突那么$d_2 = 2$ ......
比如在上图当中我们首次计算的哈希值$H(key) = 5$的结果等于5，如果有哈希冲突，那么下次计算出来的哈希值为$(H(key) + 1) \% 12 = 6$，如果还是冲突那么计算出来的哈希值为$(H(key) + 2) \% 12 = 7$ ......，直到找到一个空位置。谈到这里你可能会问，万一都满了呢？我们在下一小节再谈这个问题。
#### 二次探测再散列
$$
h_i = (H(key) + d_i) \% m, d_i = (-1)^{i - 1} i^2
$$
这个散列方法和线性探测散列差不多，只不过$d_i$的值变化情况不一样而已，大家可以参考线性探测进行分析，这个方法可以往数组的两个方法走，因为前面有一个而线性探测只能往数组的一个方向走。此外这个方法走的距离比线性探测更大，因此可能可以在更小的冲突次数当中找到一个`空位置`。
#### 伪随机数再散列
$$
h_i = (H(key) + d_i) \% m, d_i = 一个随机数
$$
这个方式的大致策略和前面差不多，只不过$d_i$上稍微有所差异。
### 再哈希法
我们可以准备多个哈希函数，当使用一个哈希函数产生冲突的时候，我们可以换一个哈希函数，希望通过不同的哈希函数得到不同的哈希值，以解决哈希冲突的问题。
### 链地址法
这个方法是目前使用比较多的方法，当产生哈希冲突的时候，数据用一个链表将冲突的数据链接起来，比如像下面这样：
以上就是一些常见的解决哈希冲突的方法，因为都是文字说明没有代码，你可能稍微有些难以理解，比如说我通过上面的方法存储数据，那么我之后怎么拿到我存进去的数据呢？好像放进去就拿不出来了呀🤣🤣🤣！没事儿，这些疑问我们在`下篇`自己实现哈希表的时候会一一解开，到时候你就发现原来这些算法的设计如此巧妙。
## 扩容
在上面的文章当中我们并没有谈到当数组满了之后怎么办。很简单嘛，我可以使用一个变量记录数组当中已经使用了的空间，如果全部使用过了，我们就进行扩容，扩大我们的数组就可以了嘛！然后将原数组当中的数据重新进行哈希存放到新数组当中即可！因为我们在计算存储下标的时候需要对数组长度进行取余，而当我们申请新数组的时候数组长度已经发生变化了，因此需要重新对数据进行哈希操作。这里面仍然有很多需要考虑的细节问题，这些问题我们在`下篇`当中进行代码实现的时候会仔细讨论。
## 总结
在本篇文章当中，我们主要谈到了如何去设计一个可以使用的哈希表，同时介绍了我们改如何设计一个哈希函数，最终谈到了解决哈希冲突和数组满了的问题！！！
- `HashMap`整体的设计结构。
- 设计一个好的哈希函数。
- 整型数据的哈希函数。
- 字符串的哈希函数。
- 自定义类型的哈希函数。
- 集合的哈希函数。
- 解决哈希冲突的办法。
- 开放地址法
- 线性探测
- 二次探测
- 随机数探测
- 再哈希法
- 链地址地址法
- 扩容方法
以上就是本篇文章的所有内容了，我们将在`下篇`当中自己动手实现一个自己的哈希表`MyHashMap`，这其中还有很多非常细节的设计，其中涉及到很多位运算操作和很多其他非常巧妙的操作。我是LeHung我们下期再见！！！
更多精彩内容合集，可访问：https://github.com/Chang-LeHung/CSCore
关注公众号：一无是处的研究僧，了解更多计算机知识！！！
#数据结构##容器##Java集合#
在此前的[四篇长文](https://github.com/Chang-LeHung/CSCore)当中我们已经实现了我们自己的`ArrayList`和`LinkedList`，并且分析了`ArrayList`和`LinkedList`的`JDK`源代码。 本篇文章主要跟大家介绍我们非常常用的一种数据结构`HashMap`，在本篇文章当中主要介绍他的实现原理，下篇我们自己动手实现我们自己的`HashMap`，让他可以像`JDK`的`HashMap`一样工作。
如果有公式渲染不了，可查看这篇[内容相同且可渲染公式的文章](https://mp.weixin.qq.com/s?__biz=Mzg3ODgyNDgwNg==&mid=2247484145&idx=1&sn=362cf64866ace02ac95c0c1a970393e4&chksm=cf0c9ef8f87b17eebb61ea422f58e9e439632783e9faa5a3b2ce55712c1582b140904b60cb17&token=1155116583&lang=zh_CN#rd)
## HashMap初识
如果你使用过`HashMap`的话，那你肯定很熟悉`HashMap`给我们提供了一个非常方便的功能就是`键值(key, value)`查找。比如我们通过学生的姓名查找分数。
```java
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>();
map.put("学生A", 60);
map.put("学生B", 70);
map.put("学生C", 20);
map.put("学生D", 85);
map.put("学生E", 99);
System.out.println("学生B的分数是：" + map.get("学生B"));
}
```
我们知道`HashMap`给我们提供查询`get函数`功能的时间复杂度为`O(1)`，他在常数级别的时间复杂度就可以查询到结果。那它是如何做到的呢？
我们知道在计算机当中一个最基本也是唯一的，能够实现常数级别的查询的类型就是数组，数组的查询时间复杂度为`O(1)`，我们只需要通过下标就能访问对应的数据。比如我们想访问下标为`6`的数据，就可以这样：
```java
String[] strs = new String[10];
strs[6] = "一无是处的研究僧";
System.out.println(strs[6]);
```
因此我们要想实现`HashMap`给我们提供的`O(1)`级别查询的时间复杂度的话，就必须使用到数组，而在具体的`HashMap`实现当中，比如说`JDK`底层也是采用数组实现的。
## HashMap整体设计
我们实现的`HashMap`需要满足的最重要的功能是根据`键(key)`查询到对应的`值(value)`，比如上面提到的根据学生姓名查询成绩。
因此我们可以有一个这样的设计，我们可以根据数据的`键值`计算出一个数字（像这种可以将一个数据转化成一个数字的叫做`哈希函数`，计算出来的值叫做`哈希值`我们后续将会仔细说明），将这个哈希值作为数组的下标，这样的话`键值`和下标就有了对应关系了，我们可以在数组对应的哈希值为下标的位置存储具体的数据，比如上面谈到的`成绩`，整个流程如下图所示：
但是像这种哈希函数计算出来的数值一般是没有范围的，因此我们通常通过哈希函数计算出来的数值通常会经过一个求余数操作(`%`)，对数组的长度进行求余数，否则求出来的数值将超过数组的长度。比如数组的长度是16，计算出来的哈希值为186，那么求余数之后的结果为`186%16=10`，那么我们可以将数据存储在数组当中下标为10的位置，下次我们来取的时候就取出下标为10位置的数据即可。
## 如何设计一个哈希函数？
首先我们需要了解一个知识，那就是在计算机世界当中我们所含有的两种最基本的数据类型就是，整型(`short`, `int`, `long`)和字符串(`String`)，其他的数据类型可以由这些数据类型组合起来，下面我们来分析一下常见的数据类型的哈希函数设计。
### 整型的哈希函数
对于整型数据，他本来就是一个数值，因此我们可以直接将这个值返回作为他的哈希值，而`JDK`中也是这么实现的！`JDK`中实现整型的哈希函数的方法：
```java
/**
* Returns a hash code for a {@code int} value; compatible with
* {@code Integer.hashCode()}.
*
* @param value the value to hash
* @since 1.8
*
* @return a hash code value for a {@code int} value.
*/
public static int hashCode(int value) {
return value;
}
```
### 字符串的哈希函数
我们知道字符串底层存储的还是用整型数据存储的，比说说字符串`hello world`，就可以使用字符数组`['h', 'e', 'l', 'l', 'o' , 'w', 'o', 'r', 'l', 'd']`进行存储，因为我们计算出来的这个哈希值需要尽量不和别的数据计算出来的哈希值冲突（这种现象叫做`哈希冲突`，我们后面会仔细讨论这个问题），因此我们要尽可能的充分利用字符串里面的每个字符信息。我们来看一下`JDK`当中是怎么实现字符串的哈希函数的
```java
public int hashCode() {
// hash 是 String 类当中一个私有的 int 变量，主要作用即存储计算出来的哈希值
// 避免哈希值重复计算 节约时间
int h = hash; // 如果是第一次调用 hashCode 这个函数 hash 的值为0，也就是说 h 值为 0
// value 就是存储字符的字符数组
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
// 更新 hash 的值
hash = h;
}
return h;
}
```
上面的计算`hashCode`的代码，可以用下面这个公式表示：
- 其中`s`，表示存储字符串的字符数组
- `n`表示字符数组当中字符的个数
$$
s[0]*31^{(n-1)} + s[1]*31^{(n-2)} + ... + s[n-1]
$$
### 自定义类型的哈希函数
比如我们自己定义了一个学生类，我们改设计他的哈希函数，并且计算他的哈希值呢？
```java
class Student {
String name;
int grade;
}
```
我们可以根据上面提到的两种哈希函数，仿照他们的设计，设计我们自己的哈希函数，比如像下面这样。
```java
class Student {
String name;
int grade;
// 我们自己要实现的哈希函数
@Override
public int hashCode() {
return name.hashCode() * 31 + grade;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Student student = (Student) o;
return grade == student.grade &&
Objects.equals(name, student.name);
}
}
```
事实上`JDK`也贴心的为我们实现了一个类，去计算我们自定义类的哈希函数。
```java
// 下面这个函数是我们自己设计的类 Student 的哈希函数
@Override
public int hashCode() {
return Objects.hash(name, grade);
}
// 下面这个函数为 Objects.hash 函数
public static int hash(Object... values) {
return Arrays.hashCode(values);
}
// 下面这个函数为 Arrays.hashCode 函数
public static int hashCode(Object a[]) {
if (a == null)
return 0;
int result = 1;
for (Object element : a)
result = 31 * result + (element == null ? 0 : element.hashCode());
return result;
}
```
`JDK`帮助我们实现的哈希函数，本质上就是将类当中所有的字段封装成一个数组，然后像计算字符串的哈希值那样去计算我们自定义类的哈希值。
### 集合类型的哈希函数
其实集合类型的哈希函数也可以像字符串那样设计哈希函数，我们来看一下`JDK`内部是如何实现集合类的哈希函数的。
```java
public int hashCode() {
int hashCode = 1;
// 遍历集合当中的对象，进行哈希值的计算
for (E e : this)
hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
return hashCode;
}
```
上述代码也可以用之前的公式来表示，其中`s[i]`表示集合当中第`i`个数据对象：
$$
s[0]*31^{(n-1)} + s[1]*31^{(n-2)} + ... + s[n-1]
$$
## 哈希冲突
因为我们用的最终的数组的下标是通过哈希值取余数得到的，那么就有可能产生冲突。比如说我们的数组长度为`10`，有两个数据他们的哈希值分别为`8`和`28`，他们对`10`取余之后得到的结果都为`8`那么改如何解决这个问题呢？
### 开放地址法（再散列法）
#### 线性探测再散列
假设我们的哈希函数为`H`，我们的数组长度为`m`，我们的键为`key`，那么我计算出来的下标为：
$$
h_i = H(key) \% m
$$
当我们有哈希冲突的时候，我们计算下标的方法变为：
$$
h_i = (H(key) + d_i) \% m, d_i = i
$$
当我们第一次冲突的时候$d_1 = 1$，如果重新进行计算仍然冲突那么$d_2 = 2$ ......
比如在上图当中我们首次计算的哈希值$H(key) = 5$的结果等于5，如果有哈希冲突，那么下次计算出来的哈希值为$(H(key) + 1) \% 12 = 6$，如果还是冲突那么计算出来的哈希值为$(H(key) + 2) \% 12 = 7$ ......，直到找到一个空位置。谈到这里你可能会问，万一都满了呢？我们在下一小节再谈这个问题。
#### 二次探测再散列
$$
h_i = (H(key) + d_i) \% m, d_i = (-1)^{i - 1} i^2
$$
这个散列方法和线性探测散列差不多，只不过$d_i$的值变化情况不一样而已，大家可以参考线性探测进行分析，这个方法可以往数组的两个方法走，因为前面有一个而线性探测只能往数组的一个方向走。此外这个方法走的距离比线性探测更大，因此可能可以在更小的冲突次数当中找到一个`空位置`。
#### 伪随机数再散列
$$
h_i = (H(key) + d_i) \% m, d_i = 一个随机数
$$
这个方式的大致策略和前面差不多，只不过$d_i$上稍微有所差异。
### 再哈希法
我们可以准备多个哈希函数，当使用一个哈希函数产生冲突的时候，我们可以换一个哈希函数，希望通过不同的哈希函数得到不同的哈希值，以解决哈希冲突的问题。
### 链地址法
这个方法是目前使用比较多的方法，当产生哈希冲突的时候，数据用一个链表将冲突的数据链接起来，比如像下面这样：
以上就是一些常见的解决哈希冲突的方法，因为都是文字说明没有代码，你可能稍微有些难以理解，比如说我通过上面的方法存储数据，那么我之后怎么拿到我存进去的数据呢？好像放进去就拿不出来了呀🤣🤣🤣！没事儿，这些疑问我们在`下篇`自己实现哈希表的时候会一一解开，到时候你就发现原来这些算法的设计如此巧妙。
## 扩容
在上面的文章当中我们并没有谈到当数组满了之后怎么办。很简单嘛，我可以使用一个变量记录数组当中已经使用了的空间，如果全部使用过了，我们就进行扩容，扩大我们的数组就可以了嘛！然后将原数组当中的数据重新进行哈希存放到新数组当中即可！因为我们在计算存储下标的时候需要对数组长度进行取余，而当我们申请新数组的时候数组长度已经发生变化了，因此需要重新对数据进行哈希操作。这里面仍然有很多需要考虑的细节问题，这些问题我们在`下篇`当中进行代码实现的时候会仔细讨论。
## 总结
在本篇文章当中，我们主要谈到了如何去设计一个可以使用的哈希表，同时介绍了我们改如何设计一个哈希函数，最终谈到了解决哈希冲突和数组满了的问题！！！
- `HashMap`整体的设计结构。
- 设计一个好的哈希函数。
- 整型数据的哈希函数。
- 字符串的哈希函数。
- 自定义类型的哈希函数。
- 集合的哈希函数。
- 解决哈希冲突的办法。
- 开放地址法
- 线性探测
- 二次探测
- 随机数探测
- 再哈希法
- 链地址地址法
- 扩容方法
以上就是本篇文章的所有内容了，我们将在`下篇`当中自己动手实现一个自己的哈希表`MyHashMap`，这其中还有很多非常细节的设计，其中涉及到很多位运算操作和很多其他非常巧妙的操作。我是LeHung我们下期再见！！！
更多精彩内容合集，可访问：https://github.com/Chang-LeHung/CSCore
关注公众号：一无是处的研究僧，了解更多计算机知识！！！
查看42道真题和解析
