повышение:: unordered_map является заказанным …?

У меня есть повышение:: 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

После исследования исходного кода повышения:

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

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

7
задан Thanatos 14 June 2010 в 18:47
поделиться

3 ответа

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

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

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

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

17
ответ дан 6 December 2019 в 06:35
поделиться

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

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

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

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

11
ответ дан 6 December 2019 в 06:35
поделиться

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

2
ответ дан 6 December 2019 в 06:35
поделиться
Другие вопросы по тегам:

Похожие вопросы: