Как сохранить небольшой коэффициент загрузки в моей хэш-таблице?

Question

Как сохранить небольшой коэффициент загрузки в моей хэш-таблице?

Я изучаю хеш-таблицы и, в частности, квадратичное зондирование. Я читал, что если коэффициент загрузки <= 0,5 и размер таблицы прост, квадратичное зондирование всегда найдет пустой слот, и ни один ключ не будет доступен несколько раз. Далее говорится, что для обеспечения эффективных вставок я всегда должен поддерживать коэффициент загрузки <= 0,5. Что это значит? Конечно, если мы продолжим добавлять элементы, коэффициент загрузки будет увеличиваться, пока он не станет равным 1, хотим мы этого или нет. Так что подразумевается, когда мой учебник говорит, что я должен поддерживать небольшой коэффициент загрузки?

1

data-structures hashtable quadratic-probing

Источник

user3481556 31 май '15 в 12:57

1 ответ

Решение

Другие вопросы по тегам data-structures hashtable quadratic-probing

user555045 31 май '15 в 13:02 2015-05-31 13:02 · Accepted Answer · 2015-05-31 13:02

Подразумевается, что в какой-то момент (когда вы превысите коэффициент загрузки 0,5 в этом случае), вам придется выделить новую таблицу (которая больше в некотором отношении, может быть, 1,5 или 2, а затем округлить до ближайшего простого числа) и скопируйте в него все элементы из старой таблицы (это не прямая копия, новая позиция элемента обычно будет отличаться от старой позиции).