无序集哈希表中元素的排序

Question

我对无序容器中的散列table感到困惑……或者至少在集合中。

所以，我认为它会像这样工作：

我散列我的对象。我计算对象和向量长度的模数 (hash%vectorlength)，并将其用作散列 table 中指向我的对象的指针的索引。据我所知，这是一个向量...

所以对于一个简单的散列函数，returns 对于一个 int 包装器来说只是 int 成员的值，它看起来像这样：

hash table:

vector index:           [0, 1, 2, 3, 4]
                         |  |  |  |  |
object with value...:    0  1  2  3  4

我写了一个程序来测试：

#include <iostream>
#include <unordered_set>

struct Obj
{

public:

    Obj(int i)
    {
        mem = i;
    }

    friend bool operator==(const Obj& o1, const Obj& o2)
    {
        return (o1.mem == o2.mem);
    }

    friend std::ostream& operator<<(std::ostream& o, const Obj& obj)
    {
        o << obj.mem;
        return o;
    }

    int mem;

};

namespace std
{
    template<>
    struct hash<Obj>
    {
        size_t operator()(const Obj& r) const
        {
            size_t hash = r.mem;
            return hash;
        }
    };
}


int main()
{
    std::unordered_set<Obj> map;
    for (int i = 0; i < 5; ++i)
    {
        map.insert(Obj(i));
    }

    for(auto it = map.begin(); it != map.end(); ++it)
    {
        std::cout << (*it) << std::endl;
    }
}

我期望输出

但我得到了：

这是为什么？

Answer 1

您希望 unordered 容器有一个顺序。它没有任何指定或保证的顺序。正如您所发现的，您的实现利用了它的自由并实现了不同于您描述的朴素散列 table 设计的东西。另一个实现可能会做其他事情。你完全不能依赖它。

Answer 2

虽然标准库实现确实可以为所欲为，但看看您的假设（以及在几条评论中表达的假设）与实际实现的对应关系也很有趣。

我可以用 GCC 重现你的非“0 1 2 3 4”结果，但只能通过添加 map.reserve(6) 或更多（奇怪的是，5 产生“4 0 1 2 3”）。

下面的细节简单地解释了我查看的 GCC 版本的行为....

挖掘解释，我首先 sanity-checked 逻辑桶是否包含 hash-function-implied 内容：

for (size_t i = 0; i < map.bucket_count(); ++i)
{
    std::cout << '[' << i << ']';
    for (auto it = map.begin(i); it != map.end(i); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';
}

而且，他们确实做到了：

[0] 0
[1] 1
[2] 2
[3] 3
[4] 4
[5]
[6]

因此，建议 "the Standard Library is free to apply any invertible function on top of your hash function, and no guarantee whatsoever about ordering is given" 的评论 - 虽然是正确的 - 并不是这里发生的事情。

深入研究标准库 headers，我在 bits/hashtable.h 的文档中找到了原因：

* Here's _Hashtable data structure, each _Hashtable has:
* - _Bucket[]       _M_buckets
* - _Hash_node_base _M_before_begin
* - size_type       _M_bucket_count
* - size_type       _M_element_count
*
* with _Bucket being _Hash_node* and _Hash_node constaining:
* - _Hash_node*   _M_next
* - Tp            _M_value
* - size_t        _M_code if cache_hash_code is true
*
* In terms of Standard containers the hastable is like the aggregation  of:
* - std::forward_list<_Node> containing the elements
* - std::vector<std::forward_list<_Node>::iterator> representing the  buckets
*
* The non-empty buckets contain the node before the first bucket node. This
* design allow to implement something like a std::forward_list::insert_after
* on container insertion and std::forward_list::erase_after on container
* erase calls. _M_before_begin is equivalent to
* std::foward_list::before_begin. Empty buckets are containing nullptr.
* Note that one of the non-empty bucket contains &_M_before_begin which  is
* not a derefenrenceable node so the node pointers in buckets shall never be
* derefenrenced, only its next node can be.
*
* Walk through a bucket nodes require a check on the hash code to see if the
* node is still in the bucket. Such a design impose a quite efficient hash
* functor and is one of the reasons it is highly advise to set
* __cache_hash_code to true.
*
* The container iterators are simply built from nodes. This way  incrementing
* the iterator is perfectly efficient independent of how many empty buckets
* there are in the container.
*
* On insert we compute element hash code and thanks to it find the bucket
* index. If the element must be inserted on an empty bucket we add it at the
* beginning of the singly linked list and make the bucket point to
* _M_before_begin. The bucket that used to point to _M_before_begin, if any,
* is updated to point to its new before begin node.

因此，支撑 unordered_set 的散列 table 由 值组织在 singly-linked 列表中，桶是迭代器向量进入该列表，而不是通常设想的vector<forward_list<>>.

当您插入元素时，它们会进入前面的前向列表，并且当您在从 begin() 到 end()，没有任何迭代器的 vector 参与，其排序对应于哈希值。

代码 here 说明如何迭代 returns 值以相反的插入顺序，不考虑哈希/冲突 - 只要足够 space reserve()d up-front 避免重新散列.

无序集哈希表中元素的排序

ordering of elements in hashtable of unordered set

c++

hash

hashtable

unordered