Не подскажите, что из себя представляет bucket, который используется в

Question

Не подскажите, что из себя представляет bucket, который используется в

ассоциативных контейнерах?

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

#c #embedded #programming #russian

0

07.08.2023

17 ответов

22 просмотра

DI Автор вопроса

Разве кроме multimap/multiset версий, несколько значений поддерживаются в set/map?

0

07.08.2023

Aleksander Spichak

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

0

07.08.2023

Андрей Таусинов

там не про несколько значений, там про те пары, для которых совпал хэш

0

07.08.2023

Aleksander Spichak

DI
Разве кроме multimap/multiset версий, несколько зн...

Не зря я уточнил, что ключей. И именно после взятия по модулю от .size() контейнера

0

07.08.2023

Андрей Таусинов

Aleksander Spichak
кстати, это понятие актуально как для хеш таблиц с...

При открытой адресации бакеты одноместные, получается? Или выделяется некая "виртуальная"?

0

07.08.2023

Aleksander Spichak

Андрей Таусинов
При открытой адресации бакеты одноместные, получае...

Зависит же от метода разрешения колизий. Может быть и мапа в которой одноместные) А могут быть с множественным хешированием

0

07.08.2023

Aleksander Spichak

Андрей Таусинов
При открытой адресации бакеты одноместные, получае...

https://en.wikipedia.org/wiki/Hash_table#Collision_resolution

0

07.08.2023

DI Автор вопроса

Андрей Таусинов
там не про несколько значений, там про те пары, дл...

Понял. Спасибо

0

07.08.2023

Aleksander Spichak

Aleksander Spichak
https://en.wikipedia.org/wiki/Hash_table#Collision...

Там, кстати, интересный график есть, про сравнение кэш миссов

0

07.08.2023

Андрей Таусинов

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

0

07.08.2023

Aleksander Spichak

Андрей Таусинов
Чтобы тему закрыть заодно еще спрошу. При рехэширо...

Вовсе не обязательно перерасчитывать хеш, тут есть всякие оптимизации связанные с сохранением хеша (- по памяти, + по скорости) А вообще вопрос немного не понял)

0

07.08.2023

Aleksander Spichak

Андрей Таусинов
Чтобы тему закрыть заодно еще спрошу. При рехэширо...

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

0

07.08.2023

Андрей Таусинов

Aleksander Spichak
Вовсе не обязательно перерасчитывать хеш, тут есть...

казалось бы хранить хэш, дополнительно расходуя память, не совсем в духе с++) Вопрос в том, правильно ли я понял, что на пальцах происходит что-то такое. Т.е. в пределе сложность зависит не от количества элементов, а от количества корзин? Вроде, в этих двух подходах принципиальной разницы быть не должно с точки зрения рехэширования

0

07.08.2023

Aleksander Spichak

Нет, от количества элементов всё таки. Если до рехеширования A и B были в одном бакете, то совсем не факт, что после они будут так же в одном бакете

0

07.08.2023

Андрей Таусинов

Aleksander Spichak
Нет, от количества элементов всё таки. Если до рех...

А как мы можем гарантированно перемещаться только по элементам, минуя пустые корзины?

0

07.08.2023

Aleksander Spichak