哈希表查找代码实现

缺乏、安全感 2022-06-18 04:18 165阅读 0赞

*前言*

博客编写人：Willam
    博客编写时间：2017/3/29
    博主邮箱：2930526477@qq.com（有志同道合之人，可以加qq交流交流编程心得）

## 1、代码实现的介绍 ##

下面我将会实现哈希表的查找代码：  
其中我会采取的散列构造函数为最常用的构造函数：除留取余数法  
而解决冲突的方法采用以下三种，分别实现：

1.  线性探测
2.  二次探测
3.  链地址法

如果需要了解哈希表的详细介绍，可参考博客：[哈希表的详解][Link 1]

## 2、线性探测的实现 ##

*  linear.h文件的代码

/************************************************************/
    /*                程序作者：Willam                          */
    /*                程序完成时间：2017/3/29                  */
    /*                有任何问题请联系：2930526477@qq.com       */
    /************************************************************/
    //@尽量写出完美的程序
    
    
    //#pragma once是一个比较常用的C/C++杂注，
    //只要在头文件的最开始加入这条杂注，
    //就能够保证头文件只被编译一次。
    #ifndef   MY_H_FILE       //如果没有定义这个宏  
    #define   MY_H_FILE       //定义这个宏  
    
    #include<iostream>
    using namespace std;
    typedef int Keytype;
    
    //每次都是取质数最接近的质数
    
    struct Hash {
        Keytype * elem; //记录哈希表中的元素
        bool * isfull;  //记录哈希表是否有元素了
        int count;      //哈希表中元素的个数
        int sizeindex;
    
    };
    
    bool searchHash(Hash t, Keytype k, int & p, int &c,int * hashsize);
    bool insertHash(Hash & t, Keytype k, int * hashsize);
    bool DeleteHash(Hash & t, Keytype k, int * hashsize);
    void print(Hash  t, int * hashsize);
    
    #endif

*  linear.cpp文件的代码

#include"linear.h"
    
    
    //查找对应的关键字
    bool searchHash(Hash t, Keytype k, int & p,int &c,int * hashsize) {
        p = k%hashsize[t.sizeindex];
        while (t.isfull[p] && t.elem[p] != k && c < hashsize[t.sizeindex]-1) {
            ++c;
            //继续往下寻找下一个散列结点
            p=(k+c) % hashsize[t.sizeindex];
        }
        if (t.elem[p] == k) {
            return true;
        }
        return false;
    
    }
    
    
    
    
    bool insertHash(Hash & t, Keytype k, int * hashsize) {
        int p;
        int c = 0;
        if (searchHash(t, k, p,c,hashsize)) {
            return false;
        }
        else if (c==hashsize[t.sizeindex]-1) {
       //此时哈希表已经满，得重新分配了
            //首先是把之前的内容保存起来
            int temp;
            temp=hashsize[t.sizeindex];
            Keytype * elem = new Keytype[hashsize[t.sizeindex]];
            bool * isfull=new bool[hashsize[t.sizeindex]];
            for (int i = 0; i < hashsize[t.sizeindex]; ++i) {
                elem[i] = t.elem[i];
                isfull[i] = t.isfull[i];
            }
            delete t.elem;
            delete t.isfull;
            ++t.sizeindex;
            //重新分配空间
            t.elem= new Keytype[hashsize[t.sizeindex]];
            t.isfull=new bool[hashsize[t.sizeindex]];
            int i;
            for (i = 0; i < temp; ++i) {
                 t.elem[i]=elem[i];
                 t.isfull[i] = isfull[i];
            }
            for (; i < hashsize[t.sizeindex]; ++i) {
                t.isfull[i] = false;
            }
        }
        else {
            //cout << p << endl;
            //直接插入对应的位置
            t.elem[p] = k;
            ++t.count;
            t.isfull[p] = true;
        }
    
    }
    
    bool DeleteHash(Hash & t, Keytype k, int * hashsize) {
        int p;
        int c = 0;
        if (!searchHash(t, k, p, c,hashsize)) {
       //没找到要删除的元素
            return false;
        }
        else {
            t.isfull[p] = false;
            --t.count;
        }
    }
    
    void print(Hash t, int * hashsize) {
        cout << "当前的表的长度：" << hashsize[t.sizeindex] << endl;
        cout << "Hash表的元素个数为：" << t.count << endl;
        cout << "打印整个表：" << endl;
        for (int i = 0; i < hashsize[t.sizeindex]; ++i) {
            if(t.isfull[i])
            cout << t.elem[i] << " ";
            else {
                cout << "^" << " ";
            }
        }
        cout << endl;
    }

*  main.cpp文件的代码

#include"linear.h"
    int hashsize[]={ 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107,
    109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,
    227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337,
    347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457,
    461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593,
    599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719,
    727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857,
    859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 };
    int main() {
        Hash t;
        t.count = 0;
        t.sizeindex = 0;
        t.elem = new Keytype[hashsize[t.sizeindex]];
        t.isfull = new bool[hashsize[t.sizeindex]];
        cout << "请先输入10个数" << endl;
        for (int i = 0; i < hashsize[t.sizeindex]; ++i) {
                t.isfull[i] = false;
        }
    
        for (int i = 0; i < 10; ++i) {
            int temp;
            cin >> temp;
            insertHash(t,temp,hashsize);
            //print(t, hashsize);
        }
        print(t,hashsize);
        cout << "输入需要查找的数：" << endl;
        int key;
        cin >> key;
        int p;
        int c = 0;
        if (searchHash(t, key,p,c, hashsize)) {
            cout << "查找成功" << endl;
            cout << "为第" << p+1 << "个元素" << endl;
        }
        else {
            cout << "查找失败" << endl;
        }
        cout << "输入需要删除的数：" << endl;
    
        cin >> key;
        if (DeleteHash(t, key, hashsize)) {
            cout << "删除成功，删除后的结果：" << endl;
            print(t, hashsize);
        }
        else {
            cout << "删除失败" << endl;
        }
    
        system("pause");
        return 0;
    }

输入：

12 67 56 16 25 37 22 29 15 47
    16
    15

输出：  
![这里写图片描述][SouthEast]

## 3、二次探测的实现 ##

对于二次探测，其实它和线性探测的插入删除代码都是一样的，只是查找过程中单位的移动量不同，所以我们只要修改对应的查找函数就可以了，修改成如下：

//查找对应的关键字
    bool searchHash(Hash t, Keytype k, int & p,int &c,int * hashsize) {
        p = k%hashsize[t.sizeindex];
        while (t.isfull[p] && t.elem[p] != k && c < hashsize[t.sizeindex]-1) {
    
            //++c;
            //二次探测和线性探测的区别
            if (c == 0) {
                c=1;
                p = (k + c) % hashsize[t.sizeindex];
            }
            else if (c > 0) {
                c = -c;
                p = (k - c*c) % hashsize[t.sizeindex];
            }
            else if (c < 0) {
                c = -c + 1;
                p = (k + c*c) % hashsize[t.sizeindex];
            }
            //继续往下寻找下一个散列结点
        }
        if (t.elem[p] == k) {
            return true;
        }
        return false;
    
    }

输入：

12 67 56 16 25 37 22 29 15 47
    67
    12

输出：  
![这里写图片描述][SouthEast 1]

## 4、链地址法的实现 ##

*  List.h文件的代码

#pragma once
    /************************************************************/
    /*                程序作者：Willam                          */
    /*                程序完成时间：2017/3/29                  */
    /*                有任何问题请联系：2930526477@qq.com       */
    /************************************************************/
    //@尽量写出完美的程序
    
    
    //#pragma once是一个比较常用的C/C++杂注，
    //只要在头文件的最开始加入这条杂注，
    //就能够保证头文件只被编译一次。
    
    
    #include<iostream>
    using namespace std;
    typedef int Keytype;
    
    struct Node {
        Keytype data; //每个结点的值
        Node * next;  //下一个结点
        Node() {
            next = NULL;
        }
    };
    
    
    //每次都是取质数最接近的质数
    struct Hash {
        Node * elem; //头结点链表
        int sizeindex;
    
    };
    
    bool searchHash(Hash t, Keytype k, Node* & p, Node * & pre, int * hashsize);
    bool insertHash(Hash & t, Keytype k, int * hashsize);
    bool DeleteHash(Hash & t, Keytype k, int * hashsize);
    void print(Hash  t, int * hashsize);

*  List.cpp文件的代码

#include"List.h"
    bool searchHash(Hash t, Keytype k, Node * & p, Node * & pre, int * hashsize) {
    
        int index = k%hashsize[t.sizeindex];
        Node * head = t.elem[index].next;
        pre = NULL;
        while (head) 
        {
       //变量整个结点
            p = head;
            if (head->data == k) {
                return true;
            }
            pre = head;
            head = head->next;
        }
        return false;
    }
    
    
    //插入
    bool insertHash(Hash & t, Keytype k, int * hashsize) {
        Node * p;
        Node * pre;
        if (searchHash(t, k, p,pre, hashsize)) {
            return false;
        }
        else {
            Node * s = new Node;
            s->data = k;
            if (pre == NULL) {
                int index = k%hashsize[t.sizeindex];
                t.elem[index].next = s;
                return true;
            }
            p->next = s;
        }
        return true;
    }
    
    //删除结点
    bool DeleteHash(Hash & t, Keytype k, int * hashsize) {
        Node * p;
        Node * pre;
        if (!searchHash(t, k, p,pre,hashsize)) {
            return false;
        }
        else {
            if (pre == NULL) {
                int index = k%hashsize[t.sizeindex];
                t.elem[index].next =p->next;
                return true;
            }
            else {
                pre->next = p->next;
                delete p;
            }
        }
        return true;
    }
    
    void print(Hash  t, int * hashsize) {
        Node * p;
        for (int i = 0; i < hashsize[t.sizeindex]; ++i) {
            cout << i << " ";
            p = t.elem[i].next;
            while (p) {
                cout << p->data << " ";
                p = p->next;
            }
            cout << "^" << endl;
        }
    }

*  main.cpp文件的代码

#include"list.h"
    int hashsize[]={ 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107,
    109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223,
    227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337,
    347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457,
    461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593,
    599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719,
    727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857,
    859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 };
    int main() {
        Hash t;
        t.sizeindex = 0;
        t.elem = new Node[hashsize[t.sizeindex]];
        cout << "请先输入10个数" << endl;
        for (int i = 0; i < hashsize[t.sizeindex]; ++i) {
            t.elem[i].next = NULL;
        }
    
        for (int i = 0; i < 10; ++i) {
            int temp;
            cin >> temp;
            insertHash(t,temp,hashsize);
            //print(t, hashsize);
        }
        print(t,hashsize);
    
    
        cout << "输入需要查找的数：" << endl;
        int key;
        cin >> key;
        Node *p;
        Node *pre;
        int c = 0;
        if (searchHash(t, key,p,pre, hashsize)) {
            cout << "查找成功" << endl;
            cout <<  p->data  << endl;
        }
        else {
            cout << "查找失败" << endl;
        }
        cout << "输入需要删除的数：" << endl;
    
        cin >> key;
        if (DeleteHash(t, key, hashsize)) {
            cout << "删除成功，删除后的结果：" << endl;
            print(t, hashsize);
        }
        else {
            cout << "删除失败" << endl;
        }
    
        system("pause");
        return 0;
    }

输入：

12 67 56 16 25 37 22 29 15 47
    29
    29

输出：  
![这里写图片描述][SouthEast 2]

[Link 1]: http://blog.csdn.net/qq_35644234/article/details/67663581
[SouthEast]: /images/20220618/e92a23cf510d40f093011c3d6c654b9f.png
[SouthEast 1]: /images/20220618/9785063cd9f94477be64642effc15fdf.png
[SouthEast 2]: /images/20220618/fabde5c86f5d403a8d403dbcce8b9f27.png