算法专栏-数据结构基础（哈希表）

文章写到这里了，我们已经了解了什么是数组什么是链表，本篇专栏为了迎合更多同学的学习梯度，主要想从数据结构开始讲起，由简入深，我一直觉得打不好基础，什么都做不好，有基础的小伙伴可以从第二章的算法开始看。

1、什么是哈希表

哈希表是一种新的存储方式，基于散列技术。散列技术建立了关键字和存储位置之间的确定对应关系，使每个关键字都对应一个存储位置。也就是说，存储位置等于关键字经过散列函数的映射结果。通过这个对应关系，我们可以在查找过程中直接通过关键字找到对应的存储位置。

 散列技术是指在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每一个关键字都对应一个存储位置。即：存储位置=f（关键字）。这样，在查找的过程中，只需要通过这个对应关系f 找到给定值key的映射f（key）。只要集合中存在关键字和key相等的记录，则必在存储位置f（key）处。我们把这种对应关系f 称为散列函数或哈希函数。

这样说可能有点直白，实际上哈希表主要是存储键值对，通过键的来寻找值的。

也就是如下图 KEY --- value 通过key来寻找value;

那么哈希表的优势在哪？

如果我们有100个学生，我们用数组去判断一个学生是否在这100个学生中需要O(N）去枚举每一个学生，但是如果用哈希表的话只需要O(1),我们只需要初始化把学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。

将学生姓名映射到哈希表上就涉及到了哈希函数。

什么是哈希函数

哈希函数（Hash Function）是一种将输入数据映射到固定大小值的函数。它接受任意长度的输入，并通过计算生成一个固定长度的输出，通常称为哈希值（Hash Value）或哈希码（Hash Code）。

通俗来说什么是哈希函数，就是把你输入的数据映射到哈希表上，比如上述的100个同学，尽可能的把同学映射到哈希表中，以保证当你想要去查询同学是否存在于你的哈希表中的时候，你可以通过映射的下标去访问到。

好了，我们已经基本了解哈希表的基本原理，那么当我们的学生数量远远大于哈希表的大小的时候就会出现碰撞，也就是哈希碰撞。

什么是哈希碰撞

哈希碰撞（Hash Collision）指的是两个或多个不同的输入值经过哈希函数计算后得到相同的哈希值。在哈希函数的输出范围有限的情况下，由于输入的数据量可能远远超过哈希函数的输出范围，因此哈希碰撞是不可避免的。

如下图当不同的key通过哈希函数计算后得出的结果是同一个索引就会出现哈希碰撞。

那么解决哈希碰撞的方式也有很多：

1. 开放定址法： 

所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入 。

公式为：fi(key) = (f(key)+di) MOD m (di=1,2,3,……,m-1) 

※ 用开放定址法解决冲突的做法是：当冲突发生时，使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者 碰到一个开放的地址（即该地址单元为空）为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探测到开放的地址则表明表中无待查的关键字，即查找失败。 

2. 再哈希法： 

再哈希法又叫双哈希法，有多个不同的Hash函数，当发生冲突时，使用第二个，第三个，….，等哈希函数

计算地址，直到无冲突。虽然不易发生聚集，但是增加了计算时间。

3. 链地址法： 

链地址法的基本思想是：每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来。

我们举一个非常简单的例子，我们以某个数字对5取余数的结果对数字进行分类，进而绘制一个哈希表。既然是对5取余运算，我们知道，其结果只能是有0,1,2,3,4五个数，因此分类有五种，索引也就是五种：那么这里的对5取余数就是哈希函数。所以这个哈希表有五种索引。

​ 而当传入数据：23,12,43,15,24,33,79的时候，他们首先会被分类规则运算并分类，然后存放在自己相应的类别下，如23取余操作之后，结果为3，因此将其存放在索引为3的分类下；12求余之后为2，因此将其存放在索引为2的分类下；43求余结果为3，因此将其存放在索引为3的分类下；15求余结果为0，将其存放在索引为0的分类下；24求余结果为4，将其存放在索引为4的分类下；33求余结果为3，将其存放在索引为3的分类下；79求余结果为4，将其存放在索引为4的分类下。因此整个数据在存入之后，我们便得到了一个这样的结构：

​ 当我们要查询一个数据33的时候，首先就会根据规则对33进行运算，获取到其分类索引值：3，然后我们在分类索引表中搜索到索引为3的分类，然后再在它对应的表中进行查找，这样一来，我们就缩小了查找范围，进而节省了时间，这实际上就是链地址法。

2.常见的哈希结构分析

• 数组
• set （集合）
• map(映射)

这里数组就没啥可说的了，我们来看一下set。

set

当我们要使用集合来解决哈希问题的时候，优先使用unordered_set，因为它的查询和增删效率是最优的，如果需要集合是有序的，那么就用set，如果要求不仅有序还要有重复数据的话，那么就用multiset

map

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。

在map 是一个key value 的数据结构，map中，对key是有限制，对value没有限制的，因为key的存储方式使用红黑树实现的。

3.哈希表代码示例(c++)

#include <iostream>
#include <vector>

#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12    // 定义哈希表长为数组的长度
#define NULLKEY -32768

class HashTable {
private:
    std::vector<int> elem;  // 数组元素存储基址，使用动态数组
    int count;              // 当前数据元素的个数
    int m;                  // 哈希表长度

public:
    HashTable() {
        m = HASHSIZE;
        count = m;
        elem.resize(m, NULLKEY);
    }

    // 哈希函数
    int Hash(int key) {
        return key % m;     // 除留取余法
    }

    // 将关键字插入哈希表
    void InsertHash(int key) {
        int addr = Hash(key);             // 求哈希地址
        while (elem[addr] != NULLKEY) {    // 如果不为空则冲突
            addr = (addr + 1) % m;         // 线性探测
        }
        elem[addr] = key;                  // 直到有空位后插入关键字
    }

    // 查找关键字
    bool SearchHash(int key, int& addr) {
        addr = Hash(key);                   // 求哈希地址
        while (elem[addr] != key) {          // 若不为空，则冲突
            addr = (addr + 1) % m;           // 线性探测
            if (elem[addr] == NULLKEY || addr == Hash(key)) {
                // 如果循环回到原点，则说明关键字不存在
                return false;
            }
        }
        return true;
    }
};

int main() {
    HashTable hashTable;
    hashTable.InsertHash(5);
    hashTable.InsertHash(15);
    hashTable.InsertHash(25);

    int addr;
    if (hashTable.SearchHash(15, addr)) {
        std::cout << "Key found at address: " << addr << std::endl;
    } else {
        std::cout << "Key not found." << std::endl;
    }

    return 0;
}

4.总结

1. 哈希表是一种以键值对存储数据的数据结构。它通过将键映射到数组的索引位置来实现高效的数据访问。
2. 哈希表在空间和时间上进行权衡。如果没有内存限制，可以直接将键作为数组的索引，实现常数时间的查找。如果没有时间限制，可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表在时间和空间上找到了平衡点，通过调整哈希函数算法可以在时间和空间之间做出取舍。
3. 哈希函数是哈希表的关键，它将键映射到数组的索引位置。好的哈希函数应该具有良好的分布性，尽量避免冲突，以提高哈希表的性能。
4. 哈希表的插入和查找操作的平均时间复杂度是常数级别的，即O(1)。但在最坏情况下，可能会有冲突发生，导致查找时间变为线性级别，即O(n)。
5. 哈希表可以用于解决查找、去重、缓存等问题，具有高效的查找和插入操作。

总之，哈希表是一种重要的数据结构，通过合理设计哈希函数和解决冲突的方法，可以实现高效的数据存储和检索。 

大家可以关注我的专栏分享更多的刷题技巧和知识。