unordered_map действительно не заказан?
Я очень смущен именем 'unordered_map'. Имя предполагает, что ключи не заказаны вообще. Но я всегда думал, что им заказывает их значение хэш-функции. Или то, что неправильно (потому что имя подразумевает, что им не заказывают)?
Или помещать его отличающийся: это
typedef map<K, V, HashComp<K> > HashMap;
с
template<typename T>
struct HashComp {
bool operator<(const T& v1, const T& v2) const {
return hash<T>()(v1) < hash<T>()(v2);
}
};
то же как
typedef unordered_map<K, V> HashMap;
? (Хорошо, не точно, STL будет жаловаться здесь, потому что могут быть ключи k1, k2 и ни k1 <k2, ни k2 <k1. Необходимо было бы использовать multimap и перезапишите равную проверку.)
Или снова по-другому: Когда я выполняю итерации через них, я могу предположить, что ключевой список заказан их значением хэш-функции?
5 ответов
Отвечая на ваш отредактированный вопрос, нет, эти два фрагмента совсем не эквивалентны. std::map хранит узлы в древовидной структуре, unordered_map хранит их в hashtable*.
Ключи не хранятся в порядке их "хэш-значения", потому что они не хранятся в каком-либо порядке вообще. Вместо этого они хранятся в "ведрах", где каждое ведро соответствует диапазону хэш-значений. В основном, реализация выглядит так:
function add_value(object key, object value) {
int hash = key.getHash();
int bucket_index = hash % NUM_BUCKETS;
if (buckets[bucket_index] == null) {
buckets[bucket_index] = new linked_list();
}
buckets[bucket_index].add(new key_value(key, value));
}
function get_value(object key) {
int hash = key.getHash();
int bucket_index = hash % NUM_BUCKETS;
if (buckets[bucket_index] == null) {
return null;
}
foreach(key_value kv in buckets[bucket_index]) {
if (kv.key == key) {
return kv.value;
}
}
}
Очевидно, что это серьезное упрощение, и реальная реализация будет гораздо более продвинутой (например, поддержка изменения размера массива buckets, возможно, использование древовидной структуры вместо связанного списка для buckets, и так далее), но это должно дать представление о том, как вы не можете вернуть значения в каком-либо определенном порядке. Дополнительную информацию см. в википедии.
* Технически, внутренние реализации std::map и unordered_map определяются реализацией, но стандарт требует определенной сложности Big-O для операций, которая подразумевает эти внутренние реализации
Если вам нужна аналогия, посмотрите на выбранную вами РСУБД.
Если при выполнении запроса вы не указываете предложение ORDER BY, результаты возвращаются "неупорядоченными" - то есть в том порядке, который считает нужным база данных. Порядок не задан, и система вольна "упорядочивать" их как ей заблагорассудится, чтобы получить наилучшую производительность.
Вы правы, unordered_map на самом деле упорядочена по хэшу. Обратите внимание, что большинство современных реализаций (до TR1) называют ее hash_map.
В документации к компилятору IBM C/C++ отмечается, что если у вас есть оптимальная хэш-функция, то количество операций, выполняемых при поиске, вставке и удалении произвольного элемента, не зависит от количества элементов в последовательности, так что это означает, что порядок не такой уж неупорядоченный...
Теперь, что значит, что это хэш-упорядоченный? Поскольку хэш должен быть непредсказуемым, по определению вы не можете принять никакого предположения о порядке элементов в карте. Именно по этой причине в TR1 он был переименован: старое название предполагало порядок. Теперь мы знаем, что порядок действительно используется, но его можно игнорировать, поскольку он непредсказуем.
Как следует из названия unordered_map, стандарт C++0x не определяет никакого упорядочивания. Видимое упорядочивание неупорядоченной карты будет зависеть от того, что удобно для фактической реализации.
"Неупорядоченность" не означает, что где-то в реализации нет линейной последовательности. Это означает, что "вы не можете ничего предположить о порядке этих элементов".
Например, люди часто предполагают, что записи будут выходить из хэш-карты в том же порядке, в котором они были туда помещены. Но это не так, потому что записи неупорядочены.
Что касается "упорядоченности по их хэш-значению": хэш-значения обычно берутся из всего диапазона целых чисел, но в хэш-картах нет 2**32 слотов. Диапазон хэш-значения будет уменьшен до количества слотов, если взять его по модулю количества слотов. Кроме того, при добавлении записей в хэш-карту она может изменить размер, чтобы вместить новые значения. Это может привести к тому, что все предыдущие записи будут размещены заново, что изменит их порядок.
В неупорядоченной структуре данных вы не можете ничего предположить о порядке записей.