Как происходит расширение (рехэш) в Swiss Tables?

В Swiss Tables (используемых, например, в реализации хеш-таблиц в Go) расширение таблицы происходит через увеличение размера массива бакетов и перераспределение элементов с новым хешированием.

Особенность Swiss Tables — хранение метаданных (например, контрольных сумм хешей) рядом с ключами для ускорения поиска и уменьшения коллизий. При расширении:

1. Размер таблицы увеличивается, обычно вдвое.
2. Все существующие элементы перебрасываются в новую таблицу с учётом нового размера.
3. Используется оптимизированный алгоритм рехэширования, который минимизирует количество операций и копирований.

Это позволяет сохранить высокую производительность операций вставки и поиска даже при росте количества элементов.

Примерно так выглядит упрощённый псевдокод расширения:

func (t *SwissTable) resize() {
    newSize := t.size * 2
    newTable := make([]bucket, newSize)
    for _, bucket := range t.buckets {
        for _, entry := range bucket.entries {
            newIndex := hash(entry.key) % newSize
            newTable[newIndex].add(entry)
        }
    }
    t.buckets = newTable
    t.size = newSize
}