Как правильно рассчитать коэффициент загрузки хеш-таблицы, которая использует отдельную цепочку?

Question

Я работаю с хеш-таблицами, которые используют отдельную цепочку в качестве метода разрешения коллизий.

Я знаю, что общая формула имеет вид N / table_length, где N - это число элементов в таблице.

Меня немного смущает знаменатель. Будет ли это размер массива + количество связанных элементов или просто размер массива?

Answer 1

Цель коэффициента загрузки состоит в том, чтобы дать представление о том, насколько вероятно (в среднем), что вам потребуется разрешение коллизий, если в таблицу добавлен новый элемент. Столкновение происходит, когда новому элементу назначается сегмент, в котором уже есть элемент. Вероятность того, что в данном сегменте уже есть элемент, зависит от количества элементов в контейнере.

load factor = # of elements / # of buckets

(В вашей терминологии: количество элементов в таблице, деленное на размер массива.)