размер массива для расширяемого хеширования

Question

Если я хочу использовать расширяемое хеширование для хранения максимум 100 записей, то какой минимальный размер массива мне нужен?

Я предполагаю, что массива 100 будет достаточно, но я могу ошибаться. Я также подозреваю, что могу использовать меньший массив.

Answer 1

Что вы знаете о своей хэш-функции?

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

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

Если ваша хеш-функция может хэшировать каждый элемент, чтобы иметь 7 из 7 (или более) разных битов, тогдау вас есть наиболее оптимальное решение с размером сегмента 1. Оставить 128 конечных узлов или массив размером 128.

Если ваша хеш-функция может хешировать каждый элемент, чтобы иметь 6 из 7 (или более) разных битов, тогда у вас есть размер сегмента 2. У вас будет 64 конечных узла / комбинации / размер массива.

Если ваша хеширующая функция может хешировать каждый элемент, чтобы иметь 5 из 7 (или более) разных битов, тогда выразмер корзины равен 4. У вас будет 32 конечных узла / комбинации / размер массива.

Поскольку вы сказали, что хотите размер корзины 4, я думаю, что ваш ответ будет 32, и у вас есть жесткое требование, чтобы выиметь хорошую функцию хеширования, которая может дать вам как минимум 5 первых битов как отличных.

Answer 2

Я думаю, это зависит от того, нужна ли вам высокая производительность или экономия памяти.Вы можете просто сохранить элементы в массив из 100. Я не знаю много о расширяемом хешировании, но мое общее понимание хэширования состоит в том, что у него будут некоторые виды коллизий, и если вы будете использовать больший массив для его хранения,количество столкновений может уменьшиться, и производительность при добавлении / удалении и запросах также будет выше.Я думаю, что вы должны использовать по крайней мере 128 (просто чтобы быть 2 ^ K, я не эксперт в хешировании):)