https://vas3k.blog/blog/blockchain/#tranzaktsii
https://vas3k.blog/blog/ethereum/

Вообще офигенные статьи у Вась3к, рекомендую ознакомиться

https://docs.google.com/spreadsheets/d/1-UlA4-tslROBDS9IqHalWVztqZo7uxlCeKPQ-8uoFOU/edit?pli=1&gid=0#gid=0

Большая таблица протоколов передачи данных с информацией про их безопасность, поддержку, функционал и т.д.
Матрикс уверенно побеждает

Вот же людям делать нехуй

The absolute state of Meta‘s Threads

https://graphics.stanford.edu/~seander/bithacks.html

Прикольно. Оказывается, можно даже битхаком узнавать, присутствует ли в 32х битном числе байт с конкретным значением. За О(1), получается

https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/

Прикольно. Для 32х-битных x, n вместо x%n можно писать (uint64(x) * n) / 32, и это будет в 4 раза быстрее (если заменить деление на битшифт, конечно же)

Нет, хуйню спизданул. Делить не на 32, делить на 2^32, поскольку битшифт вправо на x тождественен делению на 2^х

Ладно. Это вообще не про модуль. Это про честность (непредвзятость) хэшмапы. Правда, в чём соль - так и не понял, если честно. Возможно, о том, чтобы таким образом бакеты индексировать, но не уверен. Целая наука это, хэшмапы.

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

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

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

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

Бакет (в коде именуется bmap) в исходниках определён, как структура, в которой находится только поле tophash типа [8]uint8. На самом деле, это довольно хитрая хуйня, потому что это не совсем так. После него на самом деле следуют 8 ключей и 8 значений, и указатель на тот самый overflow bucket в самом конце. Одним предложением я породил сразу 2 вопроса:
1) Почему там ещё и ключи сохраняются?
2) Почему ключи и значения идут отдельно, а не как 8 пар ключ-значение (вряд-ли он у вас возник, конечно, но это используется просто как подводка к коротенькому фанфакту)?

И если на второй вопрос ответить ещё просто (чтобы уменьшить траты на выравнивание - пара из int64 ключа и 8 uint8 значеня привела бы к 56 байтам выравнивания - а таких 8! И это только основной бакет!), то первый требует немного бэкграунда.

Коллизии
Коллизии - это когда хэшфункция для разных данных выдаёт одинаковый хэш (иными словами, такие a, b, a != b, что hash(a) == hash(b)). В общем случае этого, конечно, не избежать. Пускай и существуют perfect hash function, они же PHF, они же идеальные хэш-функции - их подбирают под очень конкретные и заранее известные ключи, поэтому эта штука в хэшмапах общего назначения - самый частый гость - едва ли применима.

Load factor
Понятие, часто всплывающие при малейшем рассмотрении кулуаров хэшмап. В сущности, просто нижний предел заполнения, после которого хэшмапа решает расширяться. Она-то и так расширяться должна, но это лучше делать не тогда, когда вот вообще прям каждый слот в каждом из бакетов заполнится - по понятным причинам. Чем ближе к заполнению, тем больше коллизии между нижними битами хэша, а плохо это потому, что...

Overflow buckets, its purpose and penalties
Как и было сказано, overflow бакеты формируют связный список. А это значит, что при лукапе значения нам придется теперь не только в основном бакете ключи перебирать, но и в новом. Поскольку overflow бакетов может быть произвольное количество (до тех пор, пока не стриггерит load factor ИЛИ их не станет чрезмерное количество - детальнее будет рассказано в секции "Рост"), то вместо 8 ключей нам может предстоять перебирать уже аж 30-40. Конечно, это амортизируется за счёт первичного сравнения по tophash (о котором будет сказано ниже), но это всё равно неприятно.

(у меня лимит по длине описания, поэтому прикреплю отдельно)

tophash
Выше было упомянуто, что это "единственное" поле бакета имеет тип [8]uint8. На самом деле, это многоцелевое поле, потому что сразу двум целям служит:
- Если значение элемента больше пяти - это верхние 8 бит (в противовес нижним для адресации) хэша хранящегося там ключа;
- Если же меньше пяти, то это так званое "специальное значение" - обозначая, к примеру, что слот для ключ-значения пустует, или сообщает об эвакуации (на самом деле, если бакет эвакуируется, то ВСЕ tophash значения будут выставлены в evacuated*, а не только конкретные слоты);


Из рационального невежества, я не планирую освещать тему эвакуации. В основном потому, что я в ней и сам не разобрался, да и не сильно желанием горю - мне главное саму концепцию себе спиздить.

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

Но помимо флагов, tophash выполняет ещё и очень полезную функцию. А именно - вместо того, чтобы напрямую сравнивать каждый ключ с искомым, мы сначала сверяем верхние байты их хэшей. Так сделано потому, что некоторые ключи сравнивать - очень дорого. Строки, например.

На 454 строке как раз и перебирают.

Рост
Мапа растёт в двух случаях:
- Когда load factor пересекает предел в среднем 6.5 элементов на бакет;
- Когда количество overflow buckets становится примерно равным количеству main buckets;

При том во втором случае, происходит так званый same size growth. К сожалению, я так и не понял, как он работает, и почему он триггерится раньше, чем по load factor. Но в теории, он должен как-то переставлять вхождения, чтобы меньше overflow бакетов использовать.