Комментарии 8
Спасибо.
Зачем в такого типа тексте бенчмарки? — Правильно, незачем. Улучшили же! Виват!
Соответственно следующие 10 бит 0b1101100101→ указывают на группу внутри подтаблицы.
Разве не 10 младших бит?
удвоение количества групп в таблице происходит при достижении общей загрузки таблицы (load factor) в 81,25%
В предыдущей реализации load factor действительно был 6,5/8 =0,8125. Однако в свежей реализации его увеличили до 7/8 =0,875
“Ранее в Go для разрешения коллизий в хеш-таблицах использовался метод цепочек, при котором каждый бакет содержал указатель на связанный список элементов с одинаковым хеш-значением.» - ранее это насколько ранее? Мне вот это предложение не давало покоя. Насколько я помню, с go 1.8 в хеш - таблицах метод цепочек, предполагающий списки, уже не используется. Все хранится в одном большом массиве. И действительно:
Начиная с Go 1.8, реализация map в Go перешла с метода цепочек (связные списки в бакетах) на комбинацию открытой адресации и "bucket-ов"
Верно. Но если в bucket'е заканчивались слоты (а их было тоже 8), то динамически создавался т.н. overflow bucket, указатель на который хранился в "оригинальном" bucket'е с открытой адресацией. А если и в том заканчивались слоты, то цепочка overflow bucket'ов продолжалась.
Потому в отдельных случаях производительность map'ы сильно падала, так как "бегая" по таким overflow bucket'ам, получается random memory access и соответственно кэш миссы. Даже специальная оптимизация была, когда load factor map'ы ещё не достиг значения для её grow'инга, а кол-во overflow bucket'ов уже превысило лимит - в этом случае запускался regrow'инг, когда размер map'ы оставался тем же самым, но менялось значение seed'а для функции хэша. Это позволяло перераспределить ключи по bucket'ам и снизить кол-во overflow bucket'ов
А почему в пример с перемещением элементов: A: H1(A) & 0b1111 = 0b0011?
Вопрос. Как мы находим элемент, который был записан в групп 7 в данном примере:
1. Группа 5 заполнена → идём к группе 6.
2. Группа 6 заполнена → идём к группе 7.
3. Группа 7 свободная → записываем туда.
Если при получении хэша, мы получаем группу 5 и после не нахождения элемента в группе 5 мы заканчиваем поиск?
В случае неуспеха, возвращается значение по умолчанию для хранимого типа.
Go 1.24: принципы работы и преимущества обновленной map