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

Question

Для проекта я создаю хеш-таблицу строк. Он использует отдельную цепочку, и для каждой заполненной позиции в таблице создается связанный список. Этот связанный список содержит узел, который хранит строку, а также ее частоту. Итак, когда вставлена ​​строка:

1.) Если она соответствует хешу другой строки, а текущая строка НЕ ​​находится в таблице, она будет добавлена ​​к списку в этом хеш-значении и будет иметь частота 1.

2.) Если в таблице уже есть копия строки, частота этой строки будет увеличена.

Как рассчитать коэффициент нагрузки для этой таблицы? Будет ли это число узлов над общим числом позиций в хеш-таблице (это не включает списки). Или это будет сумма частот, деленная на количество позиций в хеш-таблице? -Спасибо!

Answer 1

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

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

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

Надеюсь, это поможет!