динамическая настройка структуры данных

Question

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

Answer 1

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

Коэффициент загрузки используется, потому что его легко вычислить, и это не является статистически шумным, какие фактические столкновения есть.

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

Естественный шум при столкновениях является проблемой при использовании их для регулировки размера стола. Мы никогда не захотим следовать именно той политике, которую вы предлагаете. Даже с коэффициентом загрузки 25% мы бы геммерически увеличивали (скажем, по коэффициенту G> 1) таблицу на каждой вставке с вероятностью 1/4, затем снова с вероятностью 1/(4G) и т. Д. И как бы мы решили когда сжимать стол? Конечно, не каждый раз, когда нет столкновения!

Таким образом, на самом деле нам пришлось бы подсчитывать столкновение против вставки в «окне» и настраивать, когда отношение превышает высокие и низкие пороговые значения. Окно должно быть достаточно большим, чтобы отфильтровывать шум с хорошей вероятностью. Это потребует хранения и вычисления накладных расходов для поддержания. Это, вероятно, не стоит, по крайней мере, для небольших таблиц, используемых большую часть времени.

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