查看: 399|回复: 1

[原创图文] C++哈希表映射 CMap类

[复制链接]

35

主题

47

帖子

3

精华

解密专家

Rank: 16

学币
380
荣耀
0
rank
0
违规
0
发表于 2021-2-8 17:07:14 | 显示全部楼层 |阅读模式
本帖最后由 鸦领主 于 2021-2-9 15:19 编辑

1.介绍

散列表(Hash table,也叫哈希表),是根据关键码值而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表
#include<iostream>
using namespace std;
typedef int Data;
enum{COUNT = 17};
struct SNode
{
    Data data;
    SNode* pNext;
};
SNode* g_hash[COUNT] = { NULL };//创建17个链表

void AddHead(Data data)//带入关键值比如5
{
    int n = data % COUNT;//取余为5
    SNode *p = new SNode;//申请一个堆空间
    p->data = data;//将关键值放进去
    p->pNext = g_hash[n];//将地址赋值为第5个链表
    g_hash[n] = p;
}
//实现了把关键码值映射到表中一个位置来访问记录
bool Lookup(Data data)
{
    int n = data % COUNT;//带入一个数求出余数是5
    SNode* p = g_hash[n];//第5个链表头节点赋值给p
    while (p)//将会在第5个链表遍历
    {
        if (data == p->data)
            return true;
            p = p->pNext;
    }
    return false;
}
//查找5,直接去了第5个链表遍历,没有去其他的链表遍历,加快了查找的速度
int main()
{
    AddHead(212);
    AddHead(8);
    AddHead(12);
    AddHead(13485);
    AddHead(17);
    AddHead(13);
    AddHead(46);
    AddHead(55);
    AddHead(49);

    return 0;
}

哈希表

哈希表


2.CMap类(几个重要函数介绍)
将密钥映射到内容的字典集合类。
a)SetAt:插入元素的主要函数
参数void SetAt(KEY key,VALUE value)
KEY--指定 密钥 参数类型的模板参数。
key--指定的密钥
VALUE--指定值参数类型的模板参数。
value--指定的值
首先,分配该密钥到链表中。 如果找到该密钥没有值,将创建新的值,如果有则相应的值更改
列子:
struct VALUE
{
    int Numb;
    char name[18];
    char Pass[18];
};
int main()
{
    CMap<int,int,VALUE,VALUE&> cm;
    VALUE va[] = {
        {1124,"张三","88"} ,
        {1134,"李四","72"} ,
        {1124,"王五","47"} ,
    };
    int i = -1;
    while (++i < _countof(va))
        cm.SetAt(va.Numb, va);//循环插入3个元素,因为有重复的密钥,先插入的将更改为后插入的值

函数实现方法
一级指针实现

 void CMap::SetAt(KEY key,VALUE& value)
 {
     int n = key % m_nCount;//m_nCount为你指定的链表数量,<span data-ttu-id="695df-358" style="box-sizing: inherit; outline-color: inherit; color: rgb(23, 23, 23); font-family: "Segoe UI", SegoeUI, "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255); text-decoration-style: initial; text-decoration-color: initial;">分配该密钥到链表中</span>
     SNode* p2 = m_map[n];
     while (p2)//实现有重复的密钥就替换
     {
         if (p2->key == key)//判断这个节点中的密钥是否与输入进来的密钥相同
         {
             p2->value = value;//如果相同则输入的值,替换这个节点的值
             return;
         }
         p2 = p2->pNext;
     }
//下面的代码则是尾插法,基本都一样
     SNode* pNew = new SNode;//申请堆空间
     pNew->key = key;//将密钥送进去
     pNew->value = value;//将值送进去
     pNew->pNext = NULL;//指向空地址
    if (!m_map[n])//判断头节点是否为空
     {
        m_map[n]=pNew;//是空节点,就将这个插入的节点变成头节点
         return;
     }
     SNode* p1 = m_map[n];
     while (p1->pNext != NULL)//将头节点循环的下一个地址为空
         p1 = p1->pNext;
      p1->pNext = pNew;//在将头节点的下一个地址为现在的这个节点,这样就连接起来了
 }

二级指针实现
<div> void CMap::SetAt(KEY key,VALUE& value)
 {
     int n = key % m_nCount;
     SNode **p=&m_map[n];//将m_map[n]的地址赋值给p
     while (*p)//等价于是m_map[n]直接放在这里
     {
         if ((*p)->key == key)
         {
             (*p)->value = value;
             return;
         }
        p = &((*p)->pNext);//将m_map[n]指向的地址的地址赋值给p,每次都将指向到空地址赋值给p
     }
     SNode *pData = new SNode;
     pData->key = key;
     pData->value = value;
     pData->pNext = NULL;
     *p = pData;//等价于m_map[n]=pData(此时m_map[n]是NULL)</div><div>}</div>
也可以使用做好的下标实现,[]有SetAt的功能
void CMap::SetAt(KEY key,VALUE& value)
{
     (*this)[key] = value;//this加上*相当于是一个对象

}

b)Lookup:查找密钥对应的值
参数BOOL Lookup(KEY key, VALUE &value);
KEY--指定 密钥 参数类型的模板参数。
key--指定的密钥
VALUE--指定值参数类型的模板参数。
value--指定的值
输入密钥,会返回出与密钥匹配的值,没有匹配的则什么也不干
列子:
    VALUE v;//指定一个VALUE类型的对象
    if (cm.Lookup(1124, v))//找到返回真,找不到返回假
        cout <<"1124:"<< v.name << "\t" << v.Numb << "\t" << v.Pass << endl;
    else
        cout << "没有找到"<<endl;
    if (cm.Lookup(1134, v))
    cout <<"1134:"<< v.name << "\t" << v.Numb << "\t" << v.Pass << endl;
    else
        cout << "没有找到" << endl;
    if (cm.Lookup(1110, v))
        cout << v.name << "\t" << v.Numb << "\t" << v.Pass << endl;
    else
        cout <<"1110:"<< "没有找到" << endl;

函数实现方法
 bool CMap::Lookup(KEY key,VALUE& value)
 {
     int n = key %m_nCount;
     SNode* p = m_map[n];//获取头节点
     while (p)//p不等于空
     {
         if (p->key == key)//对比现在节点上的密钥和输入进来的密钥
         {
             value = m_map[n]->value;//将带入的值赋值为这个节点上的值
             return true;//返回真
         }
         p = p->pNext;
     }
     return false;//找不到就返回假
 }


c)operator []:成员函数的便利替换 SetAt
参数:VALUE& operator[](KEY key)
KEY--指定 密钥 参数类型的模板参数。

key--指定的密钥


做右值:有lookup的功能,做左值:有SetAt的功能
列子:
int main()
{
    CMap cm;
    cm[1105] = { 1105,"王五","87" };//将值1105,"王五","87"送入1105对应的链表中
    VALUE va = cm[1105];//将1105对应的链表中的值取出来
    cout << "同一位置先插入的:"<< va.name <<"\t"<< va.Numb << "\t" << va.Pass << endl;
    cm[1105] = { 1105,"赵六","77" };//同一位置插入不同的值,将会更改
     va = cm[1105];//将1105对应的链表中的值取出来
    cout <<"同一位置后插入的:"<< va.name << "\t" << va.Numb << "\t" << va.Pass << endl;
    return 0;
}

哈希表

哈希表



函数实现方法
一级指针实现
<font color="#171717">int n = key % m_nCount;
     SNode* p2 = m_map[n];
     while (p2)
     {
         if (p2->key == key)
         {
             return p2->value;
         }
         p2 = p2->pNext;
     }
     SNode* pNew = new SNode;
     pNew->key = key;
     pNew->pNext = NULL;
     if (!m_map[n])
     {
         m_map[n] = pNew;
         return pNew->value ;
     }
     SNode* p1 = m_map[n];
     while (p1->pNext != NULL)
         p1 = p1->pNext;
      p1->pNext = pNew;
      return p1->pNext->value;</font>
二级指针实现
<font color="#171717">VALUE& CMap::operator[](KEY key)
 {
     
    int n = key % m_nCount;
     SNode** p2 = &m_map[n];
     while (*p2)
     {
         if ((*p2)->key == key)
         {
             return (*p2)->value;
         }
         p2 = &(*p2)->pNext;
     }
     SNode* pNew = new SNode;
     pNew->key = key;
     pNew->pNext = NULL;
     *p2 = pNew;
      return pNew->value;
</font><div>}</div>

温馨提示:
1.如果您喜欢这篇帖子,请给作者点赞评分,点赞会增加帖子的热度,评分会给作者加学币。(评分不会扣掉您的积分,系统每天都会重置您的评分额度)。
2.回复帖子不仅是对作者的最好奖励,还可以获得学币奖励,请尊重作者的劳动成果,拒绝做伸手党!
3.发广告、灌水回复等违规行为一经发现直接禁言,如果本帖内容涉嫌违规,请点击论坛底部的举报反馈按钮,也可以在【投诉建议】板块发帖举报。
学逆向论坛-免费的逆向学习论坛

2

主题

7

帖子

0

精华

初级会员

Rank: 4

学币
24
荣耀
0
rank
0
违规
0

    发表于 2021-2-9 08:43:05 | 显示全部楼层
    支持学逆向论坛,资源不错!
    学逆向论坛-免费的逆向学习论坛
    关闭

    论坛公告上一条 /1 下一条

    快速回复 返回顶部 返回列表