Существуют ли какие-либо хеш-функции, позволяющие изменить размер таблицы, не перефразируя (удаляя + повторно вставляя) содержимое?

Question

Можно ли с помощью определенной хэш-функции и метода (метод деления или двойного хеширования) создать цепочечную хеш-таблицу, размер которой можно изменять без необходимости повторной вставки (перефразирования) каждого элемента, уже находящегося в таблице?

Answer 1

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

При таком подходе можно будет также уменьшить размер таблицы.

Answer 2

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

Теоретически вы можете использовать модифицированную хеш-таблицу с закрытой адресацией, например:

1. помните все предыдущие размеры, где элементы были добавлены
2. При изменении размера сохраняйте старые корзины, связанные с ними, посредством карты sizeWhenUsed -> buckets (очевидно, если корзины пустые, не нужно беспокоиться)
3. Инвариантное отображение ключа k существует только в одной из «внутренних хеш-таблиц» в любое время.
4. при добавлении значения вы должны сначала найти его на всех других картах, чтобы определить, существует ли запись и сопоставлена ​​ли она. Если это удалить его из старого и добавить его в новый.
   • если внутренняя карта становится пустой / ниже определенного размера, она должна быть удалена, а оставшиеся элементы перемещены в текущую хэш-таблицу.
5. До тех пор, пока число внутренних хэшей остается постоянным, это не повлияет на поведение O большой структуры данных во времени, хотя будет в памяти.
   • Это, однако, повлияет на фактическую производительность, так как X должны быть выполнены дополнительные проверки, где X - количество сохраненных старых хешей.
   • Если потраченное впустую пространство списка сегментов (сами контейнеры будут нулевыми, если они пустые, а затраты равны нулю, если не заполнены) станут значительными (используйте для этого коэффициент помадки), то в какой-то момент повторного анализа вам, возможно, придется принять попадание вещей в текущую таблицу, если вы не готовы тратить практически неограниченную память.

Уменьшение размера хеша только будет функционировать желаемым образом (освобождая память), если вы захотите перефразировать. Это неизбежно.

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

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

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

Answer 3

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

Answer 4

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

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

Быстрый псевдокод для добавления элемента:

if resizing then
    smallTable = bigTable
    bigTable = new T[smallTable.length * 2] //if allocation zeroes memory, we lose O(1)
    set state to zeroing
elseif zeroing then
    zero a small amount of the bigTable memory
    if done zeroing then set state to transfering
elseif transfering then
    transfer a few values in the small table to the big table
    if done transfering then set state to resizing
end if

add new item to small array
add new item to large array

Answer 5

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