Математическая сложность работы с unordered_map (unordered_set)

@dexterov · Регистрация: 05.11.2015

Студворк — интернет-сервис помощи студентам

Здравствуйте.

Сравниваю сложность вставки/поиска элемента в упорядоченных map/set и неупорядоченных unoredered_map/unordered_set.
Везде пишется, что при работе с неупорядоченным массивом операции поиска и вставки O(1) в общем случае, а в упорядоченном - O(log n). И преимущество неупорядоченных массивов сводится к использованию таблицы хешей.

Но мне не понятно, почему, например, при поиске, сравнение в контейнере map<string, string> строчек ключа будет происходить НЕ так же, как сравнение хешей контейнера unordered_map<stringm string>. Ведь сами значения хешей - это тоже текстовая строка, пусть и определенного типа. Я понимаю, когда мы в массиве или векторе обращаемся по индексу - там идет прямое обращение к памяти по смещению от начала. Но если, например, есть контейнер unordered_map<string, string>, то почему в нем поиск элемента будет за время O(1), ведь все равно, если нам нужно извлечь пару по ключу, например, "qwe", то мы должны посмотреть все хеши этого контейнера, пока не найдем тот, который будет равен хешу строки "qwe"?

@DrOffset · 13.04.2019, 18:36

Сообщение от dexterov

пока не найдем тот, который будет равен хешу строки "qwe"?

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

Сообщение от dexterov

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

Сами значения хешей - это таки обычно целые числа.

Сообщение от dexterov

Я понимаю, когда мы в массиве или векторе обращаемся по индексу - там идет прямое обращение к памяти по смещению от начала.

Тут так и есть, в среднем случае. По хешу вычисляется индекс и дальше как с обычным массивом.

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

IGPIGP · 13.04.2019, 18:58

Сообщение от dexterov

Но мне не понятно, почему, например, при поиске, сравнение в контейнере map<string, string> строчек ключа будет происходить НЕ так же, как сравнение хешей контейнера unordered_map<stringm string>.

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

@dexterov · 13.04.2019, 20:23 **[ТС]**

Сообщение от DrOffset

Тут так и есть, в среднем случае. По хешу вычисляется индекс и дальше как с обычным массивом.

А как по хешу вычисляется индекс? Разве нам не надо пройтись по всем хешам, чтобы найти нужный?

Добавлено через 5 минут
Например, есть 5 пар в unordered_map:

C++
1
unordered_map<string, int> m = {{"q", 1}, {"w", 2}, {"e", 3}, {"r", 4}, {"t", 5}};

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

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

IGPIGP · 13.04.2019, 20:30

Сообщение от dexterov

Разве нам не надо пройтись по всем хешам, чтобы найти нужный?

Не надо.

Добавлено через 2 минуты

Сообщение от dexterov

но чтобы найти этот хеш, нам в общем случае надо просмотреть все элементы

Хэш - в простейшем случае это индекс. Или в простой реализации делается целочисленное деление на размер массива (там под капотом массив списков (корзинок/цепочек)). То есть, доступ прямой. В этом и скорость. Проблемы возникают с коллизиями и скоростью хеширования и перехеширования.

@dexterov · 13.04.2019, 20:35 **[ТС]**

Сообщение от IGPIGP

Хэш - в простейшем случае это индекс.

Т.е. я правильно понимаю, что хеш для пары {"e", 3}, а именно для ключа "e" будет 3 (или 03, 003 - как-то так)? Или все же хеш - это результат криптографической функции, который возвращает случайное n-битное значение, зависящее целиком от входного значения?

IGPIGP · 13.04.2019, 20:44

Сообщение от dexterov

Т.е. я правильно понимаю, что хеш для пары {"e", 3}, а именно для ключа "e" будет 3 (или 03, 003 - как-то так)?

Вроде того. Если бы использовался тип char то можно было бы код символа использовать как индекс в массиве из 127. Тогда и вычислять ничего не нужно. И если ключи размажутся (хешинг - размазывание) равномерно то ок. А если нужны только строчные английские то размер массива - 26 а пересчёт кода в индекс и будет в данном разе хешфункцией. Очень простой. То есть, ни чего случайного тут нет и быть не может. Ведь "где-то там" положить, это "где-то там" и искать.

@dexterov · 13.04.2019, 20:50 **[ТС]**

Сообщение от IGPIGP

Вроде того. Если бы использовался тип char то можно было бы код символа использовать как индекс в массиве из 127. Тогда и вычислять ничего не нужно. И если ключи размажутся (хешинг - размазывание) равномерно то ок. А если нужны только строчные английские то размер массива - 26 а пересчёт кода в индекс и будет в данном разе хешфункцией. Очень простой. То есть, ни чего случайного тут нет и быть не может. Ведь "где-то там" положить, это "где-то там" и искать.

Хорошо, внутри контейнера для пары {"e", 3} хеш-значение будет соответствовать порядковому номеру и составлять, например, 03 - ок. А когда я пытаюсь обратиться к контейнеру с целью поиска значений по ключу строки "e". Как программа поймет, что входную строку "e" надо преобразовать в хеш-значение число 03?

IGPIGP · 13.04.2019, 20:52

Сообщение от dexterov

орошо, внутри контейнера для пары {"e", 3} хеш-значение будет соответствовать порядковому номеру и составлять, например, 03 - ок.

Не ок. Оно соответствует значению строки "e". И когда хеш-мапа пишет и когда читает она находит индекс по значению. Не попадёт в 2 разных места. Перечитайте предыдущий пост. В моём примере, целочисленное значение ключа используется как перечислитель индексов и да, тут всё подряд. Но это простой и частный случай.
под топиком - внизу экрана есть ссылки - пройдите и почитайте.

@dexterov · 13.04.2019, 21:00 **[ТС]**

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

@DrOffset · 13.04.2019, 21:04

Сообщение от dexterov

Разве нам не надо пройтись по всем хешам, чтобы найти нужный?

Нет.

Сообщение от dexterov

Т.е. я правильно понимаю, что хеш для пары {"e", 3}, а именно для ключа "e" будет 3 (или 03, 003 - как-то так)?

Нет.
3 - это, очевидно, значение.
А хеш для "e", это hash("e"), где hash - это некая функция хеширования. Например, она может быть такой:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
size_t hash_suffix(char c, size_t seed)
{
    return static_cast<size_t>(c) + 0x9e3779b9ul + (seed << 6) + (seed >> 2);
}
 
size_t hash(std::string const & str)
{
    size_t seed = 0;
    for(char c : str)
    {
        seed ^= hash_suffix(c, seed);
    }
    return seed;
}

* Это реализация из одной из версий boost; (boost::hash)

Дальше значение, полученное после хеширования, трансформируется в индекс для одной из корзин (bucket) контейнера, которая по сути массив и есть. Непосредственное сравнение ключей производится только если одному хешу соответствует несколько элементов, в этом случае сложность превращается в O(n), где n количество коллизий.

Добавлено через 2 минуты

Сообщение от dexterov

Как выглядит хеш для строки?

Как число.

Сообщение от dexterov

Или где можно посмотреть пример реализации хеш-функции?

Вопроса этого не видел, когда отвечал, но пример есть выше.

@dexterov · 13.04.2019, 21:11 **[ТС]**

Сообщение от DrOffset

Дальше значение, полученное после хеширования, трансформируется в индекс для одной из корзин (bucket) контейнера, которая по сути массив и есть. Непосредственное сравнение ключей производится только если одному хешу соответствует несколько элементов, в этом случае сложность превращается в O(n), где n количество коллизий.

Про коллизии понятно, там сложность О(n).
Не понятно вот это

Сообщение от DrOffset

Дальше значение, полученное после хеширования, трансформируется в индекс для одной из корзин (bucket) контейнера

Вот есть у нас значение после хеширования (видимо, 4-х байтное?), которое мы трансформируем в индекс, по которому находится искомая пара. Но как происходит преобразование результата хеширования в индекс?

@DrOffset · 13.04.2019, 21:34

Сообщение от dexterov

Но как происходит преобразование результата хеширования в индекс?

В каноническом случае - хеш - это и есть индекс. Но конкретно в unordered_map - это не так. Значение хеша (продукт функции, наподобие представленной выше) используется как ключ, к которому уже применяется один из методов:
* Метод остатка от деления.
* Метод умножения
* Метод исключающего ИЛИ
И др.
Какой конкретно применяется - зависит от реализации, нужно смотреть исходники.
Подробнее об этих методах я вам советую прочитать, например у Кнута или Кормена.

@dexterov · 13.04.2019, 21:49 **[ТС]**

Тогда, возвращаясь к сложности, если нам надо найти в контейнере unordered_map пару {"qwe", 123} по ключу "qwe". Тогда мы вычисляем хеш от строки "qwe", а дальше нам надо обратиться точно по индексу, где в контейнере лежит эта пара.
Но ведь это не значение int от 0 до 4, когда можно точечно обратиться как в массиве, это список из хеш-значений, как нам найти нужное хеш-значение за O(1)? Мы ведь не знаем, где именно оно располагается в списке хеш-значений среди остальных.

Добавлено через 5 минут
В википедии https://ru.wikipedia.org/wiki/... 1%86%D0%B0:

Получающееся хеш-значение i = hash ( k e y ) играет роль индекса в массиве H

Я не понимаю, как хеш-значение может быть индексом. Это ведь огромное 4-5 или 8-байтное число. Как оно может быть индексом для прямого обращения? У нас ведь не резервируется память для элементов от индекса 0x0 даже до индекса 0xFFFFFFFF, чтобы 4-х байтный хеш мог использоваться для точечного обращения.

@DrOffset · 13.04.2019, 21:57

dexterov,
Очень приблизительно и крайне упрощенно:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
size_t hash_suffix(char c, size_t seed)
{
    return static_cast<size_t>(c) + 0x9e3779b9ul + (seed << 6) + (seed >> 2);
}
 
size_t hash_value(std::string const & str)
{
    size_t seed = 0;
    for(char c : str)
    {
        seed ^= hash_suffix(c, seed);
    }
    return seed;
}
 
const size_t TableSize = 16;
const size_t Buckets = 4;
 
std::size_t table_offset(size_t k)
{
    return ((TableSize - 1) - (k % TableSize));
}
 
int main()
{
    int table[Buckets][TableSize] = {};
 
    std::string key = "e";
    int value = 3;
    
    size_t h = hash_value(key);
    
    size_t i = table_offset(h);
    
    size_t b = h % Buckets;
    
    table[b][i] = value;
}

Тут как раз метод остатка от деления.
Количество Buckets в unordered_map - динамическое. Заканчивается место в существующих - выделяется еще один.

@dexterov · 13.04.2019, 22:14 **[ТС]**

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

@DrOffset · 13.04.2019, 22:32

dexterov, в unordered_map все несколько сложнее устроено - там другой метод используется. Предлагаю, если интересно, посмотреть самостоятельно. Я лишь передал общий принцип.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@dexterov 0 / 0 / 0 Регистрация: 05.11.2015 Сообщений: 33

	Математическая сложность работы с unordered_map (unordered_set) 13.04.2019, 18:08. Показов 11880. Ответов 16 Метки unordered_map, unordered_set (Все метки) Здравствуйте. Сравниваю сложность вставки/поиска элемента в упорядоченных map/set и неупорядоченных unoredered_map/unordered_set. Везде пишется, что при работе с неупорядоченным массивом операции поиска и вставки O(1) в общем случае, а в упорядоченном - O(log n). И преимущество неупорядоченных массивов сводится к использованию таблицы хешей. Но мне не понятно, почему, например, при поиске, сравнение в контейнере map<string, string> строчек ключа будет происходить НЕ так же, как сравнение хешей контейнера unordered_map<stringm string>. Ведь сами значения хешей - это тоже текстовая строка, пусть и определенного типа. Я понимаю, когда мы в массиве или векторе обращаемся по индексу - там идет прямое обращение к памяти по смещению от начала. Но если, например, есть контейнер unordered_map<string, string>, то почему в нем поиск элемента будет за время O(1), ведь все равно, если нам нужно извлечь пару по ключу, например, "qwe", то мы должны посмотреть все хеши этого контейнера, пока не найдем тот, который будет равен хешу строки "qwe"? 0

@dexterov 0 / 0 / 0 Регистрация: 05.11.2015 Сообщений: 33
	13.04.2019, 21:00 [ТС]
	Теперь я совсем запутался, что же является результатом работы хеш-функции для ключа контейнера? Как выглядит хеш для строки? Или где можно посмотреть пример реализации хеш-функции? 0

@dexterov 0 / 0 / 0 Регистрация: 05.11.2015 Сообщений: 33
	13.04.2019, 22:14 [ТС]
	Да, теперь понятно, получается n-байтный хеш преобразуется в пару маленьких чисел для индексации, что, по идее, сильно увеличивает вероятность возникновения коллизий. При превышении размера таблицы в процессе добавления новых элементов, видимо, все индексы каждый раз перенастраиваются? 0

@DrOffset 19500 / 10105 / 2461 Регистрация: 30.01.2014 Сообщений: 17,816
	13.04.2019, 22:32
	dexterov, в unordered_map все несколько сложнее устроено - там другой метод используется. Предлагаю, если интересно, посмотреть самостоятельно. Я лишь передал общий принцип. 1

Математическая сложность работы с unordered_map (unordered_set)

Решение