Как правильно рассчитать коэффициент загрузки хеш-таблицы, которая использует отдельную цепочку?
Я работаю с хеш-таблицами, которые используют отдельную цепочку в качестве метода разрешения коллизий.
Я знаю, что общая формула имеет вид N / table_length, где N — это количество элементов в таблице.
Я немного смущен знаменателем. Будет ли это размер массива + количество связанных элементов или просто размер массива?
Решение
Цель коэффициент нагрузки состоит в том, чтобы дать представление о том, насколько вероятно (в среднем), что вам потребуется разрешение коллизий, если в таблицу будет добавлен новый элемент. Столкновение происходит, когда новому элементу назначается сегмент, в котором уже есть элемент. Вероятность того, что в данном сегменте уже есть элемент, зависит от количества элементов в контейнере.
load factor = # of elements / # of buckets
(В вашей терминологии: количество элементов в таблице, деленное на размер массива.)
Другие решения
Других решений пока нет …