Какая точка хеш-таблицы?

Ответ 1

Это ближайший дубликат: Почему мы используем хэш-код в хеш-таблице вместо индекса?

Короче говоря, вы можете проверить, действительно ли ключ уже сохранен ОЧЕНЬ быстро, и так же быстро сохранить новое сопоставление. В противном случае вам придется хранить отсортированный список ключей, который намного медленнее хранить и извлекать сопоставления.

Ответ 2

Я не понимаю, почему значения, хранящиеся с ключом (строка, число, все), не являются ключом

И как вы это реализуете?

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

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

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

Ответ 3

что такое хеш-таблица?

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

Как это работает?

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

См. приведенную ниже диаграмму, на которой это ясно объясняется.

<сильные > Преимущества:

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

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

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

Недостатки:

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

Применение:

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

Ответ 4

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

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

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

f (x) = x% 13

Ответ 5

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

Ответ 6

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

Ну, как вы предлагаете это делать, используя O (1) поиск?

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

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

Ответ 7

В двух словах: Hashing позволяет O (1) запрашивать/вставляет/удаляет таблицу. OTOH, отсортированная структура (обычно реализуемая как сбалансированный BST) делает те же операции, что и O (logn).

Зачем брать хэш, спросите вы? Как вы предлагаете хранить ключ "как ключ"? Спросите себя, если вы планируете хранить пары (ключевые, значения), насколько быстро будут выполняться ваши поиски/вставки/удаления? Будете ли вы запускать цикл O (n) по всему массиву/списку?

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

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

Ответ 8

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

Ответ 9

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

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

Hashtables очень полезны, когда вы точно не знаете, сколько элементов у вас будет, но будет много меньше коллизий в хэш-функции, чем общее количество элементов. (Что делает хэш-функцию хэш (x) = 0 "очень, очень плохой.) У вас могут быть пустые места в вашей таблице, но в идеале большинство из них будут иметь некоторые данные.

Ответ 10

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

Ответ 11

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

... он позволяет сопоставить все пространство имен [оригинала] с относительно небольшим пространством имен хеш-значений, позволяя хэш-таблице обеспечивать производительность O (1) для извлечения элементов.

Эта производительность O (1) немного размывается, когда рассматривается дополнительное время для борьбы с коллизиями и т.д., но в целом хэш-таблица очень быстро используется для хранения и извлечения элементов, в отличие от системы, основанной исключительно на [original], которое обычно было бы O (log N), например, двоичным деревом (хотя такое дерево более эффективно, пространственно)