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

Question

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

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

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

поэтому для наивный хэш-функция, которая возвращает для ИНТ обертку только значение ИНТ члена это будет выглядеть следующим образом:

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; 
    } 
} 

Я ожидал, что выход

, но я получил:

4 
3 
2 
1 
0 

Почему?

Answer 1

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

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

Подробности ниже просто объяснить поведение версии GCC я посмотрел на ....

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

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 «s:

* 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 итераторов которых заказные соответствует к значениям хэша.

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

Answer 2

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