我想知道，unordered_set和unordered_map是如何在C++ STL中实现的？更准确地说：1.单个元素是否是节点的一部分，它们被连接成一个列表或一个连续元素的数组？1.所有的存储桶是否都并排分配在内存中？如果不是，那么迭代多个桶的逻辑是什么？1.在unordered_set和unordered_map中如何处理冲突？或者，他们不允许用户定义负载因子，并在此基础上创建一组全新的存储桶？
unordered_set
unordered_map
qncylg1j1#
基于它的接口，对unordered_(set|map)的期望至少相当接近直接链接的哈希表。也就是说，您可以从指针数组开始。这些指针中的每一个都指向一个桶，桶通常是节点的链表。我们可以从复杂性要求中推断出大部分这一点。特别地，当表被过度填充时，它从O（1）退化到O（N）的事实表明，在正常情况下（负载因子< 1）复杂度是基于对密钥进行散列以找到正确的桶。为了支持这一点，索引到bucket数组必须是O（1）操作。当表被过度填充时，复杂度退化为O（N）。这反映了遍历散列到同一桶的节点的链表的复杂性。指针失效规则也很有启发性。例如，一旦我们将一个项目插入到表中，即使我们执行了插入或删除其他节点之类的操作，指向该项目的指针仍然有效（并继续指向该节点）。因此，我们可以通过具有指向节点的指针的不同排列来将表作为一个整体重新排列，但是节点本身必须“保持不变”。这意味着我们不能（例如）将一个bucket实现为类似于std:vector<T>的东西--如果我们这样做了，当该向量被重新分配时，现有的指针将被无效。如果你真的很努力的话，你也许可以稍微偏离这一点，但是这样做并继续满足所有的需求变得相当困难（正如我最初写这篇文章的时候，我推测了几个小的变化可能是可能的，但在评论和更多的思考之后，我怀疑任何一个真的满足需求）。
unordered_(set|map)
std:vector<T>
w51jfk4q2#
单个元素是否是节点的一部分，它们被连接成一个列表或一个连续元素的数组？(see https://stackoverflow.com/a/31113618/410767解释了C标准如何有效地强制单独链接）单个元素（即键、unordered_map的值对、unordered_set的值）实际上被打包到节点中（例如在GCC的实现中，添加next指针/迭代器和键的散列记录，尽管后者是计算速度与内存使用的折衷，并且不是所有的实现都需要这样做; GCC对容器中的所有元素使用一个单链表，所以没有prev指针/迭代器，但其他实现可能有prev;如果没有prev，bucket需要指向第一个节点之前的节点，以便从bucket中删除最后一个元素时可以重新连接列表）。所有的存储桶是否都并排分配在内存中？如果不是，那么迭代多个桶的逻辑是什么？根据定义，基于哈希表的容器总是具有连续的随机访问的桶数组。但是，迭代不需要“在多个桶上”发生-在GCC的情况下，如上所述，有一个单链表可以直接迭代，独立于任何桶。这样做的一个主要优点是，如果你的容器容量很大，但大小很小，你仍然可以迭代O（size（））而不是O（bucket_count（））--我不确定后者是否符合标准（？）.如何在unordered_set和unordered_map中处理冲突？使用单独的链接（即通过将额外的节点插入到链表中）。或者，他们不允许用户定义负载因子，并在此基础上创建一组全新的存储桶？载荷系数仅与此相切。在一般情况下，不同键值的数量远远大于被存储的元素数量，并且您对将接收哪些密钥没有特别的了解，即使使用一个加密性强的哈希函数，您也需要N^2个桶的顺序，以便有50/50的机会将K个密钥放入表中而不会发生冲突。增加哈希表以避免冲突是不切实际的。在C中，加载因子由用户可设置的max_load_factor（默认值为1.0）限制，因此当加载因子超出时，实现会增长表。但载荷因子只与碰撞有概率关系。如果你好奇的话：如果你有K个密钥到B个桶中，没有冲突的概率是能够将每个连续密钥放到当时空桶中的概率的乘积，这取决于仍然空的桶的比例：B/B *（B-1）/B *（B-2）/B （B-3）/B … （B-K-1）/B。作为几个示例，对于2个桶中的2个密钥、6个桶中的3个密钥、10个桶中的4个、17个中的5个、24个中的6个、33个中的7个、43个中的8个、55个中的9个、69个中的10个、83个中的11个、100个中的12个、117个中的13个、136个中的14个、157个中的15个、157个中的15个、100个中的13个、100个中的13个密钥、10个中的4个、17个中的5个、24个、33个中的7个、33个、43个中的8个、43个中的8个、55个、55个中的9个、55个、69个中的10个、83个、10个中的8个、10个179中16、202中17、227中18、253中19、281中20、310中21、341中22、373中23、407中24、442中25、478中26、516中27、555中28、596中29、638中30、682中31 727年32人，773年33人，821年34人，870年35人，921年36人，974年37人，1027年38人，1082年39人，1139年40人，1197年41人，1257年42人，1317年43人，1380年44人，1444年45人，1509年46人，1576年47人，1644年48人，1713年49人，1784年50人，1857年51人，1931年52人，2006年53人，2083年54人，2161年55人，2241年56人，2322年57人，2405年58人，2489年59人，2574年60人，2661年61年61年，2749年62年，2839年63年，2930年64年，3023年65年，3117年66年，3213年67年，3310年68年，3408年69年，3508年70年，3609年71年，3712年72年，3816年73年，3922年74年，4029中的75、4137中的76、4247中的77、4359中的78、4472中的79、4586中的80、4702中的81、4819中的82、4938中的83、5058中的84、5179中的85、5302中的86、5427中的87、5552中的88、89在5680，90在5808，91在5939，92在6070，93在6203，94在6338，95在6474，96在6611，97在6750，98在6890，99在7032，100在7175……换句话说，对于100个密钥，我们需要有70.75个空桶，每1个使用中的桶才有>= 50%的机会不发生冲突，这将浪费大量内存，并确保使用中的桶分布在CPU缓存行上，使得桶访问（和一般CPU操作）慢得多。试图避免冲突，或者每次冲突发生时都重新散列，对于一般的散列表使用情况来说，这并不是一件值得注意的事情。也就是说， 完美散列 *（其中键散列到不同的桶）偶尔对于编译时已知的小组键或者当存在非常少量的可能键时既实用又可取。
next
prev
2条答案
按热度按时间qncylg1j1#
基于它的接口，对
unordered_(set|map)的期望至少相当接近直接链接的哈希表。也就是说，您可以从指针数组开始。这些指针中的每一个都指向一个桶，桶通常是节点的链表。
我们可以从复杂性要求中推断出大部分这一点。特别地，当表被过度填充时，它从O（1）退化到O（N）的事实表明，在正常情况下（负载因子< 1）复杂度是基于对密钥进行散列以找到正确的桶。为了支持这一点，索引到bucket数组必须是O（1）操作。
当表被过度填充时，复杂度退化为O（N）。这反映了遍历散列到同一桶的节点的链表的复杂性。
指针失效规则也很有启发性。例如，一旦我们将一个项目插入到表中，即使我们执行了插入或删除其他节点之类的操作，指向该项目的指针仍然有效（并继续指向该节点）。因此，我们可以通过具有指向节点的指针的不同排列来将表作为一个整体重新排列，但是节点本身必须“保持不变”。这意味着我们不能（例如）将一个bucket实现为类似于
std:vector<T>的东西--如果我们这样做了，当该向量被重新分配时，现有的指针将被无效。如果你真的很努力的话，你也许可以稍微偏离这一点，但是这样做并继续满足所有的需求变得相当困难（正如我最初写这篇文章的时候，我推测了几个小的变化可能是可能的，但在评论和更多的思考之后，我怀疑任何一个真的满足需求）。
w51jfk4q2#
单个元素是否是节点的一部分，它们被连接成一个列表或一个连续元素的数组？
(see https://stackoverflow.com/a/31113618/410767解释了C标准如何有效地强制单独链接）
单个元素（即键、
unordered_map的值对、unordered_set的值）实际上被打包到节点中（例如在GCC的实现中，添加next指针/迭代器和键的散列记录，尽管后者是计算速度与内存使用的折衷，并且不是所有的实现都需要这样做; GCC对容器中的所有元素使用一个单链表，所以没有prev指针/迭代器，但其他实现可能有prev;如果没有prev，bucket需要指向第一个节点之前的节点，以便从bucket中删除最后一个元素时可以重新连接列表）。所有的存储桶是否都并排分配在内存中？如果不是，那么迭代多个桶的逻辑是什么？
根据定义，基于哈希表的容器总是具有连续的随机访问的桶数组。但是，迭代不需要“在多个桶上”发生-在GCC的情况下，如上所述，有一个单链表可以直接迭代，独立于任何桶。这样做的一个主要优点是，如果你的容器容量很大，但大小很小，你仍然可以迭代O（size（））而不是O（bucket_count（））--我不确定后者是否符合标准（？）.
如何在unordered_set和unordered_map中处理冲突？
使用单独的链接（即通过将额外的节点插入到链表中）。
或者，他们不允许用户定义负载因子，并在此基础上创建一组全新的存储桶？
载荷系数仅与此相切。在一般情况下，不同键值的数量远远大于被存储的元素数量，并且您对将接收哪些密钥没有特别的了解，即使使用一个加密性强的哈希函数，您也需要N^2个桶的顺序，以便有50/50的机会将K个密钥放入表中而不会发生冲突。增加哈希表以避免冲突是不切实际的。在C中，加载因子由用户可设置的max_load_factor（默认值为1.0）限制，因此当加载因子超出时，实现会增长表。但载荷因子只与碰撞有概率关系。
如果你好奇的话：如果你有K个密钥到B个桶中，没有冲突的概率是能够将每个连续密钥放到当时空桶中的概率的乘积，这取决于仍然空的桶的比例：B/B *（B-1）/B *（B-2）/B （B-3）/B … （B-K-1）/B。作为几个示例，对于2个桶中的2个密钥、6个桶中的3个密钥、10个桶中的4个、17个中的5个、24个中的6个、33个中的7个、43个中的8个、55个中的9个、69个中的10个、83个中的11个、100个中的12个、117个中的13个、136个中的14个、157个中的15个、157个中的15个、100个中的13个、100个中的13个密钥、10个中的4个、17个中的5个、24个、33个中的7个、33个、43个中的8个、43个中的8个、55个、55个中的9个、55个、69个中的10个、83个、10个中的8个、10个179中16、202中17、227中18、253中19、281中20、310中21、341中22、373中23、407中24、442中25、478中26、516中27、555中28、596中29、638中30、682中31 727年32人，773年33人，821年34人，870年35人，921年36人，974年37人，1027年38人，1082年39人，1139年40人，1197年41人，1257年42人，1317年43人，1380年44人，1444年45人，1509年46人，1576年47人，1644年48人，1713年49人，1784年50人，1857年51人，1931年52人，2006年53人，2083年54人，2161年55人，2241年56人，2322年57人，2405年58人，2489年59人，2574年60人，2661年61年61年，2749年62年，2839年63年，2930年64年，3023年65年，3117年66年，3213年67年，3310年68年，3408年69年，3508年70年，3609年71年，3712年72年，3816年73年，3922年74年，4029中的75、4137中的76、4247中的77、4359中的78、4472中的79、4586中的80、4702中的81、4819中的82、4938中的83、5058中的84、5179中的85、5302中的86、5427中的87、5552中的88、89在5680，90在5808，91在5939，92在6070，93在6203，94在6338，95在6474，96在6611，97在6750，98在6890，99在7032，100在7175……
换句话说，对于100个密钥，我们需要有70.75个空桶，每1个使用中的桶才有>= 50%的机会不发生冲突，这将浪费大量内存，并确保使用中的桶分布在CPU缓存行上，使得桶访问（和一般CPU操作）慢得多。试图避免冲突，或者每次冲突发生时都重新散列，对于一般的散列表使用情况来说，这并不是一件值得注意的事情。也就是说， 完美散列 *（其中键散列到不同的桶）偶尔对于编译时已知的小组键或者当存在非常少量的可能键时既实用又可取。