[C++] Hash_map 实现原理和源码[散列表][散列映射][泛式数据支持][STL]

末蓝、 2022-10-14 13:59 142阅读 0赞

Hash\_map  
作为非线性数据结构.  
在阅读前,你需要确定你已经真正的理解了什么是指针.  
并且在不看任何源码的情况下,通过原理实现出链表数据结构.  
如果不太确定的话,建议以下文章:  
[\[C/C++\]指针的原理和对指针的运用及理解(包括函数指针和多级指针)][C_C]  
[\[C++\]什么是引用,以及引用和指针的关系(对内存和指针运用的理解)][C]  
[\[C++\] LinkList:双向不循环链表的原理和实现(基础)][C_ LinkList]

或者不想看长篇大论,可以直接滑动到最下面,copy源码.  
源码内有注释和例子,复制粘贴就能用.**如果可以,请点个免费的赞,支持一下**.  
纯爱发电,也得需要爱.

--------------------

我不会跟大家说太多的废话,比如时间复杂度之类的玩意,大家过来找Hash\_map的文章,必然是知道它大概是个什么东西.  
下面正式开讲.  
**Hash\_map** 或者说,STL标准容器中的 **unordered\_map**.  
它们说白了,就是一个**链表指针数组**.

而它之所以可以快速查找数据,通过较少次数的循环,就能在上百,上千,上万次的数据中,找到你想要的.  
就因为,它并不真的是挨个遍历.  
而是在指定的链表内查找.

如果没有这个概念.  
我们先在脑海中抽象一下.

LinkList<int> *list[3];

<table> 
 <thead> 
  <tr> 
   <th>LinkList [0]</th> 
   <th>LinkList [1]</th> 
   <th>LinkList [2]</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>data1</td> 
   <td>data4</td> 
   <td>data6</td> 
  </tr> 
  <tr> 
   <td>data2</td> 
   <td>data5</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>data3</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

往里面new了6个数据.

如果用数组或者链表的方式,去找data6,那么就要从头遍历.  
你最少要循环6次可以找到.  
那可能会说,我可以选择从尾遍历,这样第一次就能找到.  
那么问题来了,如果要找data1呢?  
循环次数还是这么多.  
因为你不可能未卜先知的知道自己的数据,在这个数据结构中的那一部分.  
它可能位于前部,中部,尾部.  
最糟糕的就是,你找的数据,它并不存在,而计算机又不知道你找的数据存不存在,它会整个遍历一圈.  
效率特别的低.

而用Hash\_map来遍历数据data6,它会直接去LinkList\[2\]里面找数据.  
如果LinkList\[2\]没有,那就证明整个数据结构都不存在这项数据.

这其中的关键,就是数组的下标.  
它知道这个数据,如果真的存在,它会在第几个数组元素.

它是如何实现的这个功能的.  
那么就要引入一个独特的东西.  
hash\_value,哈希值.  
哈希值是一个无符号正整数.  
Hash\_map是通过哈希值来确定数据的存放链表.

而要让Hash\_map这个数据结构,拥有哈希值.  
则要再引入一个概念.  
就是Key.  
这个Key即是哈希值的来源,也是能否找寻到这个数据的关键.

我们把这个key的原始数据,和你需要存放的数据,一起放进节点.  
而哈希值,则需要通过key转换.

--------------------

using hash = unsigned int;
    hash HashFunction(keyType key)
        { 
            uint modle{  53 }; // mapSize >32 <64 M53
    
            hash_value = ((hash)key % modle) % 数组大小;    // 最后不M数组大小,必然会出现越界问题
            return hash_value;
        }

这就是将key转换成哈希值的哈希函数.

有了哈希值的概念,我们就要知道一个名词.  
**哈希冲突**  
哈希冲突就是当两个不一样的key转换成了一样的哈希值.

如果你不把key的原始数据扔进哈希节点里面.  
你就会导致,不一样的数据,会被新数据覆写掉.

而解决哈希冲突的方式有很多种.  
我个人采用的是在指定数组的大小区间内%一个质数.  
[\[HashCollision\]\[哈希冲突\]\[HashValue\]:最佳哈希质数][HashCollision_HashValue]  
该链接有已经计算好的质数.

只要你的数组大小,在这个区间内,就可以使用相应的质数,减少哈希冲突.  
如果你觉得这个方法不适合你,也可以去网上找找其他的方法.

--------------------

我们拥有了哈希值,我们也有了链表数值.  
现在你只需要让程序,自己计算哈希值,然后将数据写入对应的链表即可.

hash\_map的原理非常简单.

实现的关键,就是Hash\_value

可以通过下面的代码,来进一步理解hash\_map

--------------------

**代码**

// ReSharper disable CppClangTidyClangDiagnosticInvalidSourceEncoding
    // 停用ReSharper插件的字符串拼写检查
    
    #include <iostream>
    
    #ifndef NULL
    #define NULL 0x0
    #endif
    
    using uint = unsigned int;
    using hash = unsigned int;
    using BOOL = short;
    
    char* StringCopy(char* dest, const char* source)
    { 
        if (!(dest != nullptr && source != nullptr))
        { 
            return nullptr;
        }
        char* tmp = dest;
        while ((*dest++ = *source++) != '\0') { }
        return tmp;
    }
    
    class Student
    { 
        const char* name;
        uint age;
    public:
        Student(uint age_ = 18, const char* name_ = "Name:Unknown") :name(name_), age(age_)
        { 
    
        }
        Student(const Student& copyObj) // 深复制构造函数:存在外部指针
        { 
            this->age = copyObj.age;
            this->name = new char[strlen(copyObj.name) + 1];
            StringCopy(const_cast<char*>(this->name), copyObj.name);
        }
        bool operator==(const Student& rightObj)    // 运算符重载:相等逻辑判断
        { 
            if (this->age == rightObj.age && strcmp(this->name, rightObj.name) != 0)
                return true;
            return false;
        }
    };
    
    template <typename keyType, typename dataType>
    class Hash_node                                 // 和链表的节点实现方式差不多
    { 
        keyType hashkey;                            // hashKey 存储钥匙,这个钥匙是hash_map能正常实现同hash_value下,在一个index中进行覆写还是链接的关键
        dataType data;                              // data area
        Hash_node* nPoint;                          // nPoint
    public:
        Hash_node(keyType hashKey_ = NULL, dataType data_ = NULL, Hash_node* nPoint_ = nullptr)
            :hashkey(hashKey_), data(data_), nPoint(nPoint_)
        { 
    
        }
    
        keyType& GetHashKey()
        { 
            return hashkey;
        }
    
        dataType& GetData()
        { 
            return this->data;
        }
    
        Hash_node*& GetNextPoint()      // 返回对象的nPoint指针引用
        {                            // 如果返回类型是Hash_node的指针类型,那么只会返回里面的值
            return this->nPoint;
        }
    
        Hash_node* GetObject()
        { 
            return this;
        }
    
    };
    
    // 模板参数1:钥匙类型 模板参数2 : 数据类型 模板参数3 : map大小
    template <typename keyType, typename dataType, size_t mapSize>
    class Hash_map
    { 
        hash hash_value;
        Hash_node<keyType, dataType>* map[mapSize];
    
        hash HashFunction(keyType key)
        { 
            uint modle{  57 }; // mapSize >32 <64 M57
            					// https://blog.csdn.net/qq_42468226/article/details/117166210 最优数
    
            hash_value = ((hash)key % modle) % mapSize;    // 最后不 m数组大小,必然会出现越界问题
            return hash_value;
        }
    
    public:
        Hash_map(keyType key = NULL, const dataType& data = NULL) :hash_value(HashFunction(key)), map{  nullptr }
        { 
            this->Hash_push(key, data);
        }
    
        // key相同覆写,hashValue相同追加
        bool Hash_push(keyType key, const dataType& data)
        { 
            /*Hash_node<keyType, dataType>** */
            this->HashFunction(key);    // 计算哈希值
            Hash_node<keyType, dataType>** hnpp = &this->map[hash_value];
            while (*hnpp)   //进入循环证明 map的该元素位置已经被某些数据写入过,所以需要检测是需要覆盖还是追加到尾.
            { 
                // 判断key是否相同,相同覆写,否则追加
                if (this->map[hash_value]->GetHashKey() == key)
                { 
                    this->map[hash_value]->GetData() = data;
                    return true;
                }
                hnpp = &(*hnpp)->GetNextPoint();
            }
            if (!*hnpp)
            { 
                *hnpp = new Hash_node<keyType, dataType>{  key,data };
                return true;
            }
    
            return false;   //safe return
        }
    
        // 0 钥匙:不匹配 1 钥匙:匹配 2 钥匙和数据:匹配
        BOOL Map_check(keyType key, const dataType& data = NULL)
        { 
            this->HashFunction(key);    // 计算哈希值
            Hash_node<keyType, dataType>** hnpp = &this->map[hash_value];
            while (*hnpp)   //进入循环证明 map的该元素位置已经被某些数据写入过,所以需要检测是需要覆盖还是追加到尾.
            { 
                // 判断key是否相同,相同覆写,否则追加
                if ((*hnpp)->GetHashKey() == key) // hnpp[hash_value]->GetHashKey()
                { 
                    if ((*hnpp)->GetData() == data)
                        return 2; // 钥匙匹配 数据匹配
                    return 1;   // 钥匙匹配 数据不匹配
                }
                hnpp = &(*hnpp)->GetNextPoint();
            }
    
            return 0;  // 0 钥匙不匹配,数据不匹配
        }
    
    };
    
    int main(void)
    { 
        std::cout << "\t\tHash_map testing program" << std::endl;
    
        // 模板参数1:钥匙类型 模板参数2:数据类型 模板参数3:map大小.
        Hash_map<int, int, 50>hash_map{ };   // 压第一个数据,来源于缺省构造,一般会在 [0]-0的位置
    
        hash_map.Hash_push(15, 99);     // 压第二个数据
        hash_map.Hash_push(15, 100);    // 覆盖第二个数据
    
        switch (hash_map.Map_check(15,100))    //switch 使用 Map_check 函数 例子
        { 
        case 0:
            std::cout << "[KEY]:未匹配" << std::endl;
            break;
        case 1:
            std::cout << "[KEY]:匹配" << std::endl;
            break;
        case 2:
            std::cout << "[DATA]:匹配" << std::endl;
            break;
        default:
            std::cout << "Hello,World!" << std::endl;
            break;
        }
    
        if (hash_map.Map_check(15))     // if 使用 Map_check 函数 例子
            hash_map.Hash_push(15, 999);    // 覆盖第二个数据
    
        for (uint count{  0 }; count < 100; count++) // 快压一百个数据
            hash_map.Hash_push(count, count);
    
        hash_map.Map_check(99, 99); // 数据查找速度例子,最多3次循环查询完毕.
    
        // 泛型结构支持
        Hash_map<const char*, Student, 30> studentMap{  "学号:1001",Student{ 18,"张三"} };
    
        studentMap.Hash_push("学号:1002", Student{  18,"李四" });
        studentMap.Hash_push("学号:1003", Student{  19,"王二麻子" });
    
        if (studentMap.Map_check("学号:1003"))
            studentMap.Hash_push("学号:1003",Student{ 5,"Hello,World"});
    
        return 0;
    }

[C_C]: https://blog.csdn.net/qq_42468226/article/details/117090516?spm=1001.2014.3001.5501
[C]: https://blog.csdn.net/qq_42468226/article/details/116539271?spm=1001.2014.3001.5501
[C_ LinkList]: https://blog.csdn.net/qq_42468226/article/details/116530424?spm=1001.2014.3001.5501
[HashCollision_HashValue]: https://blog.csdn.net/qq_42468226/article/details/117166210