Почему карта будет намного быстрее, чем unordered_map?

Question

Я реализовал результаты кэширования поиска, которые состоят из ключей типа State (класс с 7 короткими целыми числами) и значений типа Socre (класс с 3 удваивается.) Использование unordered_map было как минимум в 20 раз медленнее, чем map. Почему?

Редактировать: Черт возьми! Моя хеш-функция была

namespace std {
    size_t hash<State>::operator()(State const& s) const {
        size_t retval = hash<short>()(s.s[0]);
        for (int i = 1; i < R; i += 2) {  // 1 3 5
            int x = (static_cast<int>(s.s[i + 1]) << 16)
                + (static_cast<int>(s.s[i]));
            hash_combine(retval, x);
        }
    }
}

Я забыл return retval, так что все сталкивалось! Мне бы хотелось, чтобы у unordered_map была функция hash_function_quality (), которая сообщает о среднем количестве коллизий.

Answer 1

Скорость unordered_map прямо пропорциональна скорости вашей функции хеширования.Это никогда не прямые отношения.Например, если вы используете простейшую функцию хеширования:

std::size_t myHash(MyObjectType _object){ return 1; }

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

Что нужно сделатьэто посмотреть на две вещи:

1. Какую функцию хеширования вы используете?Обрабатывается ли это смешное количество времени?
2. Сколько столкновений он производит?То есть, сколько уникальных элементов отображается в одно и то же хеш-значение?

Любой из них сам по себе может убить производительность.

Answer 2

std::unordered_map обычно медленный для небольшого числа элементов из-за хэш-функции. Это занимает фиксированное (-ише) количество времени, но, тем не менее, может занять значительное количество времени.

std::map, с другой стороны, проще, чем std::unordered_map. Время, необходимое для доступа к элементу, зависит от количества элементов, но все меньше и меньше с ростом количества элементов. И коэффициент big-oh c для std :: map обычно тоже очень мал по сравнению с std::unordered_map.

Как правило, предпочитайте использовать std::map вместо std::unordered_map, если только у вас нет особых причин использовать std::unordered_map. Это особенно актуально, если у вас нет большого количества элементов.

Answer 3

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

Answer 4

Для

Мне бы хотелось, чтобы у unordered_map была функция hash_function_quality (), которая сообщает о среднем количестве коллизий.

Я думаю, что следующая функция может быть полезной.*

unordered_map::load_factor
    float load_factor() const;
The member function returns the average number of elements per bucket.

Чем ниже load_factor, тем лучше хэш-функция.