Avalanche effect в хэш-функциях

Пустовато здесь, поэтому буду хоть какими-то филлерами прайм-тайм забивать. Пускай и хуже сформулированными вырезками из вики.

Avalanche effect (он же лавинный эффект) - это понятие из криптографии, применяющиеся обычно к хэш-функциям или симметричным шифрам. Суть заключается в том, чтобы малейшие изменения на входе давали значительные различия на выходе. Вот как SHA-*: поменяй одну буковку - и совершенно новый хэш. Хоть и хватило бы единственный бит флипнуть.



Интересно, а сюда можно как-нибудь эффект бабочки притянуть?

https://wilsoniumite.com/2025/01/21/weve-lost-our-respect-for-complexity/

TL;DR мы склонны недооценивать сложность. Практически всегда за практически всем стоит сложность, превышающая наши ожидания, и узнать о которой можно лишь испробовав самому. Прочувствовать изнутри, иными словами - к примеру, лишь поработав официантом, начнёшь действительно ценить их труд. Думаю, сюда же можно отнести совет поработать в общепите прежде, чем открывать собственное заведение.

Фактически - он на прикладном примере разделяет людей на тех, кто знает, о чём он НЕ знает, и на тех, кто НЕ знает, о чём он НЕ знает. А заодно - и выдвигает теорию, что эти две категории людей периодически сменяются: чаша весов, как синусоида - качается в разные стороны. И сейчас настала пора вторых.

Забавно. Проверил на индиге - оказывается, у меня самый старый файл - это гитигнор) У меня действительно не осталось ни единой строчки кода с тех времён, когда я только начинал писать проект. Интересно, а это уже новый проект, или всё ещё корабль Тесея?

Find the oldest line in your repo
Article, Comments

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 (о котором будет сказано ниже), но это всё равно неприятно.