谈一谈哈希表以及哈希算法

作者: ITsCLG | 来源:发表于2021-03-14 12:48 被阅读0次

一、先谈谈数组与链表

经常写代码的小伙伴应该不陌生，在编程过程中常常面临着两个问题：存储和查找，存储和查找的效率往往决定了整个程序的效率。
实际上，数据结构的存储方式只有两种：数组（顺序存储）和链表（链式存储）【一种是连续的存储结构，一种是不连续的存储结构】。
数组的随机访问性强，查找速度快（连续内存空间导致的）；但是插入和删除效率低【每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)】。但正因为连续存储，内存空间必须一次性分配够，可能浪费内存。数组大小固定，不能动态拓展。如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N)；按序号查找时，数组可以随机访问，时间复杂度为O(1)。按值查找时，若数组无序，时间复杂度为O(n)；但是当数组有序时，可以采用折半查找将时间复杂度降为O(logn)；　
链表插入删除速度快，内存利用率高，不会浪费内存。大小没有固定，拓展很灵活【每一个数据存储了下一个数据的地址，增删效率高，时间复杂度O(1)】。但是正因为存储空间不连续，不能随机查找，必须从第一个开始遍历，查找效率低，平均需要O(n)。

二、什么是哈希表

数据结构种类很多，甚至你也可以发明自己的数据结构，但是底层存储无非数组或者链表。像堆栈、队列、树、图等数据结构，数组和链表才是「结构基础」。
但是，上述这些数据结构，并不能折衷一下数组和链表的优缺点。为了满足数据的查找和修改很容易，同时又不占用很多空间，于是就有了所谓的哈希表【Hash table，散列表】，一种不同于堆栈、队列、树、图的数据结构，可以说是数组和链表的结合体吧【结合了数组的快速查询的优点又能融合链表方便快捷的增加删除元素的优势，不是指一定要同时使用到数组和链表两种存储结构】。
那究竟什么是哈希表呢？
其实所谓的哈希表，是一种根据<key—value>【也就是关键码值】进行数据访问的数据结构。乍一听挺难理解，但并不复杂。
核心思想：
1、内部是一个数组
2、关键码key经过变换(hash函数)得到int类型的值
3、int类型的值变成一个合法的下标
4、把值value放到数组这个合法的下标的位置
所以有：
记录的存储位置=hashfunction(关键字)
当向该结构中：
1、插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。
2、搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(HashTable)(或者称散列表)。
所以说，散列技术既是一种存储方法，也是一种查找方法。然而它与线性表、树、图等结构不同的是，前面几种结构，数据元素之间都存在某种逻辑关系，可以用连线图示表示出来，而散列技术的记录之间不存在什么逻辑关系，它只与关键字有关联。因此，散列主要是面向査找的存储结构。

三、哈希冲突以及负载系数

在理想的情况下，每一个关键字key，通过散列函数计算出来的地址都是不一样的，可现实中，这只是一个理想。
我们时常会碰到两个关键字key1 ≠ key2，但却有f (key1) = f (key2)，这种现象称为冲突（collision)，并把key1和 key2称为这个散列函数的同义词（synonym）。
出现了冲突当然非常糟糕，那将造成数据査找错误。尽管我们可以通过精心设计的散列函数让冲突尽可能的少，但是不能完全避免。于是如何处理冲突就成了一个很重要的课题，这在我们后面也需要详细讲解。
处理哈希冲突是个大坑……需要深入了解的东西很多。当然，小编文章后半部分会来详细解释下。
那什么又是哈希表的负载系数(Load Factor)呢？
其实，负载系数的公式是 $\alpha$ = $\frac{n}{N}$
其中N是哈希表的尺寸,n是哈希表中已存在元素个数。
（1）α<1即表中有常有可用的空间，允许我们向当前哈希表插入其他元素
（2）α=1即表中空间已经被填满,此时需要扩容
（3）α>1即n>N已经溢出，这种情况在具体的代码实现中是要避免的。
α我们也称之为装填因子。
后面两种情况，就要求我们对现在的哈希表的向操作系统申请更多的内容空间(更多存储桶)，哈希表的这种操作就叫重散列(Rehashing)。
至于什么是重散列，后续会讲到。

四、哈希表的常用构造方法

1、直接定址法

直接定址法使用下面的公式： $f(key)=a*key+b(b为常数)$
比如统计出生年份，那么就可以使用f(key)=key-1990来计算存储的位置，也就是散列地址。

出生年份人数代码如下所示：

#include <iostream>
#include <vector>
 
using namespace std;
 
 //哈希表插入的每个数据节点 
template <typename K, typename V>
class HashNode
{
    public:
    HashNode(const K& key = K(), const V& value = V())//加上K()和V()，可缺省构造
    {
        key_ = key;
        value_ = value;
    }
 
    K key_;
    V value_;
    bool initialized_ = false;
};
 
template <typename K, typename V>
class HashTable
{
    public:
    HashTable(int size)
    {
        count=0; 
        node_num_ = size;// 存储容量 
        nodes_.resize(size);//分配哈希表空间 
    }
    //直接定址法 
    int hashFunction(const K& key)
    {
        return hash(key)-1990;
    }
 
    //根据关键码查找键值 
    V find(const K& key)
    {
        int index = hashFunction(key);
        if(nodes_[index].key_ == key)
        {
            return nodes_[index].value_;
        }
   
    }
    //哈希表数据的插入 
    void insert(const K& key, const V& value)
    {
        if(whetherfull()){
            int index = hashFunction(key);
            count++;
            nodes_[index].key_ = key;
            nodes_[index].value_ = value;
            nodes_[index].initialized_ = true;
        }
        
    }
   //del()方法是删除哈希表中某个数据。该方法接收一个参数 key
    void del(const K& key)
    {
        int index = hashFunction(key);
        if(nodes_[index].initialized_)
        {
            count--;
            nodes_[index].initialized_ = false;
            cout<<"成功删除"<<endl;
        }else{
            cout<<"哈希表中无该数据"<<endl;
        }
    }
    
    int hash(const K& key)
    {
        return key;
    }
 
    bool whetherfull()
    {
        if(count<=node_num_){
            return true;
         }else{
            cout<<"表已经满了，无法继续插入数据"<<endl;
            return false;
         }
    }
private:
    vector<HashNode<K, V> > nodes_;
    int node_num_;//存储容量 
    int count;//当前存储数据数 
};
 
int main(int argc, char** argv)
{
    HashTable<int, int> table(20);
    table.insert(1991, 1281);
    table.insert(1992, 1283);
    table.insert(1993, 1834);
    cout<<table.find(1993)<<endl;
    table.del(1993);
    return 0;
}

这样的散列函数优点就是简单、均匀，也不会产生冲突【不存在f (key1) = f (key2)的情况】，但问题是这需要事先知道关键字的分布情况，适合査找表较小且连续的情况。由于这样的限制，在现实应用中，直接定址法虽然简单，但却并不常用。

2、除留余数法

除留余数法此方法为最常用的构造散列函数方法。对于散列表长为m的散列函数公式为： $f( key ) = key{\,}{\,}{\,}mod{\,}{\,} {\,}p ( p ≤ m )$
mod是取模（求余数）的意思。
很显然，本方法的关键就在于选择合适的p, p如果选得不好，就可能会容易产生同义词。下面我们来举个例子看看：

例子可以看到总共有12个记录，现在我们要针对它设计一个散列表。如果采用除留余数法，那么可以先尝试将散列函数设计为f(key) = key mod 12【tablesize即表的尺寸】的方法。比如29 mod 12 = 5，所以它存储在下标为5的位置。
最终得到的存储结果如下：

存储结果代码其实也只是改动了下上述代码的哈希函数，如下所示：

#include <iostream>
#include <vector>
 
using namespace std;
 
 //哈希表插入的每个数据节点 
template <typename K, typename V>
class HashNode
{
    public:
    HashNode(const K& key = K(), const V& value = V())//加上K()和V()，可缺省构造
    {
        key_ = key;
        value_ = value;
    }
 
    K key_;
    V value_;
    bool initialized_ = false;
};
 
template <typename K, typename V>
class HashTable
{
    public:
    HashTable(int size)
    {
        count=0; 
        node_num_ = size;// 存储容量 
        nodes_.resize(size);//分配哈希表空间 
    }
    //除留余数法 
    int hashFunction(const K& key)
    {
        return hash(key)%node_num_;
    }
 
    //根据关键码查找键值 
    V find(const K& key)
    {
        int index = hashFunction(key);
        if(nodes_[index].key_ == key)
        {
            return nodes_[index].value_;
        }
   
    }
    //哈希表数据的插入 
    void insert(const K& key, const V& value)
    {
        if(whetherfull()){
            int index = hashFunction(key);
            count++;
            nodes_[index].key_ = key;
            nodes_[index].value_ = value;
            nodes_[index].initialized_ = true;
        }
    }
   //del()方法是删除哈希表中某个数据。该方法接收一个参数 key
    void del(const K& key)
    {
        int index = hashFunction(key);
        if(nodes_[index].initialized_)
        {
            count--;
            nodes_[index].initialized_ = false;
            cout<<"成功删除"<<endl;
        }else{
            cout<<"哈希表中无该数据"<<endl;
        }
    }
    
    int hash(const K& key)
    {
        return key;
    }
 
    bool whetherfull()
    {
        if(count<=node_num_){
            return true;
         }else{
            cout<<"表已经满了，无法继续插入数据"<<endl;
            return false;
         }
    }
private:
    vector<HashNode<K, V> > nodes_;
    int node_num_;//存储容量 
    int count;//当前存储数据数 
};
 
int main(int argc, char** argv)
{
    HashTable<int, string> table(12);
    table.insert(12, "乔丹");
    table.insert(25, "魔术师");
    //table.insert(1993, 1834);
    cout<<table.find(12)<<endl;
    //table.del(1993);
    return 0;
}

上述给的例子过于简单且没有出现冲突的情况，一旦出现冲突，小编上面的代码可就不对劲了。因为这种求余数作为下标的出现冲突的机率还是常有的，我举个极端的例子，如下所示：

极端例子可以发现，按照f(key) = key mod 12去计算，最终的f(key)都相等且为0。
但是我们如果不选用p=12来做除留余数法，而选用p=11，大家计算下可以发现冲突减少了，只有两个冲突。所以合理选取p值也能一定程度减少冲突。
至于解决冲突有哪些方法，代码该怎么补充修改，小编接下来也会讲到的。

3、数字分析法

数字分析法通常适合处理关键字位数比较大的情况，例如我们现在要存储某家公司员工登记表，如用手机号作为关键字，那么我们发现抽样后面的四位数字作为散列地址是不错的选择。
我们来看个例子，看看使用哈希表怎么来进行存储，如下图所示：

联系薄散列函数我们可以这样子去设计：

f(key)=atoi(key+7)(这里的key为字符串)

假设key="15625063012"，那么f(key)=atoi(key+7)=3012。
atoi这个函数这里小编就不详细解释了。
具体代码这里不再展示，只是更改下上述代码的哈希函数而已。
除了上述介绍的三种哈希表的构造方法之外，还有：

4、平方取中法

取关键字平方之后的中间极为作为哈希地址，一个数平方之后中间几位数字与数的每一位都相关，取得位数由表长决定。比如：表长为512,=2^9,可以取平方之后中间9位二进制数作为哈希地址。一个简单的小例子：

平方取中法

5、折叠法

关键字位数很多，而且关键字中每一位上的数字分布大致均匀的时候，把关键词分割成位数相同的几个部分，然后叠加。

折叠法

五、哈希表的冲突解决算法

hash冲突是不可能完全避免的，那么我们要考虑的还有就是当产生哈希冲突的时候，我们如何来解决。比较常见的hash冲突的解决方法有：开放定址法、链地址法。
接下来，小编就来聊一聊这两种冲突的解决办法。

1、开放定址法

其实，开放地址法很好理解。它的实现是在插入一个元素的时候，先通过哈希函数进行判断，若是发生哈希冲突，就以当前地址为基准，根据再寻址的方法（探查序列），去寻找下一个地址，若发生冲突再去寻找，直至找到一个为空的地址为止，再将数值填充进去。所以这种方法又称为再散列法。
公式为： $fi(key) = (f(key)+di){\,}{\,}{\,} mod {\,}{\,}{\,}tablesize(1<=di<tablesize-1)$ 其实，开放地址法包括三小种分别是 线性探测、平方探测、双散列。下面依次介绍各种方法。

1.1线性探测法

线性探测法的地址增量d_i = 1, 2, ... , tablesize-1，其中，i为探测次数。该方法一次探测下一个地址，知道有空的地址后插入，若整个空间都找不到空余的地址，则产生溢出。
举个例子，现在我们的关键字集合如下：

关键字集合可以发现表长为12。我们用散列函数f(key) = key mod 12。
当计算前5个数{12,67,56,16,25}时，都是没有冲突的散列地址，直接存入，得到：

无冲突情况出现前计算key = 37时，发现f(37) = 1，此时就与25所在的位置冲突。
于是我们应用上面的公式f₁(37) = (f(37)+1) mod 12 = 2。于是将37存入下标为2的位置。这其实就是房子被人买了于是买下一间的作法：

存入37 接下来22,29,15,47都没有冲突，正常的存入：

image.png 到了 key=48，我们计算得到f(48) = 0，与12所在的0位置冲突了，不要紧，我们f₁(48) = (f(48)+1) mod 12 = 1，此时又与25所在的位置冲突。于是f₂(48) = (f(48)+2) mod 12=2，还是冲突……一直到 f₆(48) = (f(48)+6) mod 12 = 6时，才有空位，机不可失，赶快存入：

多次探测到了 key=34，我们计算得到f(34) = 10，与22所在的10位置冲突了，不要紧，我们f₁(34) = (f(34)+1) mod 12 = 11，此时又与47所在的位置冲突。于是f₂(34) = (f(34)+2) mod 12=0，还是冲突……一直到 f₁₁(34) = (f(34)+11) mod 12 = 9时，才有空位，存入：

最终哈希结果

我们把这种解决冲突的开放定址法称为线性探测。
可以发现，我们探测了多少次，d_i的最终值就为多少，是一个公差为1的递增序列。
所以呢，在插入、查找、删除数据的时候，代码要进一步的修改，代码设计如下：

#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;
 
 //哈希表插入的每个数据节点 
template <typename K, typename V>
class HashNode
{
    public:
    HashNode(const K& key = K(), const V& value = V())//加上K()和V()，可缺省构造
    {
        key_ = key;
        value_ = value;
    }
 
    K key_;
    V value_;
    int collision=0; //冲突次数 
    bool initialized_ = false;
};
 
template <typename K, typename V>
class HashTable
{
    public:
    HashTable(int size)
    {
        count=0; 
        node_num_ = size;// 存储容量 
        nodes_.resize(size);//分配哈希表空间 
    }
    //除留余数法 
    int hashFunction(const K& key)
    { 
        return hash(key)%node_num_;
    }
 
    //根据关键码查找键值 
    V find(const K& key)
    {
        int index = hashFunction(key);
        int countnum=0;
        while(nodes_[index].initialized_)//判断该位置是否有值 
        {
            if(countnum>=node_num_){
                string s="哈希表中无该数据";
                return s;
            }
            if(nodes_[index].key_==key)//判断该位置的值的关键字是否相等 
            {
                return nodes_[index].value_;
            }
            index++;
            countnum++;
            index=index%node_num_;
        }
    
   
    }
    //哈希表数据的插入 
    void insert(const K& key, const V& value)
    {
        if(!whetherfull()){
            return;
        }
        int index = hashFunction(key);
        int collision=0;
        count++;
        //线性探测 
        //发生冲突，寻找下一个位置存放 
        while(nodes_[index].initialized_)
        {
            collision++;
            index++;
            if(index == node_num_)
            {
                index = 0;
            }
        }
        nodes_[index].key_ = key;
        nodes_[index].value_ = value;
        nodes_[index].initialized_ = true;
        nodes_[index].collision=collision;
    }
   //del()方法是删除哈希表中某个数据。该方法接收一个参数 key
    void del(const K& key)
    {
        int index = hashFunction(key);
        int countnum=0;
        while(nodes_[index].initialized_ )
        {
            if(countnum-node_num_>=12)
            {
                cout<<"哈希表中无该数据"<<endl;
                return ;
            }
            if(nodes_[index].key==key)
            {
                count--;
                nodes_[index].initialized_ = false;
                cout<<"成功删除"<<endl;
                return ;
            }
            index++;
            index=index%node_num_;
        }
        
    }
    
    int hash(const K& key)
    {
        return key;
    }
    
   void PrintHashTable()
    {
        for (int i = 0; i<node_num_; i++) 
        {
            if(nodes_[i].initialized_){
                cout<<"key: "<<nodes_[i].key_<<"--value: " <<nodes_[i].value_<<endl;    
            }else{
                cout<<"key: [ ]--value: [ ]" <<endl;
            }
            
        }
    }
    bool whetherfull()
    {
        if(count<=node_num_){
            return true;
         }else{
            cout<<"表已经满了，无法继续插入数据"<<endl;
            return false;
         }
    }
    
private:
    vector<HashNode<K, V> > nodes_;
    int node_num_;//存储容量 
    int count;//当前存储数据数 
};
 
int main(int argc, char** argv)
{
    HashTable<int, string> table(12);
    table.insert(12, "乔丹");
    table.insert(67, "科比");
    table.insert(56, "魔术师");
    table.insert(16, "库里");
    table.insert(25, "詹姆斯");
    table.insert(37, "邓肯");
    table.insert(22, "格林");
    table.insert(29, "杜兰特");
    table.insert(15, "奥尼尔");
    table.insert(47, "姚明");
    table.insert(48, "卡特");
    table.insert(34, "欧文");
    //table.insert(1993, 1834);
    //cout<<table.find(12)<<endl;
    cout<<table.find(64)<<endl;
    table.PrintHashTable();
    return 0;
}

我们还是看刚才那个例子，可以发现我们在解决冲突的时候，为了处理冲突就会占用下一个位置，而如果冲突较多时，就会出现数据都聚集在一块区域。例如48和37这种本来都不是同义词却需要争夺一个地址的情况，我们称这种现象为堆积【如果冲突较多时，就会出现数据都聚集在一块区域】。很显然，堆积的出现，使得我们需要不断处理冲突，无论是存入还是査找效率都会大大降低。

1.2平方探测法

看例子

我们看我们上述的例子，可以发现当最后一个key=34，f(key)=10,与22所在的位置冲突，可是22后面没有空位置了，反而它的前面有一个空位置，尽管可以不断地求余数后得到结果，但效率很差【从后到前】。
因此我们可以改进d_i = 1², -1², 2², -2²,……, q², -q² (q <= tablesize/2),这样就等于是可以双向寻找到可能的空位置。
我们还是用上述的例子来进行阐述。关键字集合如下：

关键字集合可以发现表长为12。我们用散列函数f(key) = key mod 12。
当计算前5个数{12,67,56,16,25}时，都是没有冲突的散列地址，直接存入，得到：

无冲突情况出现前计算key = 37时，发现f(37) = 1，此时就与25所在的位置冲突。于是我们重新寻找位置，有f₁(37)=（f(37)+1²）mod 12=2【第一次冲突i=1，d_i=1²】,于是将37存入下标为2的位置。

存入37 接下来22,29,15,47都没有冲突，正常的存入：

image.png 到了 key=48，我们计算得到f(48) = 0，与12所在的0位置冲突了。计算，有f₁(48)=（f(48)+1²）mod 12=1，该位置已有数据，继续寻找下一个位置；f₂(48)=（f(48)-1²）mod 12=11，该位置已经有数据，继续寻找下一个位置；f₃(48)=（f(48)+2²）mod 12=4，该位置已经有数据，继续寻找下一个位置；f₄(48)=（f(48)-2²）mod 12=8，该位置已经有数据，继续寻找下一个位置；f₅(48)=（f(48)+3²）mod 12=9，该位置无数据，插入。

插入key=48 到了 key=34，我们计算得到f(34) = 10，与22所在的10位置冲突了，不要紧，继续寻找空位置，有f₁(34)=(f(34)+1²) mod 12=11，该位置已有数据，继续寻找空位置；f₂(34)=(f(34)-1²) mod 12=9，该位置已有数据，继续寻找空位置；有f₃(34)=(f(34)+2²) mod 12=2，该位置已有数据，继续寻找空位置；有f₄(34)=(f(34)-2²) mod 12=6，该位置无数据，插入。

最终结果其实，增加平方运算的目的是为了不让关键字都聚集在某一块区域，形成堆积，我们称这种方法为平方探测法（也叫二次探测法）。

代码设计关键点之一

下面，我们来分析下代码设计中比较关键的地方。举个例子，(-1) mod 12的余数正常为11，但是如果在C++编译器中，这么去计算负数除以某个正整数的余数，如下代码所示：

#include<iostream>
using namespace std;

int main()
{
    int a=-1;
    int c=a%12; 
    cout<<c<<endl;
    return 0;
 }

程序运行后，发现输出的结果为-1。这明显不太对，因此我们需要做点小改进，有两种方法。

#include<iostream>
using namespace std;

int main()
{
    int a;//负整数 
    int b; //正整数 
    int c;
    cin>>a>>b; 
    //第一种写法 
    if(a%b<0){
        c=a%b+b;
    }else{
        c=a%b;
    } 
    //第二种 写法 
    //c=（a%b+b)%b
    cout<<c<<endl;
    return 0;
 }

上述解决方法真的对吗

上述问题是非常关键的，如果没采取这种分类求余数方法，得到的结果还发生错误，导致地址探测出现问题。
但是，如果我们用上述表长为12的哈希表去存储其他数据，有可能会出现一些问题【一般情况下我们是把表长设置为质数/素数的】，接着往下看。
对于线性探测，让散列表近乎填满元素是个坏主意，因为此时表的性能会降低。对于平方探测，情况更糟：一旦表被填满超过一半，若表的大小不是素数，那么甚至在表被填满一半之前，就不能保证找到空的单元了。这是因为最多只有表的一半可以用做解决冲突的备选位置。
这又是为什么，小编简单做个证明如下：
证明：
令表的大小tablesize是一个大于3的素数（质数)，我们证明，前[tablesize / 2]个备选位置是互异的。
可以得知(f(x)+i²) mod tablesize 和(f(x)+j²) mod tablesize 是这些位置中的两个，其中0 < i, j <= [tablesize / 2]。为推出矛盾，假设这两个位置相同，但i != j，于是:
1) f(x) + i^2 ^= f(x) + j² (mod tablesize)
2) i² - j² = 0
3) (i + j)(i - j) = 0
所以i = -j或者i = j，因为i != j，且i,j都大于0,所以前[tablesize / 2]个备选位置是互异的。
由于要被插入的元素，若无任何冲突发生，也可以放到经散列得到的单元，因此任何元素都有[tablesize / 2]个可能被放到的位置，如果最多有[tablesize / 2]个位置可以使用，那么空单元总能够找到。哪怕表有比一半多一个的位置被填满，那么插入都有可能失败。表的大小是素数也非常重要，如果表的大小不是素数，则备选单元的个数也可能锐减。
开放定址散列表中，标准的删除操作不能实行。因为相应的单元可能已经引起过冲突，元素绕过了它存在了别处。因此，开放定址散列表需要懒惰删除。
定理1：如果使用平方探测，且表的大小是素数，那么当表至少有一半是空的时候，总能够插入一个新的元素。
接下来，我们来举一个简单的例子。
将4个关键字分别为10,6,4,15的元素插入到大小为5的散列表中。
hash函数f(x)=key mod 5。
插入key=5时，f(10)=10 mod 5=0，插入，有：

插入key=10 插入key=6时，f(6)=6 mod 5=1，插入，有：

插入key=6 插入key=4时，f(4)=4 mod 5=4，插入，有：

插入key=4
插入key=15时，f(15)=15 mod 5=0，发生冲突，探测下一个地址，有：f₁(15)=(f(15)+1²) mod 5=1，该位置已有数据继续冲突，继续探寻下一个地址；f₂(15)=(f(15)-1²) mod 5=4，该位置已有数据发生冲突，继续探测下一个可用地址，有f₃(x)=(f(15)+2²) mod 5 =4,该位置已有数据发生冲突，继续探测下一个可用地址，有f₄(x)=(f(15)-2²) mod 5 =1，该位置已有数据发生冲突。进行下一次探测时，q=3>tablesize/2【5/2】，因此探测结束。
可以发现此时key=15这个元素使用平方探测法无法插入哈希表，但此时表中还有空位置。
定理2：哈希表的长度为4k+3（k为整数）形式的素数，平方探测法可以探测到整个哈希表空间。
了解完对应的知识后，我们可以来对代码做下改进，如下：

#include <iostream>
#include <vector>
#include <stdlib.h>
#include <math.h>
#include <cmath> 
using namespace std;
 
 //哈希表插入的每个数据节点 
template <typename K, typename V>
class HashNode
{
    public:
    HashNode(const K& key = K(), const V& value = V())//加上K()和V()，可缺省构造
    {
        key_ = key;
        value_ = value;
    }
 
    K key_;
    V value_;
    int collision=0; //冲突次数 
    bool initialized_ = false;
};
 
template <typename K, typename V>
class HashTable
{
    public:
    HashTable(int size)
    { 
        count=0; 
        collision=0; 
        tablesize = nextPrime(size);// 存储容量 
        nodes_.resize(tablesize);//分配哈希表空间 
    }
    //找到下一个质数 
    int nextPrime(int n)
    {
        while(!isprime(n) ){
            n++;
        }
        return n;

    }
    //判断是否质数 
    bool isprime(int x)
    {
        //判断质数
        if(x==0||x==1){
            return false;
        }
        for(int i=2;i<=(int)sqrt(x)+1;i++)
        {
            if(x%i==0){
                return false;
            }
        }
        return true;
    }

    //除留余数法 
    int hashFunction(const K& key)
    { 
        return key%tablesize;
    }
    
     //找到空位置
    int findpos(const K& key) 
    {
        int index = hashFunction(key);
        int indextemp=index;
        int i=0,j=1; 
        collision=0;
        //发生冲突，寻找下一个位置存放 【平方探测】 
        while(nodes_[index].initialized_ )//判断该位置是否有值 
        {
            if(nodes_[index].key_==key){
                return index; 
            }
            if(j>tablesize/2){
                return tablesize;
            }
            collision++;
            index=indextemp+pow(-1,i)*pow(j,2);//按照增量序列进行设计 
            if(hashFunction(index)<0){
                index=hashFunction(index)+tablesize;
            }else{
                index=hashFunction(index);
            }
            i++;
            if(i%2){
                j++;
            }
        }
        return index;
    }
    
    //根据关键码查找键值 
    V find(const K& key)
    {
       int index=findpos(key);
       if(nodes_[index].initialized_){
            return nodes_[index].value_;
       }else{
            cout<<"查找不到"<<endl;
       }
    
    }
    
    //哈希表数据的插入 
    void insert(const K& key, const V& value)
    {
        int index = findpos(key);
        if(nodes_[index].initialized_){
            cout<<"键值重复，无法插入"<<endl;
            return;
        }
        if(index==tablesize){
            cout<<"增量已经大于tablesize/2，无法插入"<<endl;
            return;
        }
        nodes_[index].key_ = key;
        nodes_[index].value_ = value;
        nodes_[index].initialized_ = true;
        nodes_[index].collision=collision;
        count++; 
    }
   //del()方法是删除哈希表中某个数据。该方法接收一个参数 key
    void del(const K& key)
    {
        int index = findpos(key);
        if(nodes_[index].initialized_){
            nodes_[index].initialized_ = false;
        }else{
            cout<<"表中没有该数据"<<endl;
            return ;
        }
        
    }
    
    void PrintHashTable()
    {
        for (int i = 0; i<tablesize; i++) 
        {
            if(nodes_[i].initialized_){
                cout<<"key: "<<nodes_[i].key_<<"--value: " <<nodes_[i].value_<<endl;    
            }else{
                cout<<"key: [ ]--value: [ ]" <<endl;
            }
            
        }
    }
    
private:
    vector<HashNode<K, V> > nodes_;
    int tablesize;//存储容量 
    int count;//当前存储数据数 
    int collision;//临时存储冲突次数 
};
 
int main(int argc, char** argv)
{
    HashTable<int, string> table(4);
    table.insert(10, "乔丹");
    table.insert(6, "科比");
    table.insert(4, "魔术师");
    table.insert(15, "库里");
    /*table.insert(25, "詹姆斯");
    table.insert(37, "邓肯");
    table.insert(22, "格林");
    table.insert(29, "杜兰特");
    table.insert(15, "奥尼尔");
    table.insert(47, "姚明");
    table.insert(48, "卡特");
    table.insert(34, "欧文");
    //table.insert(1993, 1834);*/
    //table.del(10);
    //cout<<table.find(15)<<endl;
    //table.rehash();
    table.PrintHashTable();
    return 0;
}

上述代码后续小编会进行适当优化。

表空间不够怎么办

对于使用平方探测法的闭散列里，如果元素填的太满的话后续插入将耗费过长的时间，甚至可能insert失败，因为这里面会有太多的移动和插入混合操作。怎么办呢？一种解决方法是建立另外一个大约两倍大的表，再用一个新的散列函数，扫描整个原始表然后按照新的映射插入到新的表里。上述有说过，这种操作叫做重散列【再散列】。
我们举一个最简单的例子，有一个长度为3的哈希表，现在需要插入的键值对是(6,"Mosa")，(7,"Kally")，(8"Berry")，且哈系表的散列函数是 hash(k)=k mod N,当前N=3。
这三个键值对插入表后的状态，如下图，当前N=3，n=3,那么α=1，此时，就需要执行重散列的操作,以满足后续插入元素有可用的存储桶可用。

哈希表已满
那问题来了，究竟需要扩容至多大的尺寸才适合呢？首先实现哈希表的底层基本数据结构就是顺序表，更贴切地说是数组,按照惯例就是新的内存空间是原来内存空间的2倍。
这样的话，扩容后的尺寸不就是N=2x3=6吗？但是，我们前面刚分析过，若N是非素数的话，那么多个不同的键值对出现散列冲突的概率会比使用素数高出许多，也就是说新哈希表的尺寸N不可能是2的倍数。
因此更准确地说，重散列的最终效果就是为哈希列表扩容提供更多的可用的存储位置，我们扩容后的哈希表尺寸可以靠近2N附近的素数。在本例来说,因为2N=2x3=6，那么6附近的素数可以是5和7,或者远点11,13都可以，当然按照我们这里的约定，当然7是完美的选择。

扩容但这里的事情还没完，重散列的第二个步骤就是将旧表的元素迁移到新表中，迁移过程中就需要对就旧表的每个元素的键传入hash(key)重新散列一遍，此时散列函数中的N是新表的尺寸即N=7，这也是重散列的关键操作,下图已经展示的很清楚。

旧表迁移上述的例子是在表满了【插入失败时再进行重散列】，其实，具体实现可以用平方探测以很多种方式实现，包括：
（1）只要表有一半满了就做
（2）只有当插入失败时才做（这种比较极端）
（3）途中策略：当表到达某个装填因子时再做
随着装填因子的增加，表的性能会有所下降，所以第三个方法或许是最好的。
接下来贴上改进的代码，如下：

#include <iostream>
#include <vector>
#include <stdlib.h>
#include <math.h>
#include <cmath> 
using namespace std;
 
 //哈希表插入的每个数据节点 
template <typename K, typename V>
class HashNode
{
    public:
    HashNode(const K& key = K(), const V& value = V())//加上K()和V()，可缺省构造
    {
        key_ = key;
        value_ = value;
    }
 
    K key_;
    V value_;
    int collision=0; //冲突次数 
    bool initialized_ = false;
};
 
template <typename K, typename V>
class HashTable
{
    public:
    HashTable(int size)
    { 
        count=0; 
        collision=0; 
        tablesize = nextPrime(size);// 存储容量 
        nodes_.resize(tablesize);//分配哈希表空间 
    }
    //找到下一个质数 
    int nextPrime(int n)
    {
        while(!isprime(n) ){
            n++;
        }
        return n;

    }
    //判断是否质数 
    bool isprime(int x)
    {
        //判断质数
        if(x==0||x==1){
            return false;
        }
        for(int i=2;i<=(int)sqrt(x)+1;i++)
        {
            if(x%i==0){
                return false;
            }
        }
        return true;
    }

    //除留余数法 
    int hashFunction(const K& key)
    { 
        return key%tablesize;
    }
    
     //找到空位置
    int findpos(const K& key) 
    {
        int index = hashFunction(key);
        int indextemp=index;
        int i=0,j=1; 
        collision=0;
        //发生冲突，寻找下一个位置存放 【平方探测】 
        while(nodes_[index].initialized_ )//判断该位置是否有值 
        {
            if(nodes_[index].key_==key){
                return index; 
            }
            collision++;
            index=indextemp+pow(-1,i)*pow(j,2);//按照增量序列进行设计 
            if(hashFunction(index)<0){
                index=hashFunction(index)+tablesize;
            }else{
                index=hashFunction(index);
            }
            i++;
            if(i%2){
                j++;
            }
        }
        return index;
    }
    
    //根据关键码查找键值 
    V find(const K& key)
    {
       int index=findpos(key);
       if(nodes_[index].initialized_){
            return nodes_[index].value_;
       }else{
            cout<<"查找不到"<<endl;
       }
    
    }
    
    //哈希表数据的插入 
    void insert(const K& key, const V& value)
    {
        int index = findpos(key);
        if(nodes_[index].initialized_){
            cout<<"键值重复，无法插入"<<endl;
            return;
        }
        nodes_[index].key_ = key;
        nodes_[index].value_ = value;
        nodes_[index].initialized_ = true;
        nodes_[index].collision=collision;
        count++; 
        if(count>tablesize/2)
        {
            rehash();
        }
    }
   //del()方法是删除哈希表中某个数据。该方法接收一个参数 key
    void del(const K& key)
    {
        int index = findpos(key);
        if(nodes_[index].initialized_){
            nodes_[index].initialized_ = false;
        }else{
            cout<<"表中没有该数据"<<endl;
            return ;
        }
        
    }
    
    //重散列 
    void rehash()
    {
        int oldTableSize = tablesize;
        count=0;
        vector<HashNode<K, V> > oldnodes_;
        oldnodes_.assign(nodes_.begin(), nodes_.end());
        tablesize=nextPrime(2*oldTableSize);
        nodes_.clear();
        nodes_.resize(tablesize);//分配哈希表空间 
        for( int i=0; i<oldTableSize; i++ )
        {
            if(oldnodes_[i].initialized_)
            {
                insert(oldnodes_[i].key_,oldnodes_[i].value_);
            }       
        }
        oldnodes_.clear();
    }
    
    void PrintHashTable()
    {
        for (int i = 0; i<tablesize; i++) 
        {
            if(nodes_[i].initialized_){
                cout<<"key: "<<nodes_[i].key_<<"--value: " <<nodes_[i].value_<<endl;    
            }else{
                cout<<"key: [ ]--value: [ ]" <<endl;
            }
            
        }
    }
    
private:
    vector<HashNode<K, V> > nodes_;
    int tablesize;//存储容量 
    int count;//当前存储数据数 
    int collision;//临时存储冲突次数 
};
 
int main(int argc, char** argv)
{
    HashTable<int, string> table(4);
    table.insert(10, "乔丹");
    table.insert(6, "科比");
    table.insert(4, "魔术师");
    table.insert(15, "库里");
    /*table.insert(25, "詹姆斯");
    table.insert(37, "邓肯");
    table.insert(22, "格林");
    table.insert(29, "杜兰特");
    table.insert(15, "奥尼尔");
    table.insert(47, "姚明");
    table.insert(48, "卡特");
    table.insert(34, "欧文");
    //table.insert(1993, 1834);*/
    //table.del(10);
    cout<<table.find(15)<<endl;
    //table.rehash();
    table.PrintHashTable();
    return 0;
}

重散列是一种非常昂贵的操作；其运行时间为O(N)，因为有N个元素要再散列而且表的大小约为2N，不过这并不经常发生，所以实际效果并没有这么差。本程序中只要表满到一半就再散列。

1.3 双散列

双重散列是线性开型寻址散列（开放寻址法）中的冲突解决技术。双重散列使用在发生冲突时将第二个散列函数应用于键。
此算法使用：(hash1(key) + i * hash2(key)) % tablesize
hash1() 和 hash2() 是哈希函数，而 tablesize 是哈希表的大小。当发生碰撞时，我们通过重复增加步长i 来寻找键。
第一个hash函数：hash1(key) = key ％ tablesize。
第二个hash函数是：hash2(key) = PRIME – (key ％ PRIME)，其中 PRIME 是小于tablesize的质数。
当然，第二个Hash函数表现好的特征包括：
（1）不会产生 0 索引
（2）能在整个HashTable 循环探测
（3）计算会快点
（4）与第一个Hash函数互相独立
（5）PRIME 与 tablesize 是相对质数
hash2( key )作为关键，必须要合理选取，否则会引起灾难性的后果——各种撞车。这个策略暂时不做过多分析了。所以小编也不做解释了。

2、链地址法

前面我们谈到了散列冲突处理的开放定址法，它的思路就是一旦发生了冲突，就去寻找下一个空的散列地址，这其实是一种治标不治本的冲突解决方法。那么，我们其实可以利用链表这一数据结构，把同一位置的冲突对象组织在一起，不就解决问题了吗？哈哈，这种冲突解决方法就叫做链地址法。
将所有关键字为同义词的记录存储在一个单链表中，我们称这种表为同义词子表，在散列表中只存储所有同义词子表的头指针。

举个简单的例子：

对于关键字集合{12,67,56,16,25,37, 22,29,15,47,48,34}，我们用前面同样的12为除数，进行除留余数法。得到的最终结果如下：

哈希结果

此时，已经不存在什么冲突换址的问题，无论有多少个冲突，都只是在当前位置给单链表增加结点的问题，很不错的解决思路吧！

链地址法概述

（1）一开始开辟一个tablesize的空间的数组；
（2）将要存储的对象转换成整数，用tablesize取模，结果会对应到数组中的一个索引；如果发生哈希冲突，取模的结果会指向数组中同一个索引；
（3）将产生哈希冲突的对象链入其对应索引挂接的对象的后面，形成一条链表；
（4）数组中的每个索引后都挂有一条链表，这就是所谓的链地址法（Separate Chain）
注意下，在拉链法中，装填因子α可以大于 1，但一般均取α≤1。

链地址法的优势与缺点

与开放定址法相比，拉链法有如下几个优点：
（1）链地址法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
（2）由于链地址法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
（3）开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而链地址法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
（4）在用链地址法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元（即开放地址）都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。
链地址法的缺点：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。
至于什么是平均查找长度，后续做个简单补充。

贴上代码

#include <iostream>
#include <vector>
#include <stdlib.h>
#include <math.h>
#include <cmath> 
using namespace std;
 
 //哈希表插入的每个数据节点 
template <typename K, typename V>
class HashNode
{
    public:
    HashNode(const K& key = K(), const V& value = V())//加上K()和V()，可缺省构造
    {
        key_ = key;
        value_ = value;
    }
    K key_;
    V value_;
    int collision=0; //冲突次数 
    bool initialized_ = false;
    HashNode<K,V>* NextNode=NULL;
};
 
template <typename K, typename V>
class HashTable
{
    public:
    typedef HashNode<K, V> hashnode;
    HashTable(int size)
    { 
        count=0; 
        collision=0; 
        tablesize = nextPrime(size);// 存储容量 
        nodes_.resize(tablesize);//分配哈希表空间 
    }
    //找到下一个质数 
    int nextPrime(int n)
    {
        while(!isprime(n) ){
            n++;
        }
        return n;

    }
    //判断是否质数 
    bool isprime(int x)
    {
        //判断质数
        if(x==0||x==1){
            return false;
        }
        for(int i=2;i<=(int)sqrt(x)+1;i++)
        {
            if(x%i==0){
                return false;
            }
        }
        return true;
    }

    //除留余数法 
    int hashFunction(const K& key)
    { 
        return key%tablesize;
    }
    
    
    //根据关键码查找键值 
    hashnode* find(const K& key)
    {
        int index =  hashFunction(key);
        hashnode* p=nodes_[index].NextNode;
        collision=0;
        temp=NULL;
        while (p && key != p->key_)
        {
            collision++;
            temp=p;
            p = p->NextNode;
        }
        return p;
    }
    
    //哈希表数据的插入 
    bool insert(const K& key, const V& value)
    {
        hashnode* p = find(key);
        if (!p)
        {
            //关键词未找到，可以插入
            hashnode* new_cell = new hashnode();
            new_cell->key_ = key;
            new_cell->value_ = value;
            new_cell->collision=collision;
            int pos = hashFunction(key);
            new_cell->NextNode = nodes_[pos].NextNode;
            nodes_[pos].NextNode = new_cell;
            return true;
        }
        else
        {
            cout << "键值已存在！" << endl;
            return false;
        }
                
    }
   //del()方法是删除哈希表中某个数据。该方法接收一个参数 key
    void del(const K& key)
    {
        hashnode* p = find(key);
        if(!p)
        {
            cout<<"无该数据"<<endl;
            return ;
        }
        int pos=hashFunction(key);
        if(!temp)
        {
            nodes_[pos].NextNode=p->NextNode;
        }else{
            temp->NextNode=p->NextNode;
        }
        cout<<"成功删除"<<endl;
        delete p;
        return;
    }
    
    void PrintHashTable()
    {
        hashnode* p;
        for (int i = 0; i <tablesize; i++)
        {
            p = nodes_[i].NextNode;
            if(!p)
            {
                cout<<"key: [ ]--value: [ ]" <<endl;
            }else{
                while (p)
                {
                    cout<<"key: "<<p->key_<<"--value: " <<p->value_<<"冲突次数："<<p->collision<<"  ";
                    p = p->NextNode;
                }
                cout<<endl;
            }
        }
    }
    
private:
    vector<HashNode<K, V> > nodes_;
    hashnode* temp;//用于存储查找关键字在链表里的前一个数据地址 
    int tablesize;//存储容量 
    int count;//当前存储数据数 
    int collision;//临时存储冲突次数 
};
 
int main(int argc, char** argv)
{
    HashTable<int, string> table(4);
    table.insert(10, "乔丹");
    table.insert(6, "科比");
    table.insert(4, "魔术师");
    table.insert(15, "库里");
    /*table.insert(25, "詹姆斯");
    table.insert(37, "邓肯");
    table.insert(22, "格林");
    table.insert(29, "杜兰特");
    table.insert(15, "奥尼尔");
    table.insert(47, "姚明");
    table.insert(48, "卡特");
    table.insert(34, "欧文");
    //table.insert(1993, 1834);*/
   // table.del(10);
    //cout<<table.find(15)<<endl;
    //table.rehash();
    table.PrintHashTable();
    return 0;
}

PS：代码虽然跑的起来，但小编水平有限可能也有需要改正的地方哈！

六、哈希表的查找性能

我们使用平均查找长度（ASL）来度量查找表的查找效率：成功、不成功。
这里，我们通过一个简单例子了解下。
关键字序列：{7、8、30、11、18、9、14}
散列函数： H(Key) = (key x 3) MOD 7
装载因子： 0.7
处理冲突：线性探测再散列法

1、查找成功的ASL计算方法：

因为现在的数据是7个，填充因子是0.7。所以数组大小=7/0.7=10，即写出来的散列表大小为10，下标从0~9。
第一个元素7，带入散列函数，计算得0。
第二个元素8，带入散列函数，计算得3。
第三个元素30，带入散列函数，计算得6。
第四个元素11，带入散列函数，计算得5。
第五个元素18，带入散列函数，计算得5；和11冲突，使用线性探测法，得7。
第六个元素9，带入散列函数，计算得6；和30冲突，使用线性探测法，得8。
第七个元素14，带入散列函数，计算得0；和7冲突，使用线性探测法，得1。
所以散列表如下：

哈希结果

这里的冲突次数计算不再重复，所谓的查找次数就是冲突次数加上1。
成功平均查找长度(ASLs)=（1+2+1+1+1+3+3）/ 7=12/ 7

2、查找不成功的ASL计算方法：

（1）定义什么叫查找不成功
查找不成功时呢？什么是查找不成功呢？查找不成功就是从查找位置开始直到一个位置为空需要比较的次数。
举个例子来说吧。在已知上面散列表的基础上，如果要查找key为4的关键字。根据散列函数可以计算Hash(key)=Hash(4)=5。此时在地址为5的地方取出那个数字，发现key=11，不等于4。这就说明在装填的时候会发生冲突。根据冲突处理方法，会继续检测地址为6的值，发现key=30，依然不等。这个时候到了地址为9，但是依然没有找到。那么就说明根本就没有key=4这个关键字，说明本次查找不成功，总共查找了5次。
再举一个例子。查找key为0的关键字，根据散列函数Hash(key)=Hash(0)=0。此时在地址为0的地方取出那个数字，发现key=7，不等于0。这就说明在装填的时候会发生冲突。根据冲突处理方法，会继续检测地址为1的值，发现key=14，依然不等。这个时候到了地址为2，发现为空，依然没有找到。所以停止查找，本次查找不成功。因为如果key=0这个关键字存在的话，依照冲突处理函数，就一定能找到它。总不能丢了吧。故其查找次数为3。
这里要注意下，当前哈希表线性探测地址时，最多会将整个表遍历一遍，查找失败则是遇到了空的地址。
第二个难点，位置7、8、9要不要考虑呢？答案是不需要。一个解释方式是通过哈希函数来解释，哪个数字经过哈希函数的映射之后能映射到7、8或者9？即哪个数字对7取模之后能得到7、8或者9？这个数字是不存在的，也就是说根本就不存在能够通过哈希函数映射到7、8或者9的元素，也就不会有查找失败了。这也是为什么ASL的分母是7的原因：要查找的所有元素的哈希函数映射都在0~6内。那为什么7、8或者9中存在元素呢？被前面的数字“推过来”的呗。所以，7、8或者9计入从其他位置开始的比较次数（分子），但是不从自身开始计算比较次数，也不计入分母。分母是模长。
（2）根据第一点定义的不成功，依次推下去：
查找地址为0的值所需要的次数为3；
查找地址为1的值所需要的次数为2；
查找地址为2的值所需要的次数为1；
查找地址为3的值所需要的次数为2；
查找地址为4的值所需要的次数为1；
查找地址为5的值所需要的次数为5；
查找地址为6的值所需要的次数为4
（3）计算
查找不成功ASLu=（3+2+1+2+1+5+4）/ 7=18/ 7
对于其他冲突解决办法，大抵上也是这么来计算的，比如链地址法就是下一个位置为null就代表查不到，其他的小编就不讲了。

七、写在最后

啰里啰唆写了一大堆，也算是总结了下知识吧。当然，也存在或多或少的错误，还得请小伙伴们多多指正。
写完这篇，算是真真正正在简书写了10万以上的杂记了。想想为什么能够坚持有空写写点东西呢，想来也是一种兴趣。

谈一谈哈希表以及哈希算法

一、先谈谈数组与链表

二、什么是哈希表

三、哈希冲突以及负载系数

四、哈希表的常用构造方法

1、直接定址法

2、除留余数法

3、数字分析法

4、平方取中法

5、折叠法

五、哈希表的冲突解决算法

1、开放定址法

1.1线性探测法

1.2平方探测法

看例子

代码设计关键点之一

上述解决方法真的对吗

表空间不够怎么办

1.3 双散列

2、链地址法

举个简单的例子：

链地址法概述

链地址法的优势与缺点

贴上代码

六、哈希表的查找性能

1、查找成功的ASL计算方法：

2、查找不成功的ASL计算方法：

七、写在最后

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

数据结构与算法