unordered_map详解和性能分析

---

unordered_map定义

std::unordered_map是C++标准库中的一个关联容器，它可以存储一组键值对，并且支持快速的查找、插入和删除操作。

template<class Key,
    class Ty,
    class Hash = std::hash<Key>,
    class Pred = std::equal_to<Key>,
    class Alloc = std::allocator<std::pair<const Key, Ty> > >
    class unordered_map;
    > class unordered_map
1
2
3
4
5
6
7

unordered_map构造函数

unordered_map比较重要的构造函数如下：

• 默认构造函数

std::unordered_map<Key, T> myMap;
1

创建一个空的unordered_map对象，键的类型为Key，值的类型为T。

• 初始桶数构造函数

std::unordered_map<Key, T> myMap(size_t n);
1

创建一个空的unordered_map对象，键的类型为Key，值的类型为T。这个构造函数会将unordered_map初始的桶数设置为n。

• 初始桶数和哈希函数构造函数

std::unordered_map<Key, T, Hash> myMap(size_t n, const Hash& hashFunc);
1

创建一个空的unordered_map对象，键的类型为Key，值的类型为T，并使用给定的哈希函数hashFunc。这个构造函数会将unordered_map初始的桶数设置为n。

unordered_map操作

插入

插入操作：使用insert或emplace方法可以向unordered_map中插入一个元素，其中insert方法接受一个pair对象，emplace方法接受一个可变参数模板参数列表。如果unordered_map中已经存在相同的关键字，则插入操作会失败。

#include <unordered_map>
#include <iostream>

int main() {
    std::unordered_map<std::string, int> my_map;

    // 插入元素
    my_map.insert(std::make_pair("foo", 42));
    my_map.emplace("bar", 99);

    // 输出元素
    std::cout << "foo: " << my_map["foo"] << std::endl;
    std::cout << "bar: " << my_map["bar"] << std::endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

删除

使用erase方法可以删除unordered_map中的一个或多个元素。erase方法接受一个迭代器或一个范围，或者接受一个关键字作为参数。如果关键字不存在，则删除操作会失败。

#include <unordered_map>
#include <iostream>

int main() {
    std::unordered_map<std::string, int> my_map;

    // 插入元素
    my_map.insert(std::make_pair("foo", 42));
    my_map.emplace("bar", 99);

    // 删除元素
    my_map.erase("foo");

    // 输出元素
    std::cout << "bar: " << my_map["bar"] << std::endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

查询

使用find方法可以在unordered_map中查找一个元素，如果找到了，则返回指向该元素的迭代器，否则返回unordered_map::end()。如果想要判断unordered_map中是否存在某个关键字，则可以使用count方法。

#include <unordered_map>
#include <iostream>

int main() {
    std::unordered_map<std::string, int> my_map;

    // 插入元素
    my_map.insert(std::make_pair("foo", 42));
    my_map.emplace("bar", 99);

    // 查询元素
    auto iter = my_map.find("foo");
    if (iter != my_map.end()) {
        std::cout << "foo: " << iter->second << std::endl;
    }

    if (my_map.count("baz")) {
        std::cout << "baz exists in my_map" << std::endl;
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

std::hash

std::hash 是C++标准库中用于计算哈希值的模板类，用于将对象映射到哈希表中的桶（bucket）中。

std::hash定义

std::hash的原型定义在头文件中，它是一个模板类，其原型如下：

namespace std {
  template<typename T>
  struct hash {
    std::size_t operator()(const T& key) const;
  };
}
1
2
3
4
5
6

std::hash是一个模板类，它接受一个类型参数T，用于指定需要哈希的对象类型。还提供了一个函数调用运算符（operator()），用于计算对象的哈希值。
perator()接受一个常量引用key，用于指定需要计算哈希值的对象。它返回一个std::size_t类型的哈希值，表示对象在哈希表中的桶位置。

std::hash使用

使用方法可以简单概括为以下几个步骤：

• 确定需要哈希的类型，可以是内置类型，也可以是自定义类型。
• 为该类型定义一个哈希函数，可以使用C++标准库提供的哈希函数，也可以自己实现一个哈希函数。
• 创建一个std::hash对象，并将需要哈希的对象作为参数传递给该对象的函数调用运算符（operator()）。
• 获得哈希值，可以使用std::size_t类型的std::hash对象的operator()函数返回的哈希值。

#include <iostream>
#include <string>
#include <functional>

int main() {
  std::string str = "Hello, world!";
  std::hash<std::string> hasher;
  std::size_t hash_value = hasher(str);
  std::cout << "The hash value of \"" << str << "\" is: " << hash_value << std::endl;
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11

unordered_map自定义键值类型

实现unordered_map的自定义键值类型，需以下步骤：

• 实现一个哈希函数，该函数将您的键类型映射到一个无符号整数，这将用于在哈希表中存储键值对。
• 实现一个等于运算符，该运算符将两个键进行比较，以检查它们是否相等。这是必需的，因为哈希表中的键值对需要根据键进行查找和比较，确认插入时，数据不重复。一般在自定义的键类型中重载operator==操作符。

自定义键和值类型

// 自定义键类型
class Person {
public:
    std::string name;
    int age;

    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

// 自定义值类型
class PhoneNumber {
public:
    std::string number;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

在自定义的键类型中，重载operator==()，进行两个键进行比较。

实现哈希函数

哈希函数的实现有三种方式：

• 实现一个哈希函数对象
• 实现一个普通的哈希函数
• 用lambda表达式实现哈希函数

哈希函数对象

// 实现哈希函数对象
struct PersonHasher {
    std::size_t operator()(const Person& person) const {
        std::size_t nameHash = std::hash<std::string>()(person.name);
        std::size_t ageHash = std::hash<int>()(person.age);
        return nameHash ^ (ageHash << 1);
    }
};

std::unordered_map<
        Person,         // key类型
        PhoneNumber,    // value类型
        PersonHasher    // 哈希函数对象
        > phoneBook;  //不需要把哈希函数传入构造器

// 添加键值对
phoneBook[{"Alice", 30}] = {"123-456-7890"};
phoneBook[{"Bob", 40}] = {"234-567-8901"};
// 查找键值对
auto aliceNumber = phoneBook.find({"Alice", 30});
if (aliceNumber != phoneBook.end()) {
    std::cout << "Alice's phone number is " << aliceNumber->second.number << std::endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

普通的哈希函数

// 实现普通的哈希函数
size_t PersonHash(const Person& person) {
    std::size_t nameHash = std::hash<std::string>()(person.name);
    std::size_t ageHash = std::hash<int>()(person.age);
    return nameHash ^ (ageHash << 1);
}
std::unordered_map<
        Person,
        PhoneNumber,
        std::function<size_t(const Person&)>
        > phoneBook(100, PersonHashFun);
1
2
3
4
5
6
7
8
9
10
11

这里phoneBook(100, PersonHashFun)用到的是std::unordered_map构造函数中的初始桶数和哈希函数构造函数。
std::function<size_t(const Person&)>定义了一个函数对象类型：接收一个const Person&为参数，并返回一个size_t类型的函数或者函数对象。这里也可以采用decltype来声明这个函数对象类型：decltype(&PersonHashFun)。

lambda的哈希函数

std::unordered_map<
        Person,
        PhoneNumber,
        std::function<size_t(const Person&)>
        > phoneBook(100, [] (const Person& person) -> size_t {
    std::size_t nameHash = std::hash<std::string>()(person.name);
    std::size_t ageHash = std::hash<int>()(person.age);
    return nameHash ^ (ageHash << 1);
} );
1
2
3
4
5
6
7
8
9

这里就不能采用decltype来声明这个函数对象类型了。

unordered_map实现细节

unordered_map的底层实现是哈希表，其具体实现细节如下：

• 哈希函数：unordered_map使用哈希函数将关键字映射到桶中，从而实现快速的查询和插入操作。C++标准库中提供了多个哈希函数，包括std::hash、std::hash_combine和std::hash_range等。用户也可以自定义哈希函数，只需要满足一定的要求，比如对于相同的关键字，哈希函数返回的值必须相同。

• 冲突处理：由于哈希函数的不完美性，可能会出现不同的关键字映射到同一个桶中的情况，这被称为哈希冲突。
  unordered_map解决冲突的方法主要有以下几种：

  链地址法（Chaining）：当发生哈希冲突时，将冲突的元素放入同一个桶中，以链表的形式串接起来。这种方法的优点是简单易实现，缺点是链表可能会很长，导致查询时间复杂度变高。
  

  开放地址法（Open Addressing）：当发生哈希冲突时，依次探查哈希表中的其他位置，直到找到一个空的位置为止。这种方法的优点是查询效率高，缺点是需要保证哈希表中有足够的空闲位置。

  建立更好的哈希函数：合适的哈希函数可以减少哈希冲突的发生，从而提高查询效率。可以考虑选择更复杂的哈希函数，如 SHA-1 等。

• 桶的大小：unordered_map会自动调整桶的大小，以保证哈希表的负载因子不超过某个预设值。负载因子是指哈希表中元素个数与桶的个数之比。当负载因子过高时，哈希冲突的概率会增大，影响性能。

• 迭代器：unordered_map的迭代器是前向迭代器，可以用于遍历所有元素。需要注意的是，由于哈希表的无序性，迭代器的顺序并不一定与元素的插入顺序相同。

unordered_map性能分析

std::unordered_map是一个哈希表实现的关联容器，它具有以下优点：

• O(1)的平均查找时间：由于哈希表使用哈希函数将键映射到桶中，查找元素的时间复杂度为O(1)，即平均需要常量时间查找元素。
• 高效的元素添加和删除：由于哈希表内部使用链表或红黑树来解决哈希冲突，因此在添加和删除元素时，只需要在对应桶的链表或红黑树中进行常量时间的操作。
• 适用于大规模数据：由于哈希表的查找时间复杂度为O(1)，因此它在处理大规模数据时表现良好，尤其是当键的范围很大时，比如对于字符串作为键的情况。
• 自定义键类型：哈希表可以处理自定义类型的键，只需要为该类型提供哈希函数和相等比较函数即可。

但是，std::unordered_map也存在以下一些缺点：

• 哈希表需要预先指定桶的数量和负载因子，当桶的数量或负载因子不合理时，会影响哈希表的性能。
• 哈希表的内存使用效率不高，因为哈希表需要维护桶数组和每个桶内的链表或红黑树，这会增加内存开销。
• 当哈希冲突较多时，哈希表的性能会下降，因为查找元素需要遍历桶内的链表或红黑树。
• 哈希表的迭代器不稳定，当哈希表的元素被添加或删除时，迭代器可能会失效。

总体来说，std::unordered_map是一个高效的关联容器，适用于大规模数据的处理，但是需要合理设置桶的数量和负载因子，并注意处理哈希冲突和迭代器失效的问题。

unordered_map桶的增加策略

std::unordered_map是一个哈希表实现的关联容器，它的内部实现包含一个桶（bucket）数组，每个桶中存放一个链表或红黑树。

当往unordered_map中添加元素时，它会首先将元素的键（key）通过哈希函数映射到某个桶上。如果该桶为空，则直接在该桶中插入新的键值对；如果该桶已经有元素，则遍历该桶中的链表或红黑树，找到合适的位置插入新的键值对。

为了保证unordered_map的性能，需要在创建unordered_map对象时指定桶的数量，桶的数量会影响哈希冲突的概率和查找元素的速度。如果桶的数量太少，会导致哈希冲突概率增加，导致链表或红黑树的长度增加，查找元素的时间复杂度变高；如果桶的数量太多，会浪费内存。

unordered_map的桶的增加策略一般是：
当元素的数量达到桶的负载因子（load factor）时，会重新分配桶的数量（桶的数量会按照原有桶的数量乘以2的方式进行扩容，即以2倍增长。但是，具体的增长策略也可以通过修改std::unordered_map的max_load_factor成员变量来进行调整。），并将所有元素重新哈希到新的桶中。
具体来说，当元素数量达到桶数量与负载因子的乘积时，会触发桶的重新分配。默认情况下，std::unordered_map的负载因子是0.75，即当元素数量达到桶数量的0.75倍时会触发桶的重新分配。重新分配桶的过程比较耗时，因此应该尽量避免频繁的桶的重新分配。

---