# 哈希

## 散列表

散列表也叫**哈希表**，**Hash表**或者**Hash Table**。是一种`Key-Value`数据结构。

散列表是数组的一种扩展，由数组演化而来。利用了数组支持按照下标随机访问数据的特性。

### 散列表的名词：

* 键：也叫关键字。
* 散列函数：也叫哈希函数，将键转换为数组下标的映射方法。
* 散列值：也叫哈希值，散列函数得到的值。

### 散列表实现机制

* 散列函数将元素的键映射为下标，然后将元素数据存储在数组中对应下标的位置。
* 查找时，用散列函数，将键转换为数组下标，从对应的数组下标位置获取数据。

## 散列函数

散列函数设计要求：

* 计算得到的散列值是一个非负整数。
* 如果`key1 == key2`，那么`hash(key1) == hash(key2)`。
* 如果`key1 != key2`，那么`hash(key1) != hash(key2)`。

## 散列冲突

对于不同的`key`，要使计算出的散列值完全不一样几乎不可能。

无冲突的哈希函数设计困难，数组存储空间有限，都是造成散列冲突的原因。

### 散列冲突解决办法

常用方法有两类：

* 开放寻址法
* 链表法

## 开放寻址法

### 思想：

如果出现散列冲突，就重新探测一个空闲位置。

### 探测方法：

* 线性探测

  插入数据时，如果位置被占用，就从当前位置开始一次往后查找，直到有空闲位置为止。

  查找数据时，将数组中下标为散列值的元素与要查找的元素对比，如果相等则结束，如果不等则依次往后查找。

  删除数据时，将删除元素标记为`deleted`。

  插入、查找、删除操作的最坏时间复杂度为`O(n)`。
* 二次探测

  移动步长变成了二次方，如`0^2, 1^2, 2^2...`。
* 双重探测

  使用一组散列函数，如果第一个散列函数计算出的位置被占用，则使用下一个散列函数进行计算。

## 链表法

散列表的每个槽，对应一条链表。

散列值相同的元素，会被放到相同槽位的链表上。

## 散列表碰撞攻击

精心构造数据，使其散列到同一个槽中。如果使用链表法解决冲突，这是散列表就会退化成链表。

散列表的查询效率会急剧恶化，并且消耗大量`CPU`和线程资源，导致系统无法响应其它请求。

进而达到拒绝服务攻击`DoS`的目的。

## 装载因子

为了保证散列表操作效率，一般会要求散列表中有一定比例的空闲槽位。

空闲位置的多少使用装载因子来衡量：

```
装载因子 = 填入表中的元素个数 / 散列表的长度
```

装载因子越大，散列表中元素越多，空闲位置越少，散列冲突概率越大。

当装载因子过大时，可以动态扩容。

当装载因子过小时，可以动态缩容。

## 动态扩容

当装载因子到达阈值时，先申请新空间，但是并不搬移老的数据。

有新数据插入时，将新数据插入新散列表中，并且从老的散列表中拿出一个值，放入新的散列表。

多次插入操作过后，老数据就完成了搬移。

查找数据时，需要先从新散列表中查找，如果没有找到，再去老的散列表中查找。
