论坛 › 编程技术 › C++哈希表映射 CMap类

鸦领主 发表于 2021-2-8 17:07:14

C++哈希表映射 CMap类

本帖最后由 鸦领主 于 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 = { NULL };//创建17个链表

void AddHead(Data data)//带入关键值比如5
{
    int n = data % COUNT;//取余为5
    SNode *p = new SNode;//申请一个堆空间
    p->data = data;//将关键值放进去
    p->pNext = g_hash;//将地址赋值为第5个链表
    g_hash = p;
}
//实现了把关键码值映射到表中一个位置来访问记录
bool Lookup(Data data)
{
    int n = data % COUNT;//带入一个数求出余数是5
    SNode* p = g_hash;//第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;
    char Pass;
};
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;
   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)//判断头节点是否为空
   {
      m_map=pNew;//是空节点，就将这个插入的节点变成头节点
         return;
   }
   SNode* p1 = m_map;
   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;//将m_map的地址赋值给p
   while (*p)//等价于是m_map直接放在这里
   {
         if ((*p)->key == key)
         {
             (*p)->value = value;
             return;
         }
      p = &((*p)->pNext);//将m_map指向的地址的地址赋值给p，每次都将指向到空地址赋值给p
   }
   SNode *pData = new SNode;
   pData->key = key;
   pData->value = value;
   pData->pNext = NULL;
   *p = pData;//等价于m_map=pData（此时m_map是NULL）</div><div>}</div>也可以使用做好的下标实现，[]有SetAt的功能
void CMap::SetAt(KEY key,VALUE& value)
{
   (*this) = 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;//获取头节点
   while (p)//p不等于空
   {
         if (p->key == key)//对比现在节点上的密钥和输入进来的密钥
         {
             value = m_map->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,"王五","87" };//将值1105,"王五","87"送入1105对应的链表中
    VALUE va = cm;//将1105对应的链表中的值取出来
    cout << "同一位置先插入的:"<< va.name <<"\t"<< va.Numb << "\t" << va.Pass << endl;
    cm = { 1105,"赵六","77" };//同一位置插入不同的值，将会更改
   va = cm;//将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;
   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)
   {
         m_map = pNew;
         return pNew->value ;
   }
   SNode* p1 = m_map;
   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;
   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>

宁ぺ少爺 发表于 2021-2-9 08:43:05

支持学逆向论坛，资源不错！

查看完整版本: C++哈希表映射 CMap类