具有相同散列的值是否在同一个桶的std :: unordered_map？ [英] Do values with same hash go in same bucket of std::unordered_map?

问题描述

如果std :: unordered_map的两个键具有相同的哈希值，那么标准保证它们将进入同一个桶中？我们假设根据模板等式谓词，键不相等，它们只有相同的哈希值。

If two keys for a std::unordered_map have the same hash value, is it guaranteed by the standard that they will go into the same bucket? We are assuming that the keys are not equal according to the template equality predicate, they only have the same hash value.

奖金问题：如果相同的哈希不意味着相同的桶，那么单独遍历桶的目的是什么？

Bonus question: If same hash does not imply same bucket, then what is the purpose of being able to traverse buckets individually?

推荐答案

具有相同散列的对象被放入同一个桶通过无序的关联容器。因此，两个相等的对象必须具有相同的散列。

Objects with the same hash are put into the same bucket by unordered associative containers. Consequently, two equal objects must have the same hash.

23.2.5第8段：

23.2.5 paragraph 8:

无序关联容器的元素被组织成桶。

The elements of an unordered associative container are organized into buckets. Keys with the same hash code appear in the same bucket.

奖金问题：为什么要单独遍历桶？

Bonus question: Why might you want to traverse buckets individually?

奖励答案：因为您想要并行处理容器的内容。 bucket迭代器是彼此独立的，因此每个线程可以处理一个bucket没有协调（假设没有新的条目添加到容器）。并且桶应该具有大致相同的大小，因此它们提供方便的并行化量子。

Bonus answer: Because you want to process the container's contents in parallel. The bucket iterators are independent of each other, so each thread can process a bucket without co-ordination (provided no new entries are added to the container). And the buckets should be roughly the same size, so they provide a convenient parallelisation quantum.

这篇关于具有相同散列的值是否在同一个桶的std :: unordered_map？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！