Когда использовать хеш-таблицы?

Question

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

Answer 1

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

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

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

и в каких случаях использование хеш-таблиц неприменимо?

В основном, когда:

• вход не может быть хэшируются (например, вы дали блобы и не знаете, какие биты там значительны, но у вас есть int cmp(const T&, const T&) функцию вы можете использовать для std::map), или

• имеющейся/возможно хэш-функция очень коллизии склонной или

• вы хотите избежать ш производительность orst случая хиты для:

  • обработки много хэш-сталкивающихся элементов (возможно «инженерии» кто-то пытается разбить или замедлить ваше программное обеспечение)

  • изменение размера хэш-таблицы: если не presized в быть достаточно большим (что может быть расточительным и медленным при использовании чрезмерной памяти), большинство реализаций будут перераспределять массивы, которые они используют для хеш-таблицы, время от времени, затем выделять больший массив и копировать содержимое через: это может сделать конкретные вставки, которые заставляют эту перезапись быть намного медленнее, чем обычное поведение O (1), хотя среднее значение по-прежнему равно O (1); если вам нужно более последовательное поведение во всех случаях, что-то вроде баланса двоичного дерева может служить

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

Answer 2

Мы используем таблицы Hash для получения времени доступа O (1). Представьте себе словарь. Когда вы ищете слово, например «счастливое», вы прыгаете прямо к «H». Здесь хэш-функция определяется стартовым алфавитом. И тогда вы ищете

Не имеет смысла использовать таблицы Hash при заказе ваших данных или заказывать, как отсортированные номера. (Алфавиты заказываются ABCD .... XYZ, но не имеет значения, переключились ли вы на A и Z, если вы знаете, что он включен в ваш словарь.)