Тема: Хеширование

Статья

Хеш-таблицы: хеш-функции, коллизии, открытая адресация

Как из массива и одной функции получается словарь с O(1) доступом: устройство хеш-функций, разрешение коллизий цепочками и открытой адресацией, load factor и …

#структуры данных#хеш-таблицы#хеширование

Статья

Строковые алгоритмы: KMP, Z-функция, Ахо–Корасик, хеширование

Как перестать сравнивать строки наивно: префикс-функция и KMP, Z-функция, автомат Ахо–Корасика для множества образцов, полиномиальное хеширование и его атаки — с кодом, …

#алгоритмы#строки#хеширование

Статья

Рандомизированные алгоритмы и вероятностный анализ

Почему подбрасывание монетки делает алгоритмы проще и быстрее: Las Vegas против Monte Carlo, индикаторы и линейность матожидания, границы Маркова, Чебышёва и Чернова, …

#алгоритмы#рандомизированные алгоритмы#вероятность

Статья

Прикладная криптография: симметрика, асимметрика, хеши, подписи, KDF

Как выбрать и правильно применить криптографический примитив: AEAD вместо самодельного шифрования, HMAC вместо хеша от секрета, HKDF вместо SHA-256 от пароля — и как …

#безопасность#криптография#шифрование

Статья

Вероятностные структуры: Bloom filter, HyperLogLog, Count-Min Sketch

Как обменять точность на память: устройство и математика фильтра Блума, HyperLogLog и Count-Min Sketch, их гарантии ошибок, рабочий код, границы применимости и место в …

#структуры данных#вероятностные структуры#потоковая обработка