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

Наглядности ради, статья (можно ведь такой объём информации уже и статьей именовать?) будет разбита на серию постов, дабы прикладывать скрины кода там, где это имеет наибольший смысл. Ну, а ещё в проде всё наебнулось, и меня наебал caption size limit, поэтому скрины я вообще отдельными постами постфактумом постил.

Вкратце
Берём нижние n бит хэша значения, адресуем по ним бакет, и ищем в нём искомый ключ. Если при вставке новое значение попадает в уже заполненный бакет, аллоцируется overflow bucket и референс на него вставляется в конец образованного связного списка.

А теперь, хотелось бы всё же и поподробнее рассказать, что же там происходит.