深入剖析 std::unordered

您所在的位置：网站首页 › map解决hash冲突 › 深入剖析 std::unordered

深入剖析 std::unordered

2024-02-28 08:34| 来源: 网络整理| 查看: 265

本次来讲解下c++中 std::unordered_map的设计原理。

std::unordered_map里面has-a哈希表，它提供的的各个方法基本都是由hashtable封装实现，因此在下文使用hashtable来描述std::unordered_map。

// gnu 实现 template class unordered_map { typedef __umap_hashtable _Hashtable; _Hashtable _M_h; // 内部的唯一成员变量： hashtable //... } O(1)

数组，可以通过索引index在O(1)的时间复杂度内获取元素，但如果不知道index则要O(N)的时间复杂度来查找该节点。hashtable为了弥补这一缺点，采用一个hash函数来计算元素的索引值，来满足O(1)的搜索时间复杂度。其过程如下。

计算元素的哈希值。对于单个键值对{key, value}，计算key对应的哈希值 hashcode = hash_func(key) 。计算元素在数组中的索引值。由于hashcode不一定处于[0, bucket_count]范围内，因此需要将hashcode映射到该范围：index = hashcode % bucket_count。

上面两步以O(1)时间复杂度获取了元素在数组中的索引值index，进一步，则能以O(1)时间复杂度给该索引位置赋值或者获取该索引位置的值。两个步骤可实现如下：

size_t bucket_index(const std::unordered_map& map, int key) { size_t bucket_count = map.bucket_count(); // map 的桶的个数 const auto& hash_func = map.hash_function(); // hash函数 size_t hash_code = hash_func(key); // 计算hashcode // 键key将插入的桶位置 return hash_code % bucket_count; }

bucket_index函数时间复杂度是O(1)。在C++中，std::unordered_map提供的bucket(key)方法实现了相同的功能，即计算键key在数组中位置，下面可以验证下bucket_index(...) 的正确性。

int main(int argc, char const *argv[]) { std::unordered_map map(5); // 桶的大小为5 int key = 8; // 如果 bucket_index(map, key) != map.bucket(key)， // 会触发 abort 中断 assert( bucket_index(map, key) == map.bucket(key)); // 计算结果 std::cout

【本文地址】

深入剖析 std::unordered

深入剖析 std::unordered

今日新闻

推荐新闻