❓ Как работает пробинг в Swiss Table
1. Считается хеш ключа и делится на две части.
На поддерживаемых CPU используется aeshash, иначе — memhash. Полученный хеш разбивается на:
H1 (старшие 57 бит) — выбирает стартовую группу;
H2 (младшие 7 бит) — «отпечаток» (fingerprint) ключа.
2. Внутри группы контрольные байты проверяются параллельно через SIMD.
Каждая группа — это 8 слотов и 8-байтовый control word, где каждый байт хранит H2 своего слота. Одной SIMD-инструкцией H2 искомого ключа сравнивается сразу со всеми 8 байтами → получаем маску кандидатов. Только для совпавших по fingerprint слотов сверяется полный ключ.
3. Если совпадений нет и пустого слота в группе тоже нет — переходим к следующей группе.
Пробинг идёт по группам квадратично, но по треугольным числам:
offset = (offset + i) mod size, i = 1, 2, 3, 4...
→ смещения: h, h+1, h+3, h+6, h+10, ...
Такая последовательность гарантированно обходит всю таблицу (при размере — степени двойки) и снижает кластеризацию. Если встретился пустой слот — ключа в таблице нет, поиск останавливается.
🐸 Библиотека Go для собеса
1. Считается хеш ключа и делится на две части.
На поддерживаемых CPU используется aeshash, иначе — memhash. Полученный хеш разбивается на:
H1 (старшие 57 бит) — выбирает стартовую группу;
H2 (младшие 7 бит) — «отпечаток» (fingerprint) ключа.
2. Внутри группы контрольные байты проверяются параллельно через SIMD.
Каждая группа — это 8 слотов и 8-байтовый control word, где каждый байт хранит H2 своего слота. Одной SIMD-инструкцией H2 искомого ключа сравнивается сразу со всеми 8 байтами → получаем маску кандидатов. Только для совпавших по fingerprint слотов сверяется полный ключ.
3. Если совпадений нет и пустого слота в группе тоже нет — переходим к следующей группе.
Пробинг идёт по группам квадратично, но по треугольным числам:
offset = (offset + i) mod size, i = 1, 2, 3, 4...
→ смещения: h, h+1, h+3, h+6, h+10, ...
Такая последовательность гарантированно обходит всю таблицу (при размере — степени двойки) и снижает кластеризацию. Если встретился пустой слот — ключа в таблице нет, поиск останавливается.
🐸 Библиотека Go для собеса