Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
Undisputed
217 / 145 / 38
Регистрация: 10.06.2014
Сообщений: 1,704
Завершенные тесты: 3
1

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

14.01.2017, 20:19. Просмотров 1212. Ответов 17
Метки нет (Все метки)

Читаю книгу джосаттис стандартная библиотека c++, там в разделе про unordered_map есть описание данного контейнера
Неупорядоченные контейнеры обычно реализуются в виде хеш-таблицы(рис. 6.3). Таким образом, по существу, контейнер — это массив связанных списков. Позиция элемента в массиве вычисляется с помощью хеш-функции. Цель заключается в том, что бы каждый
элемент имел свою позицию, обеспечивающую к нему быстрый доступ, при условии быстрого вычисления хеш-функции. Однако, поскольку быстрые идеальныехеш-функциине не всегда возможны или могут потребовать огромный объем памяти для массива, разрешается хранить в одной и той же позиции несколько элементов. По этой причине элементами массива являются связанные списки, позволяющие хранить в одной позиции массива несколько элементов контейнера.
Раз уж каждый элемент массива внутри unordered_map является связанным списком и допускаются коллизии, то правильно ли я понимаю как это работает(добавление элемента в unordered_map, приблизительная реализация):
1. По хеш функции вычисляется индекс
2. В связанный список индекса сохраняется значение
3. В случае коллизии в next уже существующего значения для этого ключа добавляется новый элемент
4. В списке дополнительно хранится ключ-оригинал для каждого элемента (что бы при поиске с ним можно было сравнить тот ключ который попросил программист)

Т.е хочу узнать, в случае коллизий происходит ли итерация по списку в поисках соответствующего значения для ключа который попросил программист? А если элемент один - сразу он и возвращается. Я правильно понимаю?

Добавлено через 4 минуты
И ещё вот что интересно:
Зачем может понадобится повторное хеширование всей таблицы? Какой в этом смысл?
В книге сказано что если после удаления элемента происходит добавление - это может привести к повторному хешированию всей таблицы - это может произойти даже если занять через reserve много места? Или только если в таблице осталось всего 1 свободное место для вставляемого элемента после удаления?
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.01.2017, 20:19
Ответы с готовыми решениями:

Unordered_map правильное применение
Решил разобраться с этим контейнером, но не вижу ни одной комплексной сатьи по...

Каким образом изменить файл для загрузки в дочернем классе, если метод описан в родительском?
Доброго времени суток. У меня одна форма порождена от другой, и соответственно...

Каким образом можно настроить автозаполнение в mysql значения внешнего ключа в другой таблице?
Допустим, есть две таблицы. В одной первичный ключ объявлен в качестве...

Какое значение возвратит функция, если строка str задана следующим образом?
Форумчане, проконсультируйте, пожалуйста, что делаю неправильно! Какое...

Обход коллизии в хеш-таблице
Есть два файла, в первом написан словарь, второй открывает первый файл и...

17
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4837 / 2482 / 695
Регистрация: 18.10.2014
Сообщений: 4,290
14.01.2017, 20:31 2
Лучший ответ Сообщение было отмечено Undisputed как решение

Решение

Цитата Сообщение от sys_beginner Посмотреть сообщение
3. В случае коллизии в next уже существующего значения для этого ключа добавляется новый элемент
Куда именно в этом списке добавляется новый элемент - не оговаривается. Проще добавить в начало списка.

Цитата Сообщение от sys_beginner Посмотреть сообщение
В списке дополнительно хранится ключ-оригинал для каждого элемента (что бы при поиске с ним можно было сравнить тот ключ который попросил программист)
Разумеется. Каждый элемент unordered_map (в точности как и в map) - это пара ключ-данные.

Цитата Сообщение от sys_beginner Посмотреть сообщение
в случае коллизий происходит ли итерация по списку в поисках соответствующего значения для ключа который попросил программист?
Да, конечно.

Цитата Сообщение от sys_beginner Посмотреть сообщение
А если элемент один - сразу он и возвращается. Я правильно понимаю?
Почему это "сразу возвращается"? Программист может попросить несуществующий элемент. Поэтому даже если элемент один, все равно сначала будет выполняться проверка равенства ключей.

Цитата Сообщение от sys_beginner Посмотреть сообщение
Зачем может понадобится повторное хеширование всей таблицы? Какой в этом смысл?
При перебалансировке таблицы выполняется ее полное перестроение, при котором запросто может понадобиться повторное хеширование.

Цитата Сообщение от sys_beginner Посмотреть сообщение
книге сказано что если после удаления элемента происходит добавление - это может привести к повторному хешированию всей таблицы
Непонятно, о чем речь. Повторное хеширование всей таблицы выполняется при перестроении всей таблицы. Это происходит при вызове resize или reserve, которые делаются либо вами явно, либо автоматически при превышении load factor.
1
Байт
Эксперт C
19226 / 12351 / 2607
Регистрация: 24.12.2010
Сообщений: 25,424
14.01.2017, 20:34 3
Цитата Сообщение от sys_beginner Посмотреть сообщение
Я правильно понимаю?
В общих чертах, да.
1
Undisputed
217 / 145 / 38
Регистрация: 10.06.2014
Сообщений: 1,704
Завершенные тесты: 3
14.01.2017, 20:36  [ТС] 4
TheCalligrapher,
Понятно, спасибо!

А процесс rehash он что из себя представляет? Если рассуждать по логике то hash - это результат работы хеш функции.
Какой смысл заново хешировать уже созданные ключи и получать те же самые результаты?
Судя по всему чего то не понимаю...

Добавлено через 40 секунд
Байт,
Спасибо! Раз уж два человека подтвердили... значит я на правильном пути))
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4837 / 2482 / 695
Регистрация: 18.10.2014
Сообщений: 4,290
14.01.2017, 20:51 5
Цитата Сообщение от sys_beginner Посмотреть сообщение
Какой смысл заново хешировать уже созданные ключи и получать те же самые результаты?
Ну в самой очевидной реализации:

Вы изначально выделили внутри unordered_map внутреннюю таблицу (buckets, списки коллизий) размера N. Затем вы выполняете хэширование ключа каждого приходящего нового элемента и получаете значение хэша H. Вы не можете сразу использовать значение H для входа в таблицу размера N, ибо H никак не связано с N (Н может быть много больше, чем N). Поэтому внутри unordered_map обычно вычисляется I = H % N и индекс I используется как индекс конкретного bucket.

А потом вам вдруг захотелось/понадобилось увеличить величину N. Вы выделяете внутри unordered_map новую таблицу размера N2 (N2 > N). И теперь вам надо перебросить все существующие элементы из старой таблицы в новую - разбросать их по новому в новой таблице в надежде на то, что в новой таблице они распределятся равномерно (т.е. более тонким слоем). Для этого вам снова придется вычислить значение хэша H для каждого существующего элемента чтобы затем снова вычислить I = H % N2 - индекс bucket в новой таблице.

Значения H обычно нигде не хранятся, потому их в этом случае придется вычислять по новой, хоть они и не меняются.

Вот это перебрасывание элементов из старой таблицы в новую, другого размера - это и есть процесс rehash.

Если хранить вместе с каждым элементом еще и его значение хэша H, то тогда его можно будет не перевычислять во время rehash. Но на практике это не имеет особого смысла. Rehash - операция сравнительно редкая и перманентно тратить память ради ее оптмизации смысла нет.
1
Undisputed
217 / 145 / 38
Регистрация: 10.06.2014
Сообщений: 1,704
Завершенные тесты: 3
14.01.2017, 20:52  [ТС] 6
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Вы не можете сразу использовать занчение H для входа в таблицу размера N, ибо H может быть много больше, чем N.
А разве результат работы хеш функции как правило не выдает такой ключ, который находится в диапазоне от 0 до N?

Цитата Сообщение от TheCalligrapher Посмотреть сообщение
И теперь вам надо перебросить все существующие элементы из старой таблицы в новую
А зачем перебрасывать? Почему нельзя просто добавить кусок памяти для массива и не создавать копию уже существующего? Или так нельзя с массивами в С++?

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

Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Для этого вам снова придется вычислить значение H для каждого существующего элемента
Странно почему нельзя воспользоваться уже существующими индексами если мы увеличиваем размер таблицы а не уменьшаем
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4837 / 2482 / 695
Регистрация: 18.10.2014
Сообщений: 4,290
14.01.2017, 21:09 7
Цитата Сообщение от sys_beginner Посмотреть сообщение
А разве результат работы хеш функции как правило не выдает такой ключ, который находится в диапазоне от 0 до N?
Нет, конечно. Как? Функция хеширования для unordered_map вообще не знает и не хочет знать ничего о величине N. Функция хеширования просто генерирует некое произвольное хеш-значение типа size_t. А уж как потом это значение будет загоняться в диапазон N - это внутренняя деталь реализации unordered_map, о которой функции хеширования ничего не известно.

Цитата Сообщение от sys_beginner Посмотреть сообщение
А зачем перебрасывать? Почему нельзя просто добавить кусок памяти для массива и не создавать копию уже существующего?
Ну так вся цель выделения нового массива buckets - это более тонкое размазывание уже накопившихся элементов по более длинному массиву. Для этого, как ни крути, придется выполнить "переразмазывание" уже существующих элементов фактически с нуля.

Цитата Сообщение от sys_beginner Посмотреть сообщение
Всмысле равномерно? В хеш таблице же порядок не важен
Причем здесь порядок? Речь идет не о порядке, а о равномерности распределения по buckets.

Если элементы распределились по buckets равномерно и если общее количество элементов равно C, то в каждом bucket будет сидеть примерно C/N элементов. Эта величина называется load factor. Вот когда load factor становится слишком большим, т.е. списки в buckets, по которым приходится бегать линейным поиском, становятся слишком длинными, тогда мы можем просто увеличить величину N и тем самым уменьшить load factor (т.е. сделать списки более короткими). Вот для этого и делается rehash.

Чтобы все это работало, элементы должны разбрасываться по buckets равномерно. Порядок элементов тут ни при чем и никакой роли не играет.

Цитата Сообщение от sys_beginner Посмотреть сообщение
Странно почему нельзя воспользоваться уже существующими индексами если мы увеличиваем размер таблицы а не уменьшаем
Зачем тогда вообще было увеличивать размер таблицы? Весь смысл увеличения размера таблицы - получение тонкого размазывания элементов по таблице и, соответственно, уменьшения длины списков коллизий в каждом bucket.
1
Undisputed
217 / 145 / 38
Регистрация: 10.06.2014
Сообщений: 1,704
Завершенные тесты: 3
14.01.2017, 21:14  [ТС] 8
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Нет, конечно. Функция хеширования для unordered_map вообще не знает и не хочет знать ничего о величине N
Тогда получается что при каждом добавлении нового элемента его хеш может превысить N, и если там под капотом массив, то снова придется делать rehash? Как то стремно. Выходит изначально нельзя проконтролировать этот момент.
Хотелось бы иметь на руках реализацию где при соблюдении заранее известных правил исключить rehash.

Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Ну так вся цель выделения нового массива buckets - это более тонкое размазывание уже накопившихся элементов по более длинному массиву.
А когда мы пишем .reserve(N) просто выделяется N или более бакетов, так?

Так же интересно когда пишем unordered_map[key] = new_value - для старого значения вызывается delete или что то другое происходит?
0
Croessmah
++Ͻ
14777 / 8453 / 1605
Регистрация: 27.09.2012
Сообщений: 20,803
Записей в блоге: 2
Завершенные тесты: 1
14.01.2017, 21:18 9
sys_beginner, хеш-таблица служит для быстрого поиска, а не для быстрой вставки.


Последний парематр шаблона задает аллокатор.
Вот с его помощью и будет происходить создание/удаление объектов.
1
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4837 / 2482 / 695
Регистрация: 18.10.2014
Сообщений: 4,290
14.01.2017, 21:27 10
Цитата Сообщение от sys_beginner Посмотреть сообщение
Тогда получается что при каждом добавлении нового элемента его хеш может превысить N, и если там под капотом массив, то снова придется делать rehash? Как то стремно. Выходит изначально нельзя проконтролировать этот момент.
Ничего не понял. Величина хеша H никакой связи с величиной N не имеет. А внутри unordered_map всегда просто делается I = H % N. Где тут "стремно"? И где тут повод для rehash???

Цитата Сообщение от sys_beginner Посмотреть сообщение
Хотелось бы иметь на руках реализацию где при соблюдении заранее известных правил исключить rehash.
Автоматический rehash выполняется при превышении max load factor. Поставьте max load factor в огромную величину - и не будет вам никакого rehash. Вот и все.

Цитата Сообщение от sys_beginner Посмотреть сообщение
А когда мы пишем .reserve(N) просто выделяется или более бакетов, так?
reserve выделяет память под будущие бакеты, но сами бакеты не создает. Новые бакеты создает только rehash. Тут ситуация полностью аналогична reserve/resize в std::vector.

Цитата Сообщение от sys_beginner Посмотреть сообщение
Так же интересно когда пишем unordered_map[key] = new_value - для старого значения вызывается delete или что то другое происходит?
Какое delete? Зачем? Вы же сами открытым текстом видите, что для данных вызывается обычный оператор присваивания. Больше ничего делать не надо.
1
Undisputed
217 / 145 / 38
Регистрация: 10.06.2014
Сообщений: 1,704
Завершенные тесты: 3
14.01.2017, 21:31  [ТС] 11
TheCalligrapher,
Кажется я понял:
1. Вычисляется хеш входящего значения
2. Вычисляется индекс путем получения отстатка деления хеша на кол-во элементов
3. Результирующий индекс не превышает размер N

Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Поставьте max load factor в огромную величину - и не будет вам никакого rehash.
Судя по всему в таком случае бакеты будут расти, и добавится больше линейности

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

Добавлено через 2 минуты
Цитата Сообщение от sys_beginner Посмотреть сообщение
Судя по всему в таком случае бакеты будут расти, и добавится больше линейности
Для этого и делается rehash что бы уменьшить линейность при поиске. Я правильно понимаю?
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4837 / 2482 / 695
Регистрация: 18.10.2014
Сообщений: 4,290
14.01.2017, 21:40 12
Цитата Сообщение от sys_beginner Посмотреть сообщение
Кажется я понял:
1. Вычисляется хеш входящего значения
2. Вычисляется индекс путем получения отстатка деления хеша на кол-во элементов
3. Результирующий индекс не превышает размер N
Именно так.

Цитата Сообщение от sys_beginner Посмотреть сообщение
Судя по всему в таком случае бакеты будут расти, и добавился больше линейности
Совершенно верно. Это уже вам решать, как (и надо ли) бороться с этой линейностью: заранее выбирать достаточно большую величину N и не делать rehash, или рассчитывать на то, что N само будет увеличиваться "на лету" через rehash.

Цитата Сообщение от sys_beginner Посмотреть сообщение
Для этого и делается rehash что бы уменьшить линейность при поиске. Я правильно понимаю?
Да.

Цитата Сообщение от sys_beginner Посмотреть сообщение
Имелось ввиду что происходит под капотом
Ну так в том то и дело, что если элемент уже существует (что подразумевалось в вашем вопросе), то под капотом вообще ничего не происходит. Оператор [] просто находит элемент по ключу и возвращает ссылку на его данные. Все. Больше ничего не происходит. Никакого delete тут и близко нет.

А вы уже сами вызываете оператор присваивания с этой ссылкой в левой части.
1
Undisputed
217 / 145 / 38
Регистрация: 10.06.2014
Сообщений: 1,704
Завершенные тесты: 3
14.01.2017, 21:41  [ТС] 13
Спасибо!

Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Ну так в том то и дело, что если элемент уже существует (что подразумевалось в вашем вопросе), то под капотом вообще ничего не происходит. Оператор [] просто находит элемент по ключу и возвращает ссылку на его данные.
Ок а когда мы меняем старое значение на новое, просто та область памяти которая указывает на подходящий бакет перезаписывается новым значением без всяких delete и все?
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4837 / 2482 / 695
Регистрация: 18.10.2014
Сообщений: 4,290
14.01.2017, 21:55 14
Цитата Сообщение от sys_beginner Посмотреть сообщение
Ок а когда мы меняем старое значение на новое, просто та область памяти которая указывает на подходящий бакет перезаписывается новым значением?
Я не понимаю вопроса. Никакого "перезаписывания бакета" тут быть не может.

Еще раз: в unordered_map (как и в map) хранятся пары ключ-данные. При этом содержимое второй части пары - данные - вообще на структуру или функциональность unordered_map никак не влияет. Для unordered_map эти данные - "черный ящик", "мертвый груз", с которым unordered_map сам вообще никак не работает.

Когда вы делаете unordered_map[key] = data делается поиск элемента по ключу и вам просто возвращается ссылка на данные соответствующей пары ключ-данные. С этими данными через эту ссылку вы можете делать что вам угодно. Перезаписывайте их как угодно. Это ваши данные, и что вы с ними будете делать - до этого unordered_map нет никакого дела.

Никакие "бакеты" тут не перезаписываются и никаких изменений в структуре unordered_map при этом не происходит. На структуру unordered_map влияет только первая часть пары - ключ. Но ключ вам менять никто не даст. А данные - меняйте сколько угодно.
0
Undisputed
217 / 145 / 38
Регистрация: 10.06.2014
Сообщений: 1,704
Завершенные тесты: 3
14.01.2017, 22:03  [ТС] 15
TheCalligrapher,
Постараюсь объяснить более правильно что имел ввиду
1. Таблица состоит из бакетов(списков)
2. Каждый элемент бакета таблицы например std::unordered_map<int,double>ссылается на тип данных double
3. Допустим есть пара unordered_map[2] = 2.22
4. В какой то момент я пишу unordered_map[2] = 2.23
5. Что случится с 2.22 и где разместится 2.23? 2.23 сохранится в ту область памяти где было 2.22 тем самым перенакрыв его или произойдет delete той области где хранится 2.22 и будет new для 2.23?
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4837 / 2482 / 695
Регистрация: 18.10.2014
Сообщений: 4,290
14.01.2017, 22:12 16
Цитата Сообщение от sys_beginner Посмотреть сообщение
Таблица состоит из бакетов(списков)
Так.

Цитата Сообщение от sys_beginner Посмотреть сообщение
2. Каждый бакет таблицы например std::unordered_map<int,double>ссылается на тип данных double
Нет, конечно. Каждый бакет - это список пар типа std::pair<const int, double>.

Цитата Сообщение от sys_beginner Посмотреть сообщение
Допустим есть пара unordered_map[2] = 2.22
Допустим. Это значит, что в списке бакета, соответcтвующего ключу 2, есть пара { 2, 2.22 }.

Цитата Сообщение от sys_beginner Посмотреть сообщение
4. В какой то момент я пишу unordered_map[2] = 2.23
5. Что случится с 2.22 и где разместится 2.23? 2.23 сохранится в ту область памяти где было 2.22 тем самым перенакрыв его или произойдет delete той области где хранится 2.22 и будет new для 2.23?
Вызов unordered_map[2] выполнит обыкновенный поиск, найдет существующую пару { 2, 2.22 }, и вернет вам наружу ссылку типа double & на вторую часть этой пары.

После этого вы сами выполните присваивание = 2.23 и пара { 2, 2.22 } превратится в пару { 2, 2.23 }.

Никакого delete и никакого new при этом не было.

При этом сам unordered_map не знает и не хочет знать, что 2.22 поменялось на 2.23. Ему на это глубоко плевать.
1
Undisputed
217 / 145 / 38
Регистрация: 10.06.2014
Сообщений: 1,704
Завершенные тесты: 3
14.01.2017, 22:15  [ТС] 17
TheCalligrapher,
Отлично! Я понял, большое спасибо!!
0
Croessmah
++Ͻ
14777 / 8453 / 1605
Регистрация: 27.09.2012
Сообщений: 20,803
Записей в блоге: 2
Завершенные тесты: 1
14.01.2017, 22:18 18
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
и никакого new при этом не было.
Думаю, стоит уточнить, что это если элемент уже был в таблице (как в примере).
В ином случае для возврата ссылки его придется сначала создать.
0
14.01.2017, 22:18
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.01.2017, 22:18

Каким образом выполняется оператор "+" для ссылочных типов, если один из операндов равен null
Вопрос может показаться странным, но все же хотелось бы получить ответ. 1)...

Каким образом объявлена и определена функция на С
cm_send(pfrom, mes) int *pfrom; struct cm_mes *mes; { write(pfrom, mes,...

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


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

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

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