Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.77/13: Рейтинг темы: голосов - 13, средняя оценка - 4.77
0 / 0 / 0
Регистрация: 05.11.2015
Сообщений: 33
1

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

13.04.2019, 18:08. Просмотров 2586. Ответов 16

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

Сравниваю сложность вставки/поиска элемента в упорядоченных 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
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.04.2019, 18:08
Ответы с готовыми решениями:

Unordered_set и unordered_map
Добрый день. Объясните простыми словами отличия этих контейнеров от set и map. Не нашел простого...

Сложность операции в unordered_map
Везде пишут таблицы, в которых указывают, что сложность варьируется от О(1) до О(n) Но где найти...

Контейнер unordered_map<string, unordered_map<string,int>>
Ну можно и не unordered_map&lt;string, unordered_map&lt;string,int&gt;&gt;. Мне нужен контейнер который будет...

Как вычислять сложность алгоритма, или найти асимптотическую сложность любой программки?
Например Вычислить x^n по алгоритму быстрого возведения в степень Добавлено через 43 секунды...

16
13881 / 7417 / 1759
Регистрация: 30.01.2014
Сообщений: 12,409
13.04.2019, 18:36 2
Цитата Сообщение от dexterov Посмотреть сообщение
пока не найдем тот, который будет равен хешу строки "qwe"?
Это нужно будет делать только при возникновении коллизий, которые хорошая хеш-таблица старается минимизировать.

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

Цитата Сообщение от dexterov Посмотреть сообщение
Я понимаю, когда мы в массиве или векторе обращаемся по индексу - там идет прямое обращение к памяти по смещению от начала.
Тут так и есть, в среднем случае. По хешу вычисляется индекс и дальше как с обычным массивом.

Почитайте где-нибудь про устройство хеш-таблиц, чтобы ваши вопросы были более предметными.
2
Комп_Оратор)
Эксперт по математике/физике
8610 / 4327 / 584
Регистрация: 04.12.2011
Сообщений: 12,926
Записей в блоге: 14
13.04.2019, 18:58 3
Цитата Сообщение от dexterov Посмотреть сообщение
Но мне не понятно, почему, например, при поиске, сравнение в контейнере map<string, string> строчек ключа будет происходить НЕ так же, как сравнение хешей контейнера unordered_map<stringm string>.
В общем случае нет никакого сравнения. Вычисляется индекс. Другой вопрос, что для вычисления хеш-ключа минимально конфликтующего (минимизирующего вероятность коллизий как указал уважаемый DrOffset, ) нужно задействовать более сложную и медленную хеш-функцию. Хеширование строк, - тема интересная само по себе.
1
0 / 0 / 0
Регистрация: 05.11.2015
Сообщений: 33
13.04.2019, 20:23  [ТС] 4
Цитата Сообщение от 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", потом ищем этот хеш в таблице этой карты, но чтобы найти этот хеш, нам в общем случае надо просмотреть все элементы, как мы сразу извлечем элемент по хешу?

Случай с коллизиями я не беру в рассчет - там в целом ясно, что происходит.
0
Комп_Оратор)
Эксперт по математике/физике
8610 / 4327 / 584
Регистрация: 04.12.2011
Сообщений: 12,926
Записей в блоге: 14
13.04.2019, 20:30 5
Цитата Сообщение от dexterov Посмотреть сообщение
Разве нам не надо пройтись по всем хешам, чтобы найти нужный?
Не надо.

Добавлено через 2 минуты
Цитата Сообщение от dexterov Посмотреть сообщение
но чтобы найти этот хеш, нам в общем случае надо просмотреть все элементы
Хэш - в простейшем случае это индекс. Или в простой реализации делается целочисленное деление на размер массива (там под капотом массив списков (корзинок/цепочек)). То есть, доступ прямой. В этом и скорость. Проблемы возникают с коллизиями и скоростью хеширования и перехеширования.
0
0 / 0 / 0
Регистрация: 05.11.2015
Сообщений: 33
13.04.2019, 20:35  [ТС] 6
Цитата Сообщение от IGPIGP Посмотреть сообщение
Хэш - в простейшем случае это индекс.
Т.е. я правильно понимаю, что хеш для пары {"e", 3}, а именно для ключа "e" будет 3 (или 03, 003 - как-то так)? Или все же хеш - это результат криптографической функции, который возвращает случайное n-битное значение, зависящее целиком от входного значения?
0
Комп_Оратор)
Эксперт по математике/физике
8610 / 4327 / 584
Регистрация: 04.12.2011
Сообщений: 12,926
Записей в блоге: 14
13.04.2019, 20:44 7
Цитата Сообщение от dexterov Посмотреть сообщение
Т.е. я правильно понимаю, что хеш для пары {"e", 3}, а именно для ключа "e" будет 3 (или 03, 003 - как-то так)?
Вроде того. Если бы использовался тип char то можно было бы код символа использовать как индекс в массиве из 127. Тогда и вычислять ничего не нужно. И если ключи размажутся (хешинг - размазывание) равномерно то ок. А если нужны только строчные английские то размер массива - 26 а пересчёт кода в индекс и будет в данном разе хешфункцией. Очень простой. То есть, ни чего случайного тут нет и быть не может. Ведь "где-то там" положить, это "где-то там" и искать.
0
0 / 0 / 0
Регистрация: 05.11.2015
Сообщений: 33
13.04.2019, 20:50  [ТС] 8
Цитата Сообщение от IGPIGP Посмотреть сообщение
Вроде того. Если бы использовался тип char то можно было бы код символа использовать как индекс в массиве из 127. Тогда и вычислять ничего не нужно. И если ключи размажутся (хешинг - размазывание) равномерно то ок. А если нужны только строчные английские то размер массива - 26 а пересчёт кода в индекс и будет в данном разе хешфункцией. Очень простой. То есть, ни чего случайного тут нет и быть не может. Ведь "где-то там" положить, это "где-то там" и искать.
Хорошо, внутри контейнера для пары {"e", 3} хеш-значение будет соответствовать порядковому номеру и составлять, например, 03 - ок. А когда я пытаюсь обратиться к контейнеру с целью поиска значений по ключу строки "e". Как программа поймет, что входную строку "e" надо преобразовать в хеш-значение число 03?
0
Комп_Оратор)
Эксперт по математике/физике
8610 / 4327 / 584
Регистрация: 04.12.2011
Сообщений: 12,926
Записей в блоге: 14
13.04.2019, 20:52 9
Цитата Сообщение от dexterov Посмотреть сообщение
орошо, внутри контейнера для пары {"e", 3} хеш-значение будет соответствовать порядковому номеру и составлять, например, 03 - ок.
Не ок. Оно соответствует значению строки "e". И когда хеш-мапа пишет и когда читает она находит индекс по значению. Не попадёт в 2 разных места. Перечитайте предыдущий пост. В моём примере, целочисленное значение ключа используется как перечислитель индексов и да, тут всё подряд. Но это простой и частный случай.
под топиком - внизу экрана есть ссылки - пройдите и почитайте.
0
0 / 0 / 0
Регистрация: 05.11.2015
Сообщений: 33
13.04.2019, 21:00  [ТС] 10
Теперь я совсем запутался, что же является результатом работы хеш-функции для ключа контейнера? Как выглядит хеш для строки? Или где можно посмотреть пример реализации хеш-функции?
0
13881 / 7417 / 1759
Регистрация: 30.01.2014
Сообщений: 12,409
13.04.2019, 21:04 11
Цитата Сообщение от 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 Посмотреть сообщение
Или где можно посмотреть пример реализации хеш-функции?
Вопроса этого не видел, когда отвечал, но пример есть выше.
2
0 / 0 / 0
Регистрация: 05.11.2015
Сообщений: 33
13.04.2019, 21:11  [ТС] 12
Цитата Сообщение от DrOffset Посмотреть сообщение
Дальше значение, полученное после хеширования, трансформируется в индекс для одной из корзин (bucket) контейнера, которая по сути массив и есть. Непосредственное сравнение ключей производится только если одному хешу соответствует несколько элементов, в этом случае сложность превращается в O(n), где n количество коллизий.
Про коллизии понятно, там сложность О(n).
Не понятно вот это
Цитата Сообщение от DrOffset Посмотреть сообщение
Дальше значение, полученное после хеширования, трансформируется в индекс для одной из корзин (bucket) контейнера
Вот есть у нас значение после хеширования (видимо, 4-х байтное?), которое мы трансформируем в индекс, по которому находится искомая пара. Но как происходит преобразование результата хеширования в индекс?
0
13881 / 7417 / 1759
Регистрация: 30.01.2014
Сообщений: 12,409
13.04.2019, 21:34 13
Цитата Сообщение от dexterov Посмотреть сообщение
Но как происходит преобразование результата хеширования в индекс?
В каноническом случае - хеш - это и есть индекс. Но конкретно в unordered_map - это не так. Значение хеша (продукт функции, наподобие представленной выше) используется как ключ, к которому уже применяется один из методов:
* Метод остатка от деления.
* Метод умножения
* Метод исключающего ИЛИ
И др.
Какой конкретно применяется - зависит от реализации, нужно смотреть исходники.
Подробнее об этих методах я вам советую прочитать, например у Кнута или Кормена.
1
0 / 0 / 0
Регистрация: 05.11.2015
Сообщений: 33
13.04.2019, 21:49  [ТС] 14
Тогда, возвращаясь к сложности, если нам надо найти в контейнере 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-х байтный хеш мог использоваться для точечного обращения.
0
13881 / 7417 / 1759
Регистрация: 30.01.2014
Сообщений: 12,409
13.04.2019, 21:57 15
Лучший ответ Сообщение было отмечено dexterov как решение

Решение

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 - динамическое. Заканчивается место в существующих - выделяется еще один.
2
0 / 0 / 0
Регистрация: 05.11.2015
Сообщений: 33
13.04.2019, 22:14  [ТС] 16
Да, теперь понятно, получается n-байтный хеш преобразуется в пару маленьких чисел для индексации, что, по идее, сильно увеличивает вероятность возникновения коллизий. При превышении размера таблицы в процессе добавления новых элементов, видимо, все индексы каждый раз перенастраиваются?
0
13881 / 7417 / 1759
Регистрация: 30.01.2014
Сообщений: 12,409
13.04.2019, 22:32 17
dexterov, в unordered_map все несколько сложнее устроено - там другой метод используется. Предлагаю, если интересно, посмотреть самостоятельно. Я лишь передал общий принцип.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.04.2019, 22:32

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Порядок вставки элементов в unordered_set
#include &lt;iostream&gt; #include &lt;unordered_set&gt; using namespace std; int main() {...

Переделать код для unordered_set
Здравствуйте! У меня просьба к более опытным программистам данного форума. Можно ли как-то...

Работа с unordered_map
очень прошу помочь! имеется вот такой код: struct LOCATION { DATA_TYPE type; unsigned...

Hash_map unordered_map
class P{ public: int x, y; friend bool operator&lt; (const P u, const P v) { if(u.x &lt; v.x)...

Реализация контейнера unordered_map
Привет. Не могу найти реализацию этого контейнера. Помогите ссылкой или кодом.

Доступ к элементам unordered_map
struct Foo { int a,b,c; }; std::unordered_map&lt;std::pair&lt;int32_t, int32_t&gt;,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
17
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.