упорядочение элементов в хэш-таблице неупорядоченного множества

Question

упорядочение элементов в хэш-таблице неупорядоченного множества

Я запутался в хеш-таблице в неупорядоченных контейнерах … или, по крайней мере, в наборах.

Итак, я думал, что это будет работать так:

Я хеширую свой объект. Я вычисляю модуль длины объекта и вектора (hash% vectorlength) и использую его в качестве индекса для указателя на мой объект в хэш-таблице … который, насколько я знаю, является вектором …

так что для простой хеш-функции, которая возвращает для оболочки 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;
}
}

Я ожидал выход

но я получил:

Это почему?

1

c++hash hashtable order unordered

Решение

Другие решения

Вы ожидаете unordered Контейнер для заказа. У него нет определенного или гарантированного заказа. Как вы обнаружили, ваша реализация воспользовалась своей свободой и реализовала нечто иное, чем описанный вами простой дизайн хеш-таблицы. Другая реализация может сделать что-то еще. Вы не можете полагаться на это вообще.

1

Источник

Accepted Answer

Хотя реализации стандартной библиотеки могут делать все что угодно, также интересно посмотреть, где ваши предположения — и те, которые выражены в нескольких комментариях — соответствуют реальной реализации.

Я мог бы воспроизвести ваш результат «0 1 2 3 4» с помощью GCC, но только добавив map.reserve(6) или больше (странно, 5 произведено «4 0 1 2 3»).

Детали ниже просто объясняют поведение версии GCC, на которую я смотрел ….

Пытаясь найти объяснение, я сначала проверил, нет ли в логических контейнерах содержимого, подразумеваемого хэш-функцией:

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]

Итак, комментарий, предполагающий, что «Стандартная библиотека может свободно применять любую обратимую функцию поверх вашей хеш-функции, и никаких гарантий относительно порядка не дается» — хотя правда — не то, что здесь происходит.

Копаясь в заголовках стандартной библиотеки, я нашел причину в 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 организован с значения в односвязном списке, а в этот список помещается вектор итераторов, а не как обычно vector<forward_list<>>,

Когда вы вставляете элементы, они попадают в прямой список на передней панели., и это тот список, который вы повторяете при переходе от begin() в end()без какого-либо участия vector итераторов, порядок которых соответствует хеш-значениям.

Код Вот иллюстрирует, как итерация возвращает значения в обратном порядке вставки, независимо от хэшей / коллизий — пока достаточно места reserve()буду заранее, чтобы избежать перефразирования.

1