用c++创建一个最简单的哈希表（拉链法）

悠悠 2022-04-02 14:46 417阅读 0赞

> 我们都知道，当我们要在一个集合中查找数据时，如果这个集合是顺序表且我们能确定要找的数据在顺序表中的位置的话，我们就能通过下标直接找到元素，这无非是我们要追求的最高效的查找策略！但是现实总是那么骨感，在大多数情况下，要在茫茫数据海洋中找某些关键信息，是不可能直接找到的。因为我们并不知道我们要找的数据与其所在位置之间是否存在某种关联。

> 所以我们在存储数据时，建立如同顺序表形式的可以按照下标进行查找的存储集合，然后我们可以认为建立要存的关键信息和其在集合中的下标之间的关系，这样我们在找想找的信息时，就可以确定信息在集合中的下标了，这样就可实现较为高效的查找了。而我们所说的这个集合就称为哈希表，建立的下标与信息的关系可以通过哈希函数(自定义合理的函数)来实现。

> 哈希表在查找，加密等很多方面都有广泛用途。  
> 今天我用拉链法建立了简单的哈希表其结构如图所示：  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70]

`源码`

#include <iostream>
    #include<array>
    #include<memory>
    #include<string>
    #include<vector>
    using namespace std;
    
    class data{
        
    public :
        string name;
        int age;
        data(){
        
        }
        ~data(){
        }
    };
    class info:public data{
        
    
    public :
        vector<data>ls;
        info(){
        
        }
        ~info(){
        }
        static void init(array<shared_ptr<info>,27>&ss);
        static void input(array<shared_ptr<info>,27>&ss);
        static int getLoc(char a);;
        static void search(array<shared_ptr<info>,27>&ss);
    };
    
    void info::search(array<shared_ptr<info>,27>&ss){
        
    
        string name ;
        cin>>name ;
        int index = getLoc(name[0]);
        if(index==-1){
        
            cout<<"No the name"<<endl;
        }
        int i =0 ;
        int flag =1;
        for(i=0;i<(int)ss[index]->ls.size();i++){
        
            if(ss[index]->ls[i].name==name){
        
                flag =0;
                cout<<"The info of the person:"<<endl;
                cout<<" \nAge:"<<ss[index]->ls[i].age<<"      "<<"Name:"<<ss[index]->ls[i].name<<endl;
                break;
            }
        }
        if(flag ==1){
        
            cout<<"No the info"<<endl;
        }
    }
    int info::getLoc(char a){
        
        
                if(a>='A'&&a<='Z'){
        
                    return a-65;
                }
                 else if(a>='a'&&a<='z'){
        
                    return a-97;
                }
                else{
        
                    return -1;
            }
    }
    void info::input(array<shared_ptr<info>,27>&ss){
        
        string name ;
        cout<<"请输入姓名(由英文字符组成)和年龄 -1 to return..."<<endl;
        while(1){
        
            data dd;
            cin>>dd.name ;
            if(dd.name=="-1"){
        
                    break;
                }
            cin>>dd.age;
            //差试用一下lamda表达式
            auto key= [dd](){
        
                if(dd.name[0]>='A'&&dd.name[0]<='Z'){
        
                    return dd.name[0]-65;
                }
                 else if(dd.name[0]>='a'&&dd.name[0]<='z'){
        
                    return dd.name[0]-97;
                }
                else if(dd.name[0]==' '){
        
                    return 0;
                }
                else{
        
                    return -1;
            }
            };
            int index= key();
            if(index==-1){
        
                cout<<"The name is error!"<<endl;
                continue ;
            }
            ss[index]->ls.push_back(dd);
        }
    }
    void info::init(array<shared_ptr<info>,27>&ss){
          
        int i;
        for(i=0;i<27;i++){
        
            shared_ptr<info>p(new info());
            ss[i]=p;
        }
    }
    int main()
    {
        
        array<shared_ptr<info>,27>ss;
        info::init(ss); 
        info::input(ss);
        info::search(ss);
        return 0;
    }

> 这个程序刚开始创建了info类的指针数组，info类继承了data类，info类里面有个vector容器主要存data类数据信息的。举个例子吧，要是name首字母是A，根据key = (大写字母-65)，则该data类所有信息就存在以下标为key的数组中的vector容器中，即ss\[key\].ls.push\_back(含相应name关键字的对象)，后面同样的实现方法。在找时只需根据name首字母将要搜索的范围缩小，然后只能一个个遍历vector容器了。程序总的逻辑  
> 很简单，使用拉链法，哈希冲突也比较容易解决。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjgxMjQx_size_16_color_FFFFFF_t_70]: /images/20220402/20213bb25bdd4e698ad339f7527c67b9.png