boost :: unordered_map ... заказан?

Question

У меня есть boost :: unordered_map, но, похоже, он в порядке, давая мне подавляющее ощущение: «Ты делаешь это неправильно». Почему это результат в порядке? Я бы ожидал, что алгоритм хеширования лежащий в основе были рандомизированы этот порядок:

#include <iostream> 
#include <boost/unordered_map.hpp> 

int main() 
{ 
    boost::unordered_map<int, int> im; 

    for(int i = 0; i < 50; ++i) 
    { 
     im.insert(std::make_pair(i, i)); 
    } 

    boost::unordered_map<int, int>::const_iterator i; 

    for(i = im.begin(); i != im.end(); ++i) 
    { 
     std::cout << i->first << ", " << i->second << std::endl; 
    } 

    return 0; 
} 

... дает мне ...

0, 0 
1, 1 
2, 2 
... 
47, 47 
48, 48 
49, 49 

---

При рассмотрении исходного кода BOOST в:

inline std::size_t hash_value(int v) 
{ 
    return static_cast<std::size_t>(v); 
} 

... который объяснил бы это. В приведенных ниже ответах также содержится мнение более высокого уровня, которое я нашел полезным.

Answer 1

Пока я не могу говорить с бустерными внутренностями, как я не парень ++ C, я могу предложить несколько вопросов более высокого уровня, которые могут облегчить ваши проблемы:

1) Каковы гарантии соединяемых «неупорядоченная» карта? Скажем, у вас есть упорядоченная карта, и вы хотите создать карту, которая не гарантирует упорядочение. Первоначальная реализация может просто использовать упорядоченную карту. Это почти никогда не проблема, чтобы обеспечить более сильный гарантии, чем вы рекламируете.

2) Хеш-функция - это то, что хэши X -> int. Если у вас уже есть целое число, вы можете использовать функцию идентификации. Хотя он может быть не самым эффективным во всех случаях, он может объяснить поведение, которое вы видите.

В принципе, такое поведение, как это, не обязательно является проблемой.

Answer 2

Возможно, это связано с тем, что ваши хеши являются маленькими целыми числами. Таблицы хэшей обычно вычисляют количество ковша, в которое можно поместить элемент следующим образом: bucket_index = hash%p где p - это простое число, которое представляет собой число конусов хеш-таблицы, которое достаточно велико, чтобы обеспечить низкую частоту столкновений.

Для целых чисел hash равно значению целого числа. У вас много данных, поэтому хеш-таблица выбирает большой p. Для любого p, большего, чем i, bucket_index = i%p = i.

При итерации хэш-таблица возвращает элементы из своих ковшей в порядке их индексов, что для вас - это порядок ключей. :)

Попробуйте использовать большие цифры, если вы хотите увидеть какую-то случайность.

Answer 3

Вы делаете это правильно. unordered_map не претендует на случайный порядок. На самом деле, он не предъявляет никаких претензий к порядку. Вы не должны ожидать ничего в порядке, и это касается беспорядков!

Answer 4

Это потому, что карта по умолчанию упорядочена по порядку ввода ключей, если вы вставляете ключи 1,2,3,4,5 и печатаете ее, вы всегда получите 1,2,3,4,5 поэтому он выглядит упорядоченным. Попробуйте добавить значения случайных ключей и посмотреть результат. Это будет не каждый раз, как этого не должно быть.