在学习数据结构时,看到了有关哈希表的使用,虽然STL模板库里已有相关的实现,但我想简单实现下它的功能。


哈希表可以通过哈希函数来存储和查找值,这里我使用了较为简单的哈希函数,大大增加了其冲突的概率,我对冲突的处理使用的是链地址法。

虽然我使用了模板,但其实只限于 对int类型的处理,这跟我的哈希函数有关,往后我会改进,先写个简陋的版本。

#include <iostream>

template<typename T=int>
class Hash{
    enum state      //该节点是否有值,该节点可能有多个值满足哈希函数,跟所用哈希函数有关,
                    //使用了 取余 作为哈希函数,所以可能会经常性的起冲突,采用链地址法。
    {
        exist,
        nothing
    };

    typedef struct Node
    {
        T elem;
        state s;
        struct Node *next;
        Node(T elem = 0):elem(elem),s(nothing),next(nullptr){}
        ~Node(){
            if(next != nullptr){
                delete next;
            }
        }
    }Node;

private:
    Node *elems;
    int hash_function(T elem){          //哈希函数,测试比较简单,容易起冲突
        int mid = elem % 10;
        return mid;
    }
    const static int size = 10;         //静态常成员,固定大小,由于哈希函数为取余,则只存在0~9的情况
public :
    //构造初始个数,
    Hash():elems(new Node[size]){}    


    void put(T elem){
        int mid = hash_function(elem);
        if(elems[mid].s == nothing){
            elems[mid].elem = elem;
            elems[mid].s = exist;
        }else if(elems[mid].s == exist){
            Node *node = &elems[mid];
            while(node->next != nullptr){
                node = node->next;
            }
            Node *node1 = new Node(elem);
            node->next = node1;
        }
    }
    T get(T elem){
        int mid = hash_function(elem);
        //std::cout << elems[mid].next->next->elem << std::endl;
        if(elems[mid].s == exist){
            Node *node = &elems[mid];
            while(node != nullptr){
                if(node->elem == elem){
                    return node->elem;
                }else{
                    node = node->next;
                }
            }
        }
        return -1;              //说明没有所查找的值
    }
    ~Hash(){
        if(elems != nullptr){
            delete[] elems;
        }
    }
};

int main(){
    Hash<> h;
    h.put(10);
    h.put(100);
    h.put(10000);
    std::cout << h.get(1000000) << std::endl;
    return 0;
}
Logo

GitCode 天启AI是一款由 GitCode 团队打造的智能助手,基于先进的LLM(大语言模型)与多智能体 Agent 技术构建,致力于为用户提供高效、智能、多模态的创作与开发支持。它不仅支持自然语言对话,还具备处理文件、生成 PPT、撰写分析报告、开发 Web 应用等多项能力,真正做到“一句话,让 Al帮你完成复杂任务”。

更多推荐