Математическая сложность работы с 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++

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++

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 все несколько сложнее устроено - там другой метод используется. Предлагаю, если интересно, посмотреть самостоятельно. Я лишь передал общий принцип.

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

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

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

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 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

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

@dexterov 0 / 0 / 0 Регистрация: 05.11.2015 Сообщений: 33
	13.04.2019, 20:35 [ТС]	6
	Сообщение от IGPIGP Хэш - в простейшем случае это индекс. Т.е. я правильно понимаю, что хеш для пары {"e", 3}, а именно для ключа "e" будет 3 (или 03, 003 - как-то так)? Или все же хеш - это результат криптографической функции, который возвращает случайное n-битное значение, зависящее целиком от входного значения? 0

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 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

@dexterov 0 / 0 / 0 Регистрация: 05.11.2015 Сообщений: 33
	13.04.2019, 20:50 [ТС]	8
	Сообщение от IGPIGP Вроде того. Если бы использовался тип char то можно было бы код символа использовать как индекс в массиве из 127. Тогда и вычислять ничего не нужно. И если ключи размажутся (хешинг - размазывание) равномерно то ок. А если нужны только строчные английские то размер массива - 26 а пересчёт кода в индекс и будет в данном разе хешфункцией. Очень простой. То есть, ни чего случайного тут нет и быть не может. Ведь "где-то там" положить, это "где-то там" и искать. Хорошо, внутри контейнера для пары {"e", 3} хеш-значение будет соответствовать порядковому номеру и составлять, например, 03 - ок. А когда я пытаюсь обратиться к контейнеру с целью поиска значений по ключу строки "e". Как программа поймет, что входную строку "e" надо преобразовать в хеш-значение число 03? 0

IGPIGP Комп_Оратор) $Эксперт по математике/физике$ 8610 / 4327 / 584 Регистрация: 04.12.2011 Сообщений: 12,926 Записей в блоге: 14
	13.04.2019, 20:52	9
	Сообщение от dexterov орошо, внутри контейнера для пары {"e", 3} хеш-значение будет соответствовать порядковому номеру и составлять, например, 03 - ок. Не ок. Оно соответствует значению строки "e". И когда хеш-мапа пишет и когда читает она находит индекс по значению. Не попадёт в 2 разных места. Перечитайте предыдущий пост. В моём примере, целочисленное значение ключа используется как перечислитель индексов и да, тут всё подряд. Но это простой и частный случай. под топиком - внизу экрана есть ссылки - пройдите и почитайте. 0

@dexterov 0 / 0 / 0 Регистрация: 05.11.2015 Сообщений: 33
	13.04.2019, 21:11 [ТС]	12
	Сообщение от DrOffset Дальше значение, полученное после хеширования, трансформируется в индекс для одной из корзин (bucket) контейнера, которая по сути массив и есть. Непосредственное сравнение ключей производится только если одному хешу соответствует несколько элементов, в этом случае сложность превращается в O(n), где n количество коллизий. Про коллизии понятно, там сложность О(n). Не понятно вот это Сообщение от DrOffset Дальше значение, полученное после хеширования, трансформируется в индекс для одной из корзин (bucket) контейнера Вот есть у нас значение после хеширования (видимо, 4-х байтное?), которое мы трансформируем в индекс, по которому находится искомая пара. Но как происходит преобразование результата хеширования в индекс? 0

@DrOffset 13881 / 7417 / 1759 Регистрация: 30.01.2014 Сообщений: 12,409
	13.04.2019, 21:34	13
	Сообщение от dexterov Но как происходит преобразование результата хеширования в индекс? В каноническом случае - хеш - это и есть индекс. Но конкретно в unordered_map - это не так. Значение хеша (продукт функции, наподобие представленной выше) используется как ключ, к которому уже применяется один из методов: * Метод остатка от деления. * Метод умножения * Метод исключающего ИЛИ И др. Какой конкретно применяется - зависит от реализации, нужно смотреть исходники. Подробнее об этих методах я вам советую прочитать, например у Кнута или Кормена. 1

@dexterov 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

Опции темы

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

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

Решение