std::hash和unordered_map用法，C++自定义哈希表

std::hash

std::hash是实现了仿函数的类模板，根据传入不同数据类型T，获得其哈希值。
返回值类型：size_t。
对于C/C++内置数据类型，已经实现了其哈希函数，自定义数据类型需要定义其哈希值的求值方式。

std::hash几个原则

不能拋出异常
对于相等的键必须产生相等的哈希值
对于不相等的键产生碰撞的可能性必须最小接近 size_t 最大值的倒数

1、内置类型可直接生成hash值。

    std::hash<int> inthash;
    size_t  hash1 =  inthash(1);
    size_t  hash2 =  inthash(-1);
    printf("hash1=%lu\n",hash1);
    printf("hash2=%lu\n",hash2);

    std::hash<std::string> stringhash;
    size_t  hash3 =  stringhash("helloworld");
    size_t  hash4 =  stringhash("nihao");
    printf("hash3=%lu\n",hash3);
    printf("hash4=%lu\n",hash4);
1
2
3
4
5
6
7
8
9
10
11

打印

hash1=1
hash2=18446744073709551615
hash3=10313766814229003468
hash4=5306584351276782105
1
2
3
4

2、自定义数据类型生成std::hash哈希值。

#include <unordered_map>
class Student{
public:
    int age;
    std::string name;

    //重载==，可做unordered_set和unordered_map的key，而key要保证唯一
    bool operator==(const Student& stu) const{return (age == stu.age) && (name == stu.name); }
};

//自定义数据类型Student生成hash值的方式
namespace std
{
    template<>
    struct hash<Student>: public __hash_base<size_t, Student>
    {
        size_t operator()(const Student& stu) const noexcept
        {
            //可以自定义哈希值的生成方式
            return (std::hash<int>()(stu.age)) ^ (std::hash<std::string>()(stu.name) << 1);
        }
    };
}

    std::hash<Student> Studenthash;
    Student mStudent;
    mStudent.age = 18;
    size_t hash5 = Studenthash(mStudent);
    printf("hash5=%lu\n",hash5);

    std::unordered_map<Student, char> umStudent;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

打印

hash5=12285018377944847566
1

unordered_map

C++中的哈希表是通过unordered_map实现的，它是一种关联容器，可以将键值对存储在其中。它的特点是快速查找，插入和删除，时间复杂度为O(1)。它使用哈希函数将键映射到桶中，每个桶中存储一个链表，用于解决哈希冲突。unordered_map还提供了许多操作，例如迭代器遍历，查找元素，删除元素等.

1、关联性：通过key去检索value，而不是通过绝对地址（和顺序容器不同）
2、无序性：使用hash表存储，内部无序
3、Map : 每个值对应一个键值
4、键唯一性：不存在两个元素的键一样
5、动态内存管理：使用内存管理模型来动态管理所需要的内存空间
6、时间复杂度，接近常数。

map

map内部实现了一个红黑树，根据key有序排列，查找时间复杂度lgn。

unordered_map内部实现：

首先分配一大片内存，形成许多桶。是利用hash函数，对key进行映射到不同区域（桶）进行保存。

插入过程

1、得到key。
2、通过hash函数得到hash值。
3、得到桶号(一般都为hash值对桶数求模)。
4、存放key和value在桶内。

查询过程

1、得到key。
2、通过hash函数得到hash值。
3、得到桶号(一般都为hash值对桶数求模)。
4、比较桶的内部元素是否与key相等，若都不相等，则没有找到。
5、取出相等的记录的value。

哈希冲突（开散列）

1、key通过hash函数计算得到的桶号如果相同，则把这些<key,value>都放入这个桶中，桶中的元素通过一个大链表连接起来，链表的头结点存储在哈希表中。
2、查找时先找到桶，再遍历桶里的链表。

unordered_map使用小结
1、容器内key唯一，如果存入相同的key，则存入失败。
2、不同的key，相同的value，可以存入。
3、key是否相等，取决于重载的==运算符。
4、key的哈希值相同，不影响数据存储和查询，效率会降低。
5、通过迭代器可以修改value，但不能修改key，key是无法修改的。
6、通过迭代器遍历和删除，和map类似。

unordered_map访问元素
1、通过[key]下标访问时，如果容器中没有该key，则会想容器中添加该key，value是默认初始值。
2、通过.at(key)访问时，如果没有找到key，则会抛出异常out_of_range，或crash。
3、推荐使用find查找访问，返回迭代器，查找失败返回end()。

unordered_map插入元素
1、emplace返回值类型，pair<unordered_map<Student, int>::iterator, bool> ret1,ret2;
2、当 emplace() 成功添加新键值对时，返回的迭代器指向新添加的键值对，bool 值为 True；
3、当 emplace() 添加新键值对失败时，说明容器中本就包含一个键相等的键值对，此时返回的迭代器指向的就是容器中键相同的这个键值对，bool 值为 False。

常用方法代码示例，使用上面自定义类Student做key：

 Student mStudent1;
    Student mStudent2;
    mStudent1.age = 18;
    mStudent1.name = "tom";
    mStudent2.age = 19;
    mStudent2.name = "lucy";

    std::unordered_map<Student, int> unomap;
    unomap.emplace(mStudent1,10086);//插入元素
    unomap.emplace(mStudent1,10000);//插入相同的key，value不会更新
    unomap.emplace(mStudent2,9527);//插入元素

    //遍历
    auto ite = unomap.begin();
    while(ite != unomap.end())
    {
        printf("key=%s,value=%d\n",ite->first.name.c_str(),ite->second);
        ite++;
    }

    int value = unomap[mStudent2];//下标访问，如果不存在该key，返回值为0或不可控
    printf("value=%d\n",value);

    int cnt = unomap.count(mStudent1);//使用count查询，不存在时返回0
    printf("cnt=%d\n",cnt);

    auto it = unomap.find(mStudent1);//find查找
    if(it != unomap.end())
    {
        printf("value=%d\n",it->second);
        it->second = 10010;//修改
        unomap.erase(it);//使用迭代器删除
    }

    auto ret = unomap.erase(mStudent1);//使用key删除,如果没有找到返回0
    printf("ret=%lu\n",ret);

    auto it2 = unomap.find(mStudent2);
    if(it2 != unomap.end())
        printf("value=%d\n",it->second);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

打印

key=lucy,value=9527
key=tom,value=10086
value=9527
cnt=1
value=10086
ret=0
value=10010
1
2
3
4
5
6
7

C++自定义哈希表

实现思路:

1.定义节点,包含key和value和下一节点的指针(单链表);
2.定义固定大小的桶,桶内存放根据key计算得到相同hash值的节点;
3.如果存在哈希冲突,相同hash值的节点放入同一个桶内,用单链表存储.

#ifndef HASHTABLEDEF_H
#define HASHTABLEDEF_H

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <string>

using namespace std;

template <typename KEY, typename VALUE,  size_t TABLE_SIZE = 1000>
class HashTableDef
{
public:
    typedef struct HashNode//哈希节点
    {
        HashNode() {}
        HashNode(const KEY &key, const VALUE &val) :
            m_key(key), m_value(val), m_pNext(nullptr) { }
        KEY m_key;
        VALUE m_value;
        struct HashNode *m_pNext;//单链表，指向桶内下一个节点
    } Node, *pNode;

    HashTableDef() : m_nCnt(0),m_nSize(TABLE_SIZE)
    {
        for (size_t nIdx = 0; nIdx < TABLE_SIZE; ++nIdx)
        {
            m_pHashTable[nIdx] = nullptr;
        }
    }
    ~HashTableDef(){ReleaseTable();}

    //删除
    bool Delete(const KEY &key, const VALUE &val)
    {
        size_t nHash = 0;
        pNode pCurNode = nullptr;

        nHash = hash<KEY>{}(key) % TABLE_SIZE;// 计算hash值
        pCurNode = m_pHashTable[nHash];// 获取hash表头结点
        if (!pCurNode)
        {
            return(false);
        }
        while (pCurNode)
        {
            // 如果找到了结点
            if (pCurNode->m_key == key && pCurNode->m_value == val)
            {
                pNode pHeadNode = m_pHashTable[nHash];
                // 头结点的内容覆盖掉被删除的结点
                pCurNode->m_key = pHeadNode->m_key;
                pCurNode->m_value = pHeadNode->m_value;
                // 删除头结点
                m_pHashTable[nHash] = pHeadNode->m_pNext;
                delete pHeadNode;
                pHeadNode = nullptr;
                --m_nCnt;

                return(true);
            }
            pCurNode = pCurNode->m_pNext;
        }

        return(false);
    }

    // 插入
    bool Insert(const KEY &key, const VALUE &Value)
    {
        size_t nIdx = 0;
        pNode pNewNode = nullptr;
        //没有作查重处理,因此可以插入相同的键值对,可根据需求修改
        nIdx = hash<KEY>{}(key) % TABLE_SIZE;// 计算出key的hash值作为索引
        pNewNode = new Node(key, Value);// 分配新结点
        if (!pNewNode)
        {
            return(false);
        }

        if (m_pHashTable[nIdx])
        {
            // 如果桶内存在节点,则进行头插法插入
            pNewNode->m_pNext = m_pHashTable[nIdx]->m_pNext;
            m_pHashTable[nIdx]->m_pNext = pNewNode;
        }
        else
        {
            // 如果不存在则直接赋值给头结点
            m_pHashTable[nIdx] = pNewNode;
        }
        ++m_nCnt;

        return(true);
    }

    // 查找
    bool Find(const KEY &key, vector<VALUE> &rVecValue) const
    {
        size_t nHash = 0;
        pNode pCurNode = nullptr;

        nHash = hash<KEY>{}(key) % TABLE_SIZE;// 计算hash值
        pCurNode = m_pHashTable[nHash];// 获取hash表头结点
        if (!pCurNode)
        {
            return(false);
        }
        while (pCurNode)
        {
            if (pCurNode->m_key == key)
            {
                //key可以相同,出参是相同hash值的集合
                rVecValue.push_back(pCurNode->m_value);
            }
            pCurNode = pCurNode->m_pNext;
        }

        return(true);
    }

    // 遍历
    void PrintTable() const
    {
        for (size_t nIdx = 0; nIdx < TABLE_SIZE; ++nIdx)
        {
            if (m_pHashTable[nIdx])
            {
                pNode pCurNode = m_pHashTable[nIdx];
                cout << "key: " << /*nIdx*/pCurNode->m_key << endl;
                while (pCurNode)
                {
                    cout << "value: " << pCurNode->m_value << endl;
                    pCurNode = pCurNode->m_pNext;
                }
                cout << endl;
            }
        }
    }
private:
    // 释放表
    void ReleaseTable()
    {
        for (size_t nIdx = 0; nIdx < TABLE_SIZE; ++nIdx)
        {
            if (m_pHashTable[nIdx])
            {
                pNode pCurNode = m_pHashTable[nIdx];
                pNode pTmpNode = nullptr;
                while (pCurNode)
                {
                    pTmpNode = pCurNode->m_pNext;// 保存下一个结点
                    delete pCurNode;// 删除当前结点
                    pCurNode = nullptr;
                    pCurNode = pTmpNode;// 当前结点指向下一个结点
                }
                m_pHashTable[nIdx] = nullptr;
            }
        }
        m_nCnt = 0;
    }
private:
    Node *m_pHashTable[TABLE_SIZE];//哈希桶数组
    size_t m_nCnt;//存入节点总数量
    size_t m_nSize;//哈希表最大容量，桶的个数
};

#endif // HASHTABLEDEF_H

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172