链表法解决hash冲突[亲测有效]

全栈程序员-站长 • 2021年12月18日上午10:00 • 未分类 • 阅读 48

大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。

此处内容已经被作者隐藏，请输入验证码查看内容

请关注本站微信公众号，回复“验证码”，获取验证码。在微信里搜索“全栈程序员社区”或者“www_javaforall_cn”或者微信扫描右侧二维码都可以关注本站微信公众号。

/* @链表法解决hash冲突
* 大单元数组，小单元链表
*/
#pragma once 
#include <string>
using namespace std;

template<typename map_t>
struct Node
{
    size_t key;
    map_t content;
        
    Node *next;
    bool isEmpty;

    Node():next(NULL),isEmpty(true){}
};

// 根据hash函数将content添加到hash表中
template<typename map_t>
class ListHash
{
public:
    ListHash();
    ~ListHash();

    bool insert(size_t key, const map_t& val);
    bool find(size_t key, map_t& val);
    bool erase(size_t key);

private:
    size_t hash(size_t key);

private:
    size_t m_nElementSize;
    Node<map_t> *m_pNodeArray;
};

//////////////////////////实现/////////////////////////
template<typename map_t>
ListHash<map_t>::ListHash()
{
    m_nElementSize = 3;
    m_pNodeArray = NULL;
    m_pNodeArray = new Node<map_t>[m_nElementSize];
}

template<typename map_t>
ListHash<map_t>::~ListHash()
{
    delete[] m_pNodeArray;
    m_pNodeArray = NULL;
}

template<typename map_t>
size_t ListHash<map_t>::hash( size_t key )
{
    return key % m_nElementSize;
}


template<typename map_t>
bool ListHash<map_t>::insert( size_t key, const map_t& val )
{
    size_t idx = hash(key);
    Node<map_t> *pNode = &m_pNodeArray[idx];
    if (m_pNodeArray[idx].isEmpty)
    {
        pNode->key = key;
        pNode->content = val;
        pNode->isEmpty = false;
        pNode->next = NULL;
    }
    else
    {
        while (pNode->next != NULL)
        {
            pNode = pNode->next;
        }

        Node<map_t> *pTempNode = new Node<map_t>;
        pTempNode->key = key;
        pTempNode->content = val;
        pTempNode->isEmpty = false;
        pTempNode->next = NULL;

        pNode->next = pTempNode;
    }

    return true;
}

template<typename map_t>
bool ListHash<map_t>::erase( size_t key )
{
    size_t idx = hash(key);
    Node<map_t> *pNode = &m_pNodeArray[idx];
    Node<map_t> *pPrepNode = NULL;

    while (pNode!= NULL)
    {
        if (pNode->key == key)
        {
            if (pPrepNode)
            {
                pPrepNode->next = pNode->next;
            }
            delete pNode;
            return true;
        }

        pPrepNode = pNode;
        pNode = pNode->next;
    }
    return false;
}

template<typename map_t>
bool ListHash<map_t>::find( size_t key, map_t& val )
{
    size_t idx = hash(key);
    Node<map_t> *pNode = &m_pNodeArray[idx];

    while (pNode!= NULL)
    {
        if (pNode->key == key)
        {
            val = pNode->content;
            return true;
        }

        pNode = pNode->next;
    }
    return false;
}

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/120238.html原文链接：https://javaforall.net

链表法解决hash冲突[亲测有效]

相关推荐

Mask_RCNN训练自己的数据——制作COCO格式的数据集[通俗易懂]

c语言之voliate「建议收藏」

struts2拦截器学习

awvs原理_csgo奇葩武器代码

docker下载安装教程_mac装sql server

shell批量新建文件

发表回复