Реализованной с помощью метода цепочек

Notation: пусть M - количество ячеек массива, N - общее количество ключей в хэш-таблице.

Издержки

Число исследований (probes) для поиска и вставки пропорционально $\frac{N}{M}$. ・Слишком большое M ⇒ слишком много пустых цепочек ・Слишком маленькое M ⇒ слишком длинные цепочки ・Практический результат: $\bf\frac{N}{M}\approx4$ ⇒ константное время операций

Цель

Средняя длинна цепи $\frac{N}{M}$ - константа. ・Удваиваем значение M когда $\frac{N}{M}$ ≥ 8. ・Делим пополам значение M когда $\frac{N}{M}$ ≤ 2. ・Повторное хэширование (rehash) после изменения размеров.

Algorithms (4th Edition) (March 24, 2011) Robert Sedgewick, Kevin Wayne. https://github.com/il-bychkov/algorithms

<aside> ℹ️ Число $\frac{N}{M}$ также называют load factor’ом хэш-таблицы. Это среднее количество элементов в цепочке.

</aside>

Реализованной на открытой адресации (массив)

Если такая хэш-таблица заполнилась на 80%-90% (можно менять), то необходимо сделать:

• resize: увеличиваем размер массива;
• rehash: mod q изменилось, теперь надо пересчитать хэши для элементов.

Если в хэш-таблице много удалённых элементов, то у нас linear probing слишком долго будет ходить вперёд по ячейкам удалённых элементов, пока наконец-то дойдёт до искомого или до незанятой. Чтобы это исправить, нужно сделать:

• rehash: тогда у нас не будет этих “пробелов” между элементами из-за операций удаления.

Также, если $\frac{M}{N}$ ≥ 8 (размер таблицы минимум в 8 раз больше количества элментов), то предлагается уменьшить размер массива вдвое.