哈希概念

顺序结构和平衡树中 元素关键码和它的储存位置之间没有对应的关系

因此 在我们查找一个元素时 必须要经过关键码的多次比较

搜索的效率取决于搜索过程中的比较次数

在顺序结构中 这个效率是N

在平衡树结构中 这个效率是Log(N)

对于我们来说 最理想的搜索方法是经过常数次比较 也就是在时间复杂度O(1)的情况下找到元素

为了达到我们上面的效果 我们可以创造出一种结构 该结构通过某种函数让元素的储存位置和关键码之间建立一一映射的关系

向该结构插入和搜索元素的时候遵循以下规则

插入元素： 根据待插入元素的关键码 经过计算找到储存位置 并将元素储存到该位置

搜索元素： 对元素的关键码进行相同的计算找到理论储存位置 并与该位置的元素进行比较 若相同则搜索成功

这种构造方式即为哈希（散列）方法

哈希方法中使用的转换函数叫做哈希（散列）函数

构造出来的表被称为哈希表（散列表）

举例

例如 当集合为{1, 7, 6, 4, 5, 9}

我们将哈希函数设置为 hash(key) = key % capacity

其中capacity为储存元素空间的总大小

若我们将该集合储存在capacity大小为10的哈希表中 各元素的储存位置对应如下

使用该方法进行存储 则只需要通过哈希函数判断对应位置是否存放着待查找元素

而不必进行多次关键码的比较 因而效率较高

哈希冲突

不同的关键字通过相同的哈希函数计算出相同的哈希地址 这种情况叫做哈希冲突或者叫哈希碰撞

我们把关键码不同而具有相同哈希地址的数据元素称为 “同义词”

比如说在上面的例子中如果我们再插入一个数据11 就会引起哈希冲突

hash(11) = 11 % 10 = 1

哈希函数

引起哈希冲突的一个原因可能是哈希函数设计的不够合理

这里给出哈希函数设计的三条原则

1 哈希函数的定义域必须要包括需要储存元素的所有关键码 若散列表允许有m个地址 其值域必须要在0~m-1之间

2 哈希函数计算出来的地址要尽可能均匀的分布在整个空间中

3 哈希函数应该比较简单

这里给出两个常用的哈希函数

一 直接定址法

取关键字的某个线性函数的哈希地址为 ： Hash(key) = A * key + B

优点 每个值都有一个唯一的对应位置 效率很高 一次就能找到

缺点 使用场景比较局限 只能是整数且数据范围比较集中

二 除留余数法

假设散列表中的允许的存在的地址数为m 则取一个不大于m但是接近于m的质数p作为除数

按照哈希函数 Hash(key) = key % p 将关键码转化为哈希地址

优点： 使用场景广泛 不受限制

缺点： 存在哈希冲突 哈希冲突越多 效率下降越厉害

哈希冲突的解决方式之一

闭散列 --开放定址法

闭散列 也叫开放定址法 当哈希发生冲突的时候 如果哈希表未被装满 则表示一定有剩余的位置 那么可以把冲突的元素存放到下一个位置去

寻找下一个位置的方式有很多种 还是一样 我们介绍比较常见的两种

一 线性探测

当哈希冲突发生时候 从发生冲突位置开始 依次向后探测 直到找到下一个空位置为止

例如我们上面的例子

这里的11就找到了下一个空的位置 也就是1后面的一个位置

当然随着我们插入数字的增多 哈希冲突的概率必然会增加

为了解决这个问题 我们引入一个叫做负载因子的概念

负载因子 = 表中有效数据的个数 / 空间的大小

负载因子越大 产生冲突的概率越高 增删查改的效率越低

负载因子越小 产生冲突的概率越低 增删查改的效率越高

但是当负载因子越小 实际上也说明了空间利用率越低 因此大量的空间实际上都被浪费掉了

对于闭散列来说 负载因子是十分重要的一个参数 一般控制在0.7~0.8之间

负载因子高于0.8则会导致在查表示缓存不命中按照指数上升（因为多次哈希冲突）

所以一些采用开放定址法的hash库 比如说java的系统库 限制了负载因子为0.75

如果超过0.75则会对哈希表进行增容

线性探测的优点： 实现非常的简单

线性探测的缺点： 一旦发生冲突 所有的冲突连在一起 容易产生数据的堆积 即不同的关键码占据了可利用的空位置 使得寻找某关键码的位置需要比较多次 导致搜索效率变低

二 二次探测

线性探测的缺点是产生冲突的数据堆积在一起 这个缺点和它总是找下一个空位置有关系

为了解决这个缺陷我们发明了二次探测

我们使用下面的哈希函数

Hi=(H0+i^2)%m ( i = 1 , 2 , 3 , . . . ) (i=1,2,3,…)

这样子即使发生哈希冲突了 数据寻找下一个位置的时候也不会那么集中

能够很有效的缓解堆积的问题

和线性探测一样 二次探测也需要关注负载因子

因此 闭散列最大的缺陷就是空间利用率不足 这也是哈希的缺陷

哈希表的闭散列实现

哈希表的结构

在闭散列的哈希表中 哈希表的每个位置除了储存所给数据之外 还需要存储当前位置的状态

哈希表的每个位置可能有以下三种状态

1 EMPTY(空)

2 EXIST(存在)

3 DELETE(存在过数据 但是被删除了)

我们可以使用枚举来定义这三种状态

// 标记每个位置的状态
enum State
{
  EMPTY,
  EXIST,
  DELETE
};

这里抛出一个问题

我们为什么需要标记哈希表每个位置的状态呢？

我们首先来看一个场景 以除留余数法的线性探测为例 假设一个哈希表的大小是10

我们现在要查找一个元素40 步骤如下

1 通过除留余数法求得40在哈希表中的映射是0

2 从0下标开始往后找 若找到40则存在

但是我们寻找40的时候不可能将整个哈希表遍历一遍 这样子就失去了哈希表的意义

那么什么时候停止呢？

我们说 只要找到一个空位置就停止

为什么 因为根据线性探测的规则 我们从计算出的位置开始往后找 只要找到之后就会插入

所以说如果到空位置了还没找到就一定是不存在这个元素

但是到这里就会引发两个新问题

1 我们如何标志一个位置是存在还是不存在呢？ 使用数据0来标志吗？ 可是假如这个位置本来存储的数据就是0呢？

2 假如查找的时候中间有一个位置被删除了 那么这个位置是空吗？ 如果是空 我们是不是就找不到后面的数据了

所以说 我们针对这几个问题设计了哈希表数据的三种状态 存在 空 和删除

使用这三种状态就能解决上面的所有问题

我们这里先给出哈希数据的结构

template<class K,class V>
struct HashData
{
  pair<K, V> _kv;
  State _state = EMPTY; // 状态默认设置为空
};

为了能够更好的计算负载因子 我们还应该储存整个哈希表的有效元素

template<class K, class V>
class HashTable
{
public:
  // ..
private:
  vector<HashData<K, V>> _table; //哈希表
  size_t _n = 0; // 哈希表中有效元素个数
};

哈希表的插入

向哈希表中插入数据的步骤如下

1 查看哈希表中是否存在该键值对 若存在则插入失败

2 判断是否需要调整哈希表的大小

3将键值对插入哈希表

4 调整哈希表的大小

其中哈希表的调整方式如下

如果哈希表的大小为0 则扩容至10

如果哈希表的负载因子大于0.7 则先创建一个新哈希表 新的哈希表大小为原来的两倍 之后遍历原哈希表 将其中的所有元素放到新哈希表中 最后将原哈希表和新哈希表交换即可

将键值对插入哈希表的方式如下

通过哈希函数计算出对应的哈希地址

若产生哈希冲突 则从哈希地址处开始 采用线性探测向后寻找一个状态为EMPTY或DELETE的位置

将键值对插入到该位置 并将该位置的状态设置为EXIST

bool Insert(const pair<K, V>& kv)
  {
  // 1. 查看哈希表中是否存在该键值的键值对 
  HashData<K, V>* ret = Find(kv.first);
  if (ret)
  {
    return false; // 如果存在则表示插入失败
  }
  // 2. 判断是否需要调整哈希表的大小
  if (_table.size() == 0)
  {
    _table.resize(10);
  }
  else if ((double)_n / (double)_table.size() > 0.7) // 这里涉及到小数 有两种方式 一种是扩大十倍 一种是转换double 
  {
    // 扩容
    HashTable<K, V> newHT;
    newHT._table.resize(2 * _table.size());
    // 将原哈希表中的数据插入到新哈希表中
    for (auto& e : _table)
    {
    if (e._state == EXIST)
    {
      newHT.Insert(e._kv);
    }
    }
    // 交换这两个哈希表
    _table.swap(newHT._table);
  }
  // 将键值对插入哈希表
  size_t start = kv.first % _table.size();
  size_t index = start;
  size_t i = 1;
  // 找到一个EMPTY或者是DELETE的位置
  while (_table[index]._state == EXIST)
  {
    index = start + i;
    index% _table.size(); // 防止下标超出哈希范围
    i++;
  }
  _table[index]._kv = kv;
  _table[index]._state = EXIST;
  _n++;
  return true;  
  }

哈希表的查找

哈希表的查找分为以下几步

先判断哈希表中的大小是否为0 为0则查找失败

通过哈希函数计算出一个哈希地址

在这个地址的基础上一直往后找直到找到待查找的值或者空

代码表示如下

HashData<K, V>* Find(const K& key)
  {
  if (_table.size() == 0)
  {
    return nullptr;
  }
  size_t start = key % _table.size();
  size_t index = start;
  size_t i = 1;
  while (_table[index]._state != EMPTY)
  {
    if (_table[index]._state == EXIST && _table[index]._kv.first == key)
    {
    return &_table[index];
    }
    index = start + i;
    index% _table.size(); // 防止下标超出哈希范围
    i++;
  }
  return nullptr;
  }

哈希表的删除

哈希表的删除就十分简单了

我们只需要找到删除元素 然后将改数据的状态改为DELETE即可

步骤如下

查看哈希表中是否有该键值对存在 若不存在则返回失败

若存在 则将该键值对所在位置的状态改为DELETE即可

之后别忘记将有效元素数据减一

代码表示如下

bool Erase(const K& key)
  {
  HashData<K, V>* ret = Find(key);
  if (ret)
  {
    ret->_state = DELETE;
    _n--;
    return true;
  }
  return false;