Какие алгоритмы доступны для изменения размеров хеш-таблицы?
Я реализовал свои собственные функции хеш-таблицы в C, но в настоящее время он не поддерживает изменение размеров. Я задавался вопросом, какие алгоритмы действительно существуют кроме способа "в лоб" создать новую пустую хеш-таблицу и переместить все туда?
3 ответа
Существует инкрементальное изменение размера.
Из Википедии:
Инкрементальное изменение размера
Некоторые реализации хэш-таблиц, особенно в системах реального времени, не может заплатить цену за увеличение гашиша за столом все сразу, потому что это может прерывать критические по времени операции. Если нельзя избежать динамического изменения размеров, a решение заключается в выполнении изменения размера постепенно:
Во время изменения размера, выделите новый хэш-стол, но оставьте старый стол без изменений. В каждой операции поиска или удаления проверяйте обе таблицы. Выполняйте операции вставки только в новую таблицу. При каждой вставке также перемещайте элементы r из старой таблицы в новую. Стол. Когда все элементы будут удалены из старой таблицы, разберитесь с ней.
Чтобы убедиться, что старая таблица будет полностью скопированный перед новым сам стол должен быть увеличен, это необходимо увеличить размер таблицу не менее чем в два раза (r + 1)/r во время изменения размера.
Так что это не какой-то умный способ переместить все элементы из старой таблицы в новую (а если и есть, то я его не видел); скорее, это облегчает бремя изменения размера, позволяя миграции происходить постепенно.
Обычно отговорка заключается в том, чтобы предоставить клиентскому коду возможность угадать оптимальное количество сегментов заранее. Это удобно, у клиента обычно есть разумное предположение о том, сколько элементов окажется в таблице. Если вы хотите сделать это автоматически, вам сначала нужно объявить массив простых чисел для размеров ведра. Когда вы видите, что коэффициент загрузки корзины становится слишком высоким, выберите следующее простое число в массиве, воссоздайте список сегментов и переместите элементы из старых сегментов в новую таблицу.
В Википедии есть несколько мудрых слов по этой теме.
Кроме того, это не решение, но может быть его частью - если вы работаете под Windows, вы можете использовать семейство функций VirtualAlloc, которые позволяют резервировать адресное пространство без фактического сохранения страниц памяти. То есть, с точки зрения непрофессионала, вы должны сделать что-то вроде «malloc» и сказать ему «зарезервировать 1000 МБ, но сделать доступными только первые 10». Так что, если вы напишете больше 10 МБ, вы получите обычный сбой. Но когда приходит время расширяться, вы просто говорите: «Хорошо, дайте мне еще 10 МБ после первых». Следующие 10 МБ становятся доступными по адресу сразу после первых 10 МБ. Это похоже на изменение размера массива. Фактически используемой оперативной памяти будет ровно столько, сколько вам нужно, но адреса памяти будут зарезервированы заранее, чтобы другие операции выделения памяти не использовали их.