【C++】哈希Hash（未完成）

学习完了红黑树以及map/set，下面让我们来康康另外一种用于查找数据的新方式，那便是哈希表

1.概念

哈希是一种用下标映射来查找数据的方式。在STL库中，有map和set的unordered(即为stl库里面的哈希)版本

我们可以来对比一下它和红黑树（map/set的标准版本）的查找时间差距（是通过for循环查找所有插入数据来实现的计时）

可以看到，在查找方面，unordered版本查找的速度比正常的map和set快了一倍有余。之前我已经觉得搜索二叉树的查找已经非常快了，实际上哈希才是真正的快中之快！

这两种算法的时间复杂度为：

• 平衡二叉搜索树 O(logN)
• 哈希算法 O(1)

因为哈希是直接从对应的下标映射位置找到数据的，这就和我们进行随机访问顺序表里面的数据一样，都是O(1)的直接访问

1.1 下标映射

那么，要怎么对一个数据进行下标映射呢？

• 假设我们现在有一个长度为10的数组
• 我们需要存放一组int类型的数据，0-9以内的数字可以直接通过下标映射放入对应位置。而大于9的数据则需要进行取模操作，找到对应的下标。比如12%10=2，则放入下标为2的位置

那，如果一个下标位置本来就有数据了怎么办?我们有两种办法来解决这个问题

1.2 闭散列（开放定址法）

当一个下标的位置已经有数据的时候，如果哈希表还没有满，我们可以往这个映射位置的后方插入这个数据

• 线性探测：依次去找空位置，找到后直接插入
• 二次探测：跳跃地找空位置，不会出现太多的拥堵

你可能会问，不对啊。你把别人的位置占了，到时候被人要用这个位置，该怎么去操作啊？

没错，这个就是闭散列的一大缺点：会占用原本属于其他人的空间。

1.3 开散列（拉链法）

这时候我们就需要用到拉链法。于其在每一个下标映射的位置插入一个数据，我们不如整一个链表。在原有的哈希表中存放链表的头节点。当有相同映射值的数据插入的时候，我们可以执行链表的头插，使其挂载到相同位置的链表上。

• 这个链表也被称为桶

而没有数据的映射位置，全都为nullptr空指针

在这个应用场景下，我们只需要使用单链表即可以完成桶的操作。若使用list或者自己写的双链表，则会出现不必要的空间浪费。

你可能会问，那如果一个映射值挂载了特别多的节点，查找的效率会不会从O(1)变成O(N)（即需要遍历一个链表）的时间复杂度呢？

这就必须要提到哈希表的扩容问题了

1.4 什么时候需要扩容？

在哈希表中，我们一般会定义一个负载因子，用于标记哈希表的数据个数

负载因子=已有元素个数/总长度

当负载因子大于一定数量级的时候，也就是哈希表快要满的时候，插入数据遇到冲突的可能性就非常大。即便我们用拉链法挂载了桶，如果冲突很多的话，就容易出现上面说的效率低下问题。

而如果我们的负载因子不大的时候，大部分情况新插入的节点都能找到它自己独立的没有冲突的映射位置，这样就大大增加了访问效率

• 需要注意的是，哈希表的映射关系和表的长度相关
• 所以当我们扩容之后，需要把当前表内的所有元素拿出来，根据键值重新进行下标映射，插入进新表。

对于开放定址法，负载因子应该限制在0.8以下。java的系统库中就以0.75作为了负载因子的限制值，超过此值将进行扩容操作

---

1.5 怎么映射？

关于映射的即便理念、冲突、扩容问题我们都已经提到了。现在还有一个重要的问题，那就是怎么映射？

如果我们插入的数据是int或者char、double这种可以强转为int的类型作为key，那还算好操作，直接用int进行下标映射即可。

• 那假如我们用string/自定义类型来作为key呢？

这种类型不能直接强制转为int，虽然string我们可以取第一个元素的ASCII码作为映射值。但是那么做的冲突会非常多，ABC/ADFC/ASD这些字符串都是以A开头，难道我们就要把它放在相同位置下面吗？那样效率也太低了！

• 可不可以把字符串每一个字符的ASCII加起来呢？

这样能解决一定程度上的冲突，但是ABC/ACB这种字符串排列不同，但是字符是相同的字符串，就会得出相同的结果造成冲突。

---

这时候就有一个不知名的程序猿[Dennis M. Ritchie](https://baike.baidu.com/item/Dennis M. Ritchie/1971171?fromModule=lemma_inlink)想出来了一个超级牛逼的办法：把每一个char的ASCII都乘上一个数，再进行相加

size_t operator()(const string& key)
{
    size_t hash = 1;
    for (auto s : key)
    {//每一次都*13，避免冲突
        hash = hash * 13 + s;
    }
    return hash;
}

因为字符串的排列顺序不相同，所以每一次获得的hash值肯定是不同的，再乘上一个数之后，就完美的避免了大部分的冲突问题。

这个方法可以沿用到所有自定义类型！比如我们之前写的日期类，就可以把年加入hash之后，乘一个数再加月，再乘一个数再加天

这么牛逼的方法，怎么可能是不知名程序员想出来的？咳咳，实际上，Dennis M. Ritchie还有另外一个名字“C语言之父”

膜拜大佬，大佬牛逼！😍

---

在本篇博客中就不去讲解STL库中unordered_map/set的使用办法了，因为它们的使用和基础的map/set相差无几。我们直接开始模拟实现

2.哈希表1-开放定址法

2.1 插入

插入的时候，我们要做的便是遵循哈希表的映射方法，对key进行映射，再将pair插入进封装好的vector中

插入的思路如下：

• 首先判断哈希表中是否有相同键值key的数据（此时我们写的是不支持键值冗余的哈希表，如果出现相同键值的数据，则不再进行二次插入return false（这里复用了查找函数）
• 若没有这个键值，则判断负载因子的占比。这里我设置的负载因子是0.7，超过这个比例的时候，将会执行扩容操作。注意：扩容之后映射的位置会发生变化，所以我们需要对已有的数据进行重新插入。
• 扩容（或不需要扩容）结束后，我们利用预先写好的仿函数获取道key的hash值，找到对应下标位置。这里采用线性探测的方法，如果当前的下标位置已经有数据了，则往后查找状态值为EMPTY/DELETE的位置，并将我们的数据插入到这个位置上。
• 插入成功后，将状态修改为EXITS，return true插入结束

bool Insert(const pair<K, V>& kv)
{
    if (Find(kv.first))//找到了相同的键值，直接退出（说明已经插入过了）
    {
        return false;
    }

    // 负载因子到0.7及以上，就扩容（避免冲突）
    if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
    {
        size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
        // 扩容以后，需要重新映射
        HashTable<K, V, HashFunc> newHT;
        newHT._tables.resize(newSize);// 扩容vector
        // 遍历旧表，插入newHT
        for (auto& e : _tables)
        {
            if (e._state == EXITS)
            {
                newHT.Insert(e._kv);
            }
        }
        newHT._tables.swap(_tables);
        //利用vector的交换，这是一种现代写法的深拷贝
    }

    HashFunc hf;// 仿函数的实例化
    size_t starti = hf(kv.first);
    starti %= _tables.size();

    size_t hashi = starti;
    size_t i = 1;
    // 线性探测/二次探测
    // 线性探测代表是自映射值开始往后依次找为空的位置
    // 二次探测指跳着找为空的位置
    while (_tables[hashi]._state == EXITS)
    {
        hashi = starti + i;
        ++i;//依次查找，为线性探测
        hashi %= _tables.size();
    }

    _tables[hashi]._kv = kv;//插入数据
    _tables[hashi]._state = EXITS;//修改状态码
    _n++;//长度+1

    return true;
}

2.2 查找

和之前模拟实现的map一样，查找函数我们需要返回一个data，以便用户修改value

因为这里我们使用的是开放定址法，没有设置桶。所以查找的操作和顺序表的查找没有本质上的区别。

• 当映射值的位置就是我们需要找的key，直接返回当前的位置
• 当当前映射值的数据不是我们需要找的key，说明这个地方出现了冲突。这时候我们现需要往后查找（线性探测，依次查找）查找的时候需要判断状态码
  • 如果状态码为EMPTY，则代表后面没有这个数据，返回nullptr代指找不到
  • 如果状态码为EXITS或者DELETE，说明后面还有可能找到这个数据找到数据后返回该数据的引用
• 如果遍历完整个列表，还是没有找到该数据，同样返回nullptr

这里单独说明DELETE：在insert和find操作之中，我们可能执行了删除，这时候就有可能导致原本的映射值位置和线性探测后的位置之中出现了状态码为DELETE的位置。遇到DELETE并不代表后面没有这个键值，我们需要继续查找。这点和insert的判断不同。

代码实现如下

//查找
Data* Find(const K& key)
{
    //空表
    if (_tables.size() == 0)
    {
        return nullptr;
    }

    HashFunc hf;//仿函数的实例
    size_t starti = hf(key);//利用hash仿函数算出起始值
    starti %= _tables.size();//进行膜大小，获取道映射值

    size_t hashi = starti;
    size_t i = 1;
    while (_tables[hashi]._state != EMPTY)
    {
        if (_tables[hashi]._state != DELETE && _tables[hashi]._kv.first == key)
        {
            return &_tables[hashi];
        }

        hashi = starti + i;
        ++i;//线性探测
        hashi %= _tables.size();
    }

    return nullptr;
}

2.3 删除

删除操作比较简单，我们利用find找到键值后，直接把这个位置的状态码改成DELETE即可，并不需要执行释放空间的操作。

如果没有这个键值，则返回false

//删除，找到映射位置之后，直接修改状态码，而不是真的删除这个内容
bool Erase(const K& key)
{
    Data* ret = Find(key);
    if (ret)
    {
        ret->_state = DELETE;
        _n--;
        return true;
    }
    else
    {
        return false;
    }
}

---