Хеширование - что это делает?

Question

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

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

Answer 1

Хеширование - это быстрая эвристика для нахождения класса эквивалентности объекта.

Другими словами:

Хеширование полезно, потому что это вычислительно дешево.Стоимость не зависит от размера класса эквивалентности.http://en.wikipedia.org/wiki/Time_complexity#Constant_time

Класс эквивалентности - это набор эквивалентных элементов.Подумайте о строковых представлениях чисел.Вы можете сказать, что «042», «42», «42.0», «84/2», «41.9 ...» являются эквивалентными представлениями одного и того же базового абстрактного понятия.Они будут в одном классе эквивалентности.http://en.wikipedia.org/wiki/Equivalence_class

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

Хеширование является эвристическим , т.е. оно не всегда дает идеальный результат, но его недостатки могут быть смягчены разработчиком алгоритма, который знает о них.Хеширование производит хеш-код.Два разных объекта (не в одном и том же классе эквивалентности) могут создавать один и тот же хэш-код, но обычно этого не происходит, но два объекта в одном и том же классе эквивалентности должны создавать один и тот же хэш-код.http://en.wikipedia.org/wiki/Heuristic#Computer_science

Answer 2

Хеширование суммируется.

Хэш последовательности чисел (2,3,4,5,6) представляет собой сводку этих чисел. Например, 20 представляет собой один вид сводки, который не очень хорошо включает все доступные биты в исходных данных. Это не очень хорошее резюме, но это резюме.

Когда значение включает в себя более нескольких байтов данных, некоторые биты должны быть отклонены. Если вы используете sum и mod (например, чтобы сохранить сумму менее 2 миллиардов), вы, как правило, сохраняете много самых правых битов и теряете все самые левые биты.

Таким образом, хороший хеш справедлив - он сохраняет и отклоняет биты по справедливости. Это имеет тенденцию предотвращать столкновения.

Например, в нашем упрощенном «хэше суммы» будут конфликты между другими последовательностями чисел, которые также имеют одинаковую сумму.

Answer 3

Я бы сказал, что ответ Линута довольно хороший, но я его немного дополню. Компьютеры очень хороши для доступа к вещам в массивах. Если я знаю, что элемент находится в MyArray [19], я могу получить к нему доступ напрямую. Хеш-функция - это средство отображения ключей поиска для индексов массива. Если в массиве хранится 193 372 различных строки, и у меня есть функция, которая будет возвращать 0 для одной из строк, 1 для другой, 2 для другой и т. Д. До 193 371 для последней, я могу посмотреть, есть ли строка находится в массиве, запустив эту функцию и посмотрев, соответствует ли данная строка той, что находится в этом месте в массиве. Красиво и просто.

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

  if (inputstring == thefirststring) return 0;
  if (inputstring == thesecondstring) return 1;
  if (inputstring == thethirdstring) return 1;
... up to the the193371ndstring

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

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

1. Линейное хеширование - если два элемента отображаются на одно и то же хеш-значение, сохраните один из них в слоте массива, следуя тому, который указан хеш-кодом. При поиске предмета ищите в указанном слоте, а затем в следующем, затем в следующем и т. Д., Пока предмет не будет найден или один не попадет в пустой слот. Линейное хеширование простое, но работает плохо, если таблица не намного больше, чем количество элементов в ней (оставляя много пустых слотов). Также обратите внимание, что удаление элементов из такой хеш-таблицы может быть затруднено, так как существование элемента могло помешать некоторому другому элементу попасть в указанное место.
2. Двойное хеширование - если два элемента отображаются на одно и то же значение, вычислите другое значение хеш-функции для второго добавленного и вытолкните второй элемент на много слотов (если этот слот заполнен, продолжайте шагать с этим приращением до свободный слот найден). Если значения хеш-функции независимы, этот подход может хорошо работать с более плотной таблицей. Однако еще сложнее удалить элементы из такой таблицы, чем с помощью линейной хэш-таблицы, поскольку нет хорошего способа найти элементы, которые были смещены элементом, подлежащим удалению.
3. Вложенное хеширование - каждый слот в хеш-таблице содержит хеш-таблицу, использующую функцию, отличную от основной таблицы. Это может хорошо работать, если две хеш-функции независимы, но может работать очень плохо, если это не так.
4. Хэширование цепочки - каждый слот в хеш-таблице содержит список вещей, которые соответствуют этому хеш-значению. Если N вещей отображаются в определенный слот, то нахождение одного из них займет время O (N). Однако, если хеш-функция является приличной, большинство непустых слотов будет содержать только один элемент, большинство из тех, у которых больше этого, будет содержать только два, и т. Д., Поэтому ни один слот не будет содержать очень много элементов.

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

Answer 4

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

Предположим, у вас есть некоторые данные (может быть, массив, дерево или записи базы данных).Вы хотите найти конкретный элемент в этом хранилище данных (например, в массиве) как можно быстрее.Как это сделать?

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

Итак, теперь у вас есть массив элементов, и для каждого элемента у вас есть это HashValue.Как это использовать?Предположим, у вас есть массив из N элементов.Давайте поместим ваши элементы в этот массив в соответствии с их HashHalues.

Предположим, вы должны ответить на этот вопрос: существует ли элемент "it1" в этом массиве?Чтобы ответить на него, вы можете просто найти HashValue для «it1» (назовем его f («it1»)) и посмотреть на массив в позиции f («it1»).Если элемент в этой позиции не является нулевым (и равен нашему элементу "it1"), наш ответ верен.В противном случае ответ будет ложным.

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

Некоторые примеры для лучшего понимания:

Предположим, у вас есть массив строк: A = {"aaa", "BGB», "ЧПСК", "dddsp", ...}.И вы должны ответить на вопрос: содержит ли этот массив строку S?

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

Итак, f ("aaa ") = 3, f (" qwerty ") = 6 и т. д. ...

Итак, теперь мы должны вычислить значения HashValues ​​для каждого элемента в массиве A: f (" aaa ") = 3,f ("eccc") = 4, ...

Давайте возьмем массив для хранения этих элементов (он также называется HashTable) - назовем его H (массив строк).Итак, теперь мы помещаем наши элементы в этот массив согласно их HashValues:

H [3] = "aaa", H [4] = "eccc", ...

И, наконец,Как найти данную строку в этом массиве?

Предположим, вам дана строка s = "eccc".f ("eccc") = 4. Итак, если H [4] == "eccc", наш ответ будет верным, в противном случае он будет заполнен как ложный.

Но как избежать ситуаций, когда элементам приходитсято же самое HashValues?Есть много путей к этому.Одно из этого: каждый элемент в HashTable будет содержать список элементов.Итак, H [4] будет содержать все элементы, которым HashValue равно 4. И как найти конкретный элемент?Это очень просто: посчитать этот элемент HashValue и посмотреть список элементов в HashTable [HashValue].Если один из этих элементов соответствует нашему поисковому элементу, ответ верен, а в противном случае - ложь.

Answer 5

Вы должны сначала прочитать статью википедии .Затем задайте вопросы по темам, которые вы не понимаете.

Короче говоря, цитируя статью, хэш означает:

для нарезки и смешивания

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

Давайте возьмем x % 9 в качестве примера функции хеширования.

345 % 9 = 3
355 % 9 = 4
344 % 9 = 2
2345 % 9 = 5

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

С другой стороны, если бы мы взяли x%10.Мы получили бы

345 % 10 = 5
355 % 10 = 5
344 % 10 = 4
2345 % 10 = 5

Как видите, большинство хэшированных значений равны 5.Это говорит нам о том, что x%10 является худшей функцией хеширования, чем x%9.

Обратите внимание, что x%10 по-прежнему является функцией хеширования .Тождественную функцию можно также считать хэш-функцией.

Answer 6

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

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

существует множество требований к определенным типам хэш-функций

, например, что хэш всегда имеет одинаковую длину.

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

единственный важный момент заключается в том, что он детерминирован (всегда один и тот же хеш для одних и тех же данных).

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

читать все об этом здесь

http://en.wikipedia.org/wiki/Hash_function

Answer 7

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