Библиотека Go для собеса | вопросы с собеседований

❓ Как работает пробинг в Swiss Table

1. Вычисляется хеш ключа (hash(key))
Используется aeshash (на поддерживаемых CPU) или memhash (на других архитектурах).
Определяется bucket: bucket_index = hash(key) % num_buckets.

2. Проверяется metadata (fingerprint) в bucket'е
Каждый bucket хранит 8 слотов, где хранятся fingerprints ключей.
Если fingerprint совпадает → проверяем полный ключ.

3. Если слот занят → применяется квадратичный пробинг:
next_index = (index + i²) % num_buckets
i увеличивается (1, 4, 9, 16...), что уменьшает кластеризацию.
Если после нескольких попыток элемент не найден → он отсутствует.

👍19

www.tgoop.com/go_interview_lib/745

2.87K viewsFeb 26 at 14:40

❓ Как работает пробинг в Swiss Table

1. Вычисляется хеш ключа (hash(key))
Используется aeshash (на поддерживаемых CPU) или memhash (на других архитектурах).
Определяется bucket: bucket_index = hash(key) % num_buckets.

2. Проверяется metadata (fingerprint) в bucket'е
Каждый bucket хранит 8 слотов, где хранятся fingerprints ключей.
Если fingerprint совпадает → проверяем полный ключ.

3. Если слот занят → применяется квадратичный пробинг:
next_index = (index + i²) % num_buckets
i увеличивается (1, 4, 9, 16...), что уменьшает кластеризацию.
Если после нескольких попыток элемент не найден → он отсутствует.

BY Библиотека Go для собеса | вопросы с собеседований