Как в std::unordered_multimap реализуется хранение пар с одинаковыми ключами?

#cpp

Я реализую аналог std::unordered_multimap, делаю это на C.

Меня интересует, каким образом в std::unordered_multimap (да и вообще) реализуется
хранение пар с одинаковыми ключами? Я покопался в исходниках, но шаблоны, умноженные
на инопланетные идентификаторы, исключают даже малейший шанс понять того, что там происходит
внутри.

Проблемы такие:

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

И это очень плохо.

2) Если хэширование происходит и по ключу, и по значению, тогда значения пар, уже
находящихся в таблице, нельзя будет изменять прямо на месте. Сперва их нужно будет
вырезать, затем изменять и потом вновь вставлять.

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

Ответы

Ответ 1

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

Средства итерирования по std::unordered_multimap гарантируют, что пары с одинаковым
ключом будут идти непрерывной последовательностью в процессе итерирования. Поэтому
как ни верти, разумная реализация будет вынуждена хранить их рядом.

Ни о каком хэшировании "и по ключу, и по значению" в std::unordered_multimap не может
быть и речи.