C++哈希表映射 CMap类

鸦领主

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>

宁ぺ少爺

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