Я изучаю хеш-таблицы и, в частности, квадратичное зондирование. Я читал, что если коэффициент загрузки ‹= 0,5, а размер таблицы простой, квадратичное зондирование всегда будет находить пустой слот, и к ключу не будет обращаться несколько раз. Далее говорится, что для обеспечения эффективной вставки я всегда должен поддерживать коэффициент загрузки ‹ = 0,5. Что это значит? Конечно, если мы будем продолжать добавлять элементы, коэффициент загрузки будет увеличиваться до тех пор, пока не станет равным 1, хотим мы этого или нет. Так что же подразумевается, когда мой учебник говорит, что я должен поддерживать небольшой коэффициент нагрузки?
Как сохранить небольшой коэффициент загрузки в моей хеш-таблице?
Ответы (1)
Подразумевается, что в какой-то момент (когда в этом случае вы превысите коэффициент загрузки 0,5) вам придется выделить новую таблицу (которая больше в какой-то раз, может быть, в 1,5 или 2, а затем округлить до ближайшее простое число) и скопируйте в нее все элементы из старой таблицы (это не прямая копия, новая позиция элемента обычно будет отличаться от старой позиции).
person
harold
schedule
31.05.2015
Эффективно ли это делать? Не лучше ли было бы в самом начале просто иметь большой стол? И есть ли какой-либо жаргон, связанный с этим значением?
- person aidandeno; 31.05.2015
@aidandeno неэффективно, когда он должен расти, но амортизированная стоимость добавления элемента по-прежнему составляет O (1) (по той же причине, что и со списками массивов). Если вы начнете с очень большой таблицы, рост будет меньше, но что, если вы все равно достигнете ее предела? И, конечно, это потенциально тратит впустую много места. Это действие по созданию новой таблицы большего размера называется перефразированием.
- person harold; 31.05.2015
@aidandeno Также, возможно, стоит отметить, что, хотя гигантская разреженная таблица, которая более чем вмещает все заранее, кажется меньшей работой по обработке, она может быть еще медленнее просто из-за меньшей пространственной локальности. Пространство и время не обязательно являются взаимоисключающими понятиями.
- person ; 31.05.2015
