Что такое hashtables и hashmaps и их типичные случаи использования?

Ответ 1

Хорошо, подумайте об этом так.

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

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

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

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

Каждый элемент имеет два свойства, данные и ключ, который идентифицирует данные. Например, список почтовых индексов США будет представлять собой тип ассоциации почтового индекса → . Функция уменьшает ключ, но не учитывает данные.

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

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

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

Типичная хэш-таблица не имеет бесконечного количества элементов, доступных для хранения, поэтому число обычно уменьшается до индекса, который вписывается в размер массива. Один из способов сделать это - просто взять модуль индекса по сравнению с размером массива. Для массива размером 10, индекс 0-9 будет отображаться непосредственно в индекс, а индекс 10-19 будет отображаться до 0-9 снова и т.д.

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

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

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

Функция, которая сводит ключ к числу, не дает линейного значения, т.е. "AAA" становится равным 1, тогда "AAB" становится равным 2, поэтому хэш-таблица не сортируется по какой-либо типичной величине.

В этой статье есть хорошая статья по википедии, здесь.

Ответ 2

lassevk ответ очень хорош, но может содержать слишком много деталей. Вот резюме. Я намеренно не указывая определенную релевантную информацию, которую вы можете смело игнорировать в 99% случаев.

В хеш-таблицах и хэш-картах в% от времени нет важной разницы.

Таблицы хэшей - это волшебство

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

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

2) Если вы делаете что-либо одним ключом в хеш-таблице, оно невероятно быстро. Это означает, что put(key,value), get(key), contains(key) и remove(key) все очень быстро.

3) Общие хеш-таблицы не выполняют ничего, что не указано в # 2! (Под "неудачей" мы подразумеваем, что они невероятно медленны.)

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

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

Например, кеширование часто заканчивается использованием хеш-таблицы - например, скажем, у нас 45 000 студентов в университете, и некоторые процессы должны содержать записи для всех из них. Если вы обычно обращаетесь к ученику по номеру ID, то кеш ID => student имеет отличный смысл. Операция, которую вы оптимизируете для этого кеша, быстрый поиск.

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

Они также делают довольно хороший первый выбор для структуры данных, за исключением случаев, когда вам нужно выполнить одно из следующих действий:

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

Итерации по элементам. Хэш-таблицы обычно не очень хорошо выполняют итерацию. (Например, в частности, в Java, LinkedHashMap позволяет быстро перебирать ключи или значения.)

Сортировка. Если вы не можете выполнять итерацию, сортировка также является сильной болью.

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

Ответ 3

если вы говорите в терминах Java, оба являются коллекциями, которые позволяют добавлять, удалять и обновлять объекты и использовать алгоритмы Hasing внутри.

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

Помимо синхронизации, внутренний механизм хранения и извлечения объектов является хэшированием в обоих случаях.

Если вам нужно посмотреть, как работает Hashing, я бы порекомендовал немного поиска в Google Data Structers и хэширования.

Ответ 4

Hashtables/hashmaps связывают значение (называемое "ключ" для целей неоднозначности) с другим значением. Вы можете считать их своего рода словарем (слово: определение) или записью базы данных (ключ: данные).