Какие алгоритмы доступны для изменения размера хэш-таблицы?

Question

Я реализовал свои собственные хеш-таблицы в C, но в настоящее время он не поддерживает изменение размера. Мне было интересно, какие алгоритмы существуют, кроме грубого метода создания новой пустой хеш-таблицы и перемещения всего туда?

Answer 1

Существует постепенное изменение размера.

Из Википедии:

Увеличение размера

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

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

Чтобы убедиться, что старая таблица будет полностью скопированы перед новым Сам стол должен быть увеличен, это необходимо увеличить размер таблица не менее чем в (r + 1) / r при изменении размера.

Так что это не какой-то умный способ переместить все элементы из старой таблицы в новую таблицу (и если она есть, я ее не видел); скорее это облегчает бремя изменения размера, позволяя миграции происходить постепенно.

Answer 2

В Википедии есть слов мудрости на эту тему.

Кроме того, это не решение, но может быть его частью - если вы находитесь под Windows, вы можете использовать семейство функций VirtualAlloc, которые позволяют резервировать адресное пространство без фактической фиксации страниц памяти. То есть, с точки зрения непрофессионалов, вы должны сделать что-то вроде «malloc» и сказать ему «зарезервировать 1000 МБ, но сделать только первые 10 доступных». Так что, если вы напишите больше 10 МБ, вы получите обычный сбой. Но когда приходит время расширяться, вы просто говорите: «Хорошо, дайте мне еще 10 МБ после первых». И следующие 10 МБ становятся доступными по адресу сразу после первых 10 МБ. Это похоже на изменение размера массива. Фактическое количество используемой оперативной памяти будет составлять столько, сколько вам нужно, но адреса памяти будут зарезервированы заранее, чтобы другие операции выделения памяти их не использовали.

Answer 3

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