/¯
Ну значит, что память выделена, а в ней пусто (или мусор)
Хешмапа это вообще структура данных с вероятностными свойствами. Оценивать её надо опять же имея какие-то предположения на распределение данных
Size: a a a
2020 August 13
VK
(Есть ещё варианты с подкручиванием хеша одинаковым образом при вставке и поиске в случае коллизии и выбором другой ячейки, но суть примерно та же)
/¯
Она вроде хороша в "среднем" случае, и надо проследить, чтобы паттерн данных этому соответвовал
CC
Берётся от ключа хеш, по кусочку этого хеша выбирается ячейка
А я правильно понимаю, что пустая unordered_map занимает как минимум sizeof(void*) * (количество возможных хешей) байт?
/¯
Чтобы последовательность хеш-функции от данных была примерно равномерна
/¯
load_factor надо тоже подбирать, количество бакетов тоже
/¯
Доходило до того, что нейронку учили определять распределение данных, чтобы подкручивать хеш-функцию, и это работает
VK
А я правильно понимаю, что пустая unordered_map занимает как минимум sizeof(void*) * (количество возможных хешей) байт?
От хеш-функции, которая обычно size_t, берётся только несколько бит, чтобы ячеек было чуть больше, чем сейчас элементов
CC
От хеш-функции, которая обычно size_t, берётся только несколько бит, чтобы ячеек было чуть больше, чем сейчас элементов
А количество ячеек динамическое?
/¯
А количество ячеек динамическое?
Да
CC
Аааа, кажется, я таки понял, как работает unordered_map
/¯
И есть процедура рехешинга, которая заново делает бакеты
VK
А количество ячеек динамическое?
Но при расширении хеши считаются заново, то есть, вставляются в новую таблицу все элементы из старой по одному
CC
Но при расширении хеши считаются заново, то есть, вставляются в новую таблицу все элементы из старой по одному
А это зачем?
CC
Прост оставить их в старых ячейках и всё, не?
VK
Прост оставить их в старых ячейках и всё, не?
Если у тебя в старой таблице (с ёмкостью 8) хеш у ключа был 101, а в новой (с ёмкостью 16) 1101, то в новой ты по хешу 101 его не найдёшь
M
g++ юзай
Ок, буду пробовать, спасибо
IL
Аааа, кажется, я таки понял, как работает unordered_map
Но лучше прочитай что такое хэш-мапы
CC
Если у тебя в старой таблице (с ёмкостью 8) хеш у ключа был 101, а в новой (с ёмкостью 16) 1101, то в новой ты по хешу 101 его не найдёшь
А, примерно понятна проблема
/¯
Прост оставить их в старых ячейках и всё, не?
Есть foo и bar,
hash(foo) = 88005553535
hash(bar) = 225
Сначала у тебя 10 бакетов.
hash(foo) % 10 = 5
hash(bar) % 10 = 5
Теперь у тебя 100 бакетов
hash(foo) % 10 = 35
hash(bar) % 10 = 25
Ты не можешь и дальше foo и bar держать в одной корзине
hash(foo) = 88005553535
hash(bar) = 225
Сначала у тебя 10 бакетов.
hash(foo) % 10 = 5
hash(bar) % 10 = 5
Теперь у тебя 100 бакетов
hash(foo) % 10 = 35
hash(bar) % 10 = 25
Ты не можешь и дальше foo и bar держать в одной корзине