哈希表

哈希表的定义：

哈希表又叫散列表，关键值通过哈希函数映射到数组上，查找时通过关键值直接访问数组。在上面的例子里，我们将用户名通过哈希函数映射成一个整数，也就是数组的存储位置，在检测时用同样方法计算出存储位置，如果位置上已有元素则表示用户名已经被注册。

哈希函数指的是关键值和存储位置建立的对应关系，查找时只要根据这个关系就能找到目标位置。一般我们只要通过一次查找就能找到目标位置，但有些关键字需要多次比较和查找才能找到，这是为什么呢？因为哈希表里，可能存在关键字不同但是哈希地址相同的情况，也就是冲突。一般情况下，冲突是不可避免的，因为关键字集合往往比哈希地址集合大很多。

设计哈希函数没有统一的方法，同一个哈希函数不一定能适用所有问题，其产生的影响也是不一样的。哈希函数的设计又是至关重要的，那么我们该如何设计呢？一般来说，设计哈希函数时要达到两个要求：计算简单，计算复杂的哈希函数会增加查询的时间；关键字尽可能地均分到存储地址上，这样可以减少冲突。

• 设计哈希函数时，既要让哈希函数计算尽可能简单，又要尽可能让存储地址分配均匀
• 在关键字数量和跨度都不大的情况下，可以用直接寻址法构造哈希函数避免冲突
• 用除留余数法构造哈希函数，p 一般选择不大于 m 的质数，可以减少冲突

---

通过前面的课程，我们了解到我们可以构造优秀的哈希函数来减少冲突，但是一般情况下冲突是不可避免的，那么我们该怎么处理冲突呢？前面的课程提到了解决冲突的方法也会影响哈希表的查找效率，选择一个优秀的方法来处理冲突显得尤为重要。那么常见的处理冲突的方法有哪些呢？

（1）开放地址法

如果发生冲突，那么就使用某种策略寻找下一存储地址，直到找到一个不冲突的地址或者找到关键字，否则一直按这种策略继续寻找。如果冲突次数达到了上限则终止程序，表示关键字不存在哈希表里。一般常见的策略有这么几种：

1. 线性探测法，如果当前的冲突位置为 d，那么接下来几个探测地址为 d + 1，d + 2，d + 3 等，也就是从冲突地址往后面一个一个探测；
2. 线性补偿探测法，它形成的探测地址为 d + m，d + 2 * m，d + 3 * m 等，与线性探测法不同，这里的查找单位不是 1，而是 m，为了能遍历到哈希表里所有位置，我们设置 m 和表长 size 互质；
3. 随机探测法，这种方法和前两种方法类似，这里的查找单位不是一个固定值，而是一个随机序列。
4. 二次探测法，它形成的探测地址为 d + 12，d + (-1)2，d + 22，d + (-2)2 等，这种方法在冲突位置左右跳跃着寻找探测地址。

开放地址法计算简单快捷，处理起来方便，但是也存在不少缺点。线性探测法容易形成“堆聚”的情况，即很多记录就连在一块，而且一旦形成“堆聚”，记录会越聚越多。另外，开放地址法都有一个缺点，删除操作显得十分复杂，我们不能直接删除关键字所在的记录，否则在查找删除位置后面的元素时，可能会出现找不到的情况，因为删除位置上已经成了空地址，查找到这里时会终止查找。

（2）链地址法

该方法将所有哈希地址相同的结点构成一个单链表，单链表的头结点存在哈希数组里。链地址法常出现在经常插入和删除的情况下。

相比开放地址法，链地址法有以下优点：不会出现“堆聚”现象，哈希地址不同的关键字不会发生冲突；不需要重建哈希表，在开放地址法中，如果哈希表里存满关键字了就需要扩充哈希表然后重建哈希表，而在链地址法里，因为结点都是动态申请的，所以不会出现哈希表里存满关键字的情况；相比开放地址法，关键字删除更方便，只需要找到指定结点，删除该结点即可。

开放地址法和链地址法各有千秋，适用于不同情况。当关键字规模少的时候，开放地址法比链地址法更节省空间，因为用链地址法可能会存在哈希数组出现大量空地址的情况，而在关键字规模大的情况下，链地址法就比开放地址法更节省空间，链表产生的指针域可以忽略不计，关键字多，哈希数组里产生的空地址就少了。

示例代码及相关基础操作：

#include <iostream>
#include <string>
using namespace std;
class HashTable {
private:
    string *elem;
    int size;
public:
    HashTable() {
        size = 2000;
        elem = new string[size];
        for (int i = 0; i < size; i++) {
            elem[i] = "#";
        }
    }
    ~HashTable() {
        delete[] elem;
    }
  哈希表构成：一个数组
             一个局部哈希表容量的size

//构造哈希函数    
int hash(string& index) {
     int code = 0;
     for (size_t i = 0; i < index.length(); i++)
     {
      //设计的哈希表取地址公式
     code = (code * 256 + index[i] + 128) % size;
    }
        return code;
    }
解析：code字符串index的哈希值，
         也就是对应的存储地址。

//查找
bool search(string& index, int& pos, int& times) {
      pos = hash(index);
      times = 0;
     //发生冲突：pos位置存在元素而且不是index
      while (elem[pos] != "#" && elem[pos] != index)
       {//循环退出条件：空的或者该位置向是index
            times++;//记录冲突数
            if (times < size) {
             //冲突数小于表的大小
             //然后线性探测，一个一个往后找
             //同时也是循环条件
                pos = (pos + 1) % size;
            } else {
                return false;
            }
        }
//退出时有可能是空的也有可能是index
//所以在这里要判断
      if (elem[pos] == index) {
            return true;
        } else {
            return false;
        }
    }
分析：pos记录插入的位置
     times记录冲突的次数
 
//插入
//调用元素如果哈希表内已有元素则不做处理；
//如果冲突次数没达到哈希表长度的一半，
//则插入到哈希表，否则需要重建哈希表表示失败。
    int insert(string& index){
        int pos,times;
        if(search(index,pos,times)){
        return 2;
//返回2表示元素液晶存在
        }
        else if(times<size/2){
        elem[pos]=index;
            return 1;
//返回1表示数组插入成功
        }
        else{
        recreate();
            return 0;
//插入失败返回0
        }
    }

//重建哈希表
//没什么好说的：新建一个两倍大小的
//数组，然后for循环复制原来的数据，
//最后交换数组地址就酱~
  void recreate(){
    string* temp_elem;
    temp_elem=new string[size];
        for(int i=0;i<size;i++){
        temp_elem[i]=elem[i];
        }
        int copy_size=size;
        size=size*2;
        delete[] elem;
        elem=new string[size];
        for(int i=0;i<size;i++){
        elem[i]="#";
        }
        for(int i=0;i<copy_size;i++){
            if(temp_elem[i]!="#"){
            insert(temp_elem[i]);
            }
        }

        delete[] temp_elem;

    }

 
};
int main() {
    HashTable hashtable;
    string buffer;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
    cin>>buffer;
      int ans=hashtable.insert(buffer);
        if(ans==0){
        cout<<"insert failed!"<<endl;
        }
         else if(ans==1){
        cout<<"insert success!"<<endl;
        }
          else if(ans==2){
        cout<<"It already exists!"<<endl;
        }

    }
    int temp_pos,temp_times;
    cin>>buffer;
   if( hashtable.search(buffer,temp_pos,temp_times))
   {
       cout<<"search success!"<<endl;
   }else{
       cout<<"search failed!"<<endl;
   }

    return 0;

}