unordered

unordered_map详解和性能分析

• unordered_map定义
• • unordered_map构造函数
  • unordered_map操作
  • • 插入
    • 删除
    • 查询
    • std::hash
    • • std::hash定义
      • std::hash使用
      • unordered_map自定义键值类型
      • • 自定义键和值类型
        • 实现哈希函数
        • • 哈希函数对象
          • 普通的哈希函数
          • lambda的哈希函数
          • unordered_map实现细节
          • unordered_map性能分析
          • • unordered_map桶的增加策略

              ---

              unordered_map定义

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

              template,
                  class Pred = std::equal_to,
                  class Alloc = std::allocator > > class unordered_map;
                  > class unordered_map
              

              unordered_map构造函数

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

              • 默认构造函数

                std::unordered_map myMap;
                

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

                • 初始桶数构造函数

                  std::unordered_map myMap(size_t n);
                  

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

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

                    std::unordered_map myMap(size_t n, const Hash& hashFunc);
                    

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

                    unordered_map操作

                    插入

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

                    #include #include int main() {
                        std::unordered_map 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;
                    }
                    

                    删除

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

                    #include #include int main() {
                        std::unordered_map 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;
                    }
                    

                    查询

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

                    #include #include int main() {
                        std::unordered_map 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;
                    }
                    

                    std::hash

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

                    std::hash定义

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

                    namespace std {
                      template struct hash {
                        std::size_t operator()(const T& key) const;
                      };
                    }
                    

                    std::hash是一个模板类，它接受一个类型参数T，用于指定需要哈希的对象类型。还提供了一个函数调用运算符（operator()），用于计算对象的哈希值。

                    perator()接受一个常量引用key，用于指定需要计算哈希值的对象。它返回一个std::size_t类型的哈希值，表示对象在哈希表中的桶位置。

                    std::hash使用

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

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

                      #include #include #include int main() {
                        std::string str = "Hello, world!";
                        std::hash hasher;
                        std::size_t hash_value = hasher(str);
                        std::cout << "The hash value of \"" << str << "\" is: " << hash_value << std::endl;
                        return 0;
                      }
                      

                      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;
                        };
                        

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

                        实现哈希函数

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

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

                          哈希函数对象

                          // 实现哈希函数对象
                          struct PersonHasher {
                              std::size_t operator()(const Person& person) const {
                                  std::size_t nameHash = std::hash()(person.name);
                                  std::size_t ageHash = std::hash()(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;
                          }
                          

                          普通的哈希函数

                          // 实现普通的哈希函数
                          size_t PersonHash(const Person& person) {
                              std::size_t nameHash = std::hash()(person.name);
                              std::size_t ageHash = std::hash()(person.age);
                              return nameHash ^ (ageHash << 1);
                          }
                          std::unordered_map<
                                  Person,
                                  PhoneNumber,
                                  std::function > phoneBook(100, PersonHashFun);
                          

                          这里phoneBook(100, PersonHashFun)用到的是std::unordered_map构造函数中的初始桶数和哈希函数构造函数。

                          std::function定义了一个函数对象类型：接收一个const Person&为参数，并返回一个size_t类型的函数或者函数对象。这里也可以采用decltype来声明这个函数对象类型：decltype(&PersonHashFun)。

                          lambda的哈希函数

                          std::unordered_map<
                                  Person,
                                  PhoneNumber,
                                  std::function > phoneBook(100, [] (const Person& person) -> size_t {
                              std::size_t nameHash = std::hash()(person.name);
                              std::size_t ageHash = std::hash()(person.age);
                              return nameHash ^ (ageHash << 1);
                          } );
                          

                          这里就不能采用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倍时会触发桶的重新分配。重新分配桶的过程比较耗时，因此应该尽量避免频繁的桶的重新分配。

                                ---