Modern Perfect Hashing
Автор обсуждает реализацию идеального хеширования для строк, где известный набор строк отображается в целые числа с отверганием остальных. Критикуется подход с использованием PEXT (из-за больших таблиц, отсутствия на ARM и медленной работы на старых x86), предлагается альтернатива из шахматного программирования — "магические битборды". Метод заключается в умножении значения на магическое число (например, 0x28400000U) и сдвиге верхних бит для получения уникальных индексов. Для строк длиной 4 символа это позволяет создать компактную таблицу с 10 записями, где проверка memcmp гарантирует отсутствие ложных срабатываний.
Для строк разной длины можно выбирать различные битовые диапазоны (16, 32 или 64 бита) или их комбинации. В удачных случаях, как с 24-символьными CSS-ключами, удается найти магическое число, дающее прямую индексацию без промежуточной таблицы. Авторы предпочитают меньшие типы данных для компактности кода и возможности перебора вместо случайного поиска. Подход эффективен для наборов в тысячи строк с допустимым временем компиляции.