Почему хэш-коды, генерируемые этой функцией, не уникальны?
https://stackoverflow.com/questions/63897
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я тестирую приведенную ниже функцию VB, которую я получил из поиска в Google.Я планирую использовать его для генерации хэш-кодов для быстрого сравнения строк.Однако бывают случаи, когда две разные строки имеют один и тот же хэш-код.Например, эти строки
"Размер кучи 122Gen 1 (память .NET CLR w3wp): mccsmtpteweb025.2083333333333333E-02"
"Размер кучи 122Gen 2 (память .NET CLR w3wp): mccsmtpteweb015.2083333333333333E-02"
имеют тот же хэш-код 237117279.
Пожалуйста, скажи мне:- Что не так с этой функцией?- Как я могу это исправить?
Спасибо
мартин
Private Declare Sub CopyMemory Lib "kernel32" Alias "RtlMoveMemory" (dest As Any, src As Any, ByVal bytes As Long)
Private Function HashCode(Key As String) As Long
On Error GoTo ErrorGoTo
Dim lastEl As Long, i As Long
' copy ansi codes into an array of long'
lastEl = (Len(Key) - 1) \ 4
ReDim codes(lastEl) As Long
' this also converts from Unicode to ANSI'
CopyMemory codes(0), ByVal Key, Len(Key)
' XOR the ANSI codes of all characters'
For i = 0 To lastEl - 1
HashCode = HashCode Xor codes(i) 'Xor'
Next
ErrorGoTo:
Exit Function
End Function
Решение
Я готов поспорить, что существует нечто большее, чем просто "случаи", когда две строки генерируют один и тот же хэш с помощью вашей функции.На самом деле, это, вероятно, случается чаще, чем вы думаете.
Несколько вещей, которые нужно осознать:
Во-первых, возникнут коллизии хэшей.Такое случается.Даже с очень, очень большими пробелами, такими как MD5 (128 бит), все равно есть две строки, которые могут генерировать один и тот же результирующий хэш.Вы должны иметь дело с этими столкновениями, создавая сегменты.
Во-вторых, длинное целое число на самом деле не является большим хэш-пространством.Вы получите больше столкновений, чем если бы использовали больше битов.
В-третьих, в Visual Basic вам доступны библиотеки (например .NET's System.Security.Cryptography пространство имен), которое будет выполнять хэширование гораздо лучше, чем большинство простых смертных.
Другие советы
Эти две строки содержат одинаковые символы.(Обратите внимание на "2" и "1", которые являются перевернутыми)
Вот почему хэш-значение одно и то же.
Убедитесь, что хэш-функция учитывает порядок расположения символов.
Хэш-функции не гарантируют уникальность хэш-значений.Если диапазон входных значений (судя по вашим примерным строкам) больше диапазона выходных значений (например, 32-битное целое число), то уникальность физически невозможна.
Если самая большая проблема заключается в том, что она не учитывает положение байтов, вы могли бы исправить это следующим образом:
Private Function HashCode(Key As String) As Long
On Error GoTo ErrorGoTo
Dim lastEl As Long, i As Long
' copy ansi codes into an array of long'
lastEl = (Len(Key) - 1) \ 4
ReDim codes(lastEl) As Long
' this also converts from Unicode to ANSI'
CopyMemory codes(0), ByVal Key, Len(Key)
' XOR the ANSI codes of all characters'
For i = 0 To lastEl - 1
HashCode = HashCode Xor (codes(i) + i) 'Xor'
Next
ErrorGoTo:
Exit Function
End Function
Единственное отличие заключается в том, что он добавляет позицию символов к своему байтовому значению перед XOR.
Никакая хэш-функция не может гарантировать уникальность.Существует ~ 4 миллиарда 32-разрядных целых чисел, поэтому даже самая лучшая хэш-функция будет генерировать дубликаты при представлении ~ 4 миллиардов и 1 строки (и, скорее всего, задолго до этого).
Переход на 64-битные или даже 128-битные хэши на самом деле не является решением, хотя это снижает вероятность коллизии.
Если вам нужна лучшая хэш-функция, вы могли бы посмотреть на криптографические хэши, но было бы лучше пересмотреть свой алгоритм и решить, можете ли вы справиться с коллизиями каким-либо другим способом.
Тот Самый Система.Безопасность.Криптография пространство имен содержит несколько классов, которые могут выполнять хеширование за вас (например, MD5), который, вероятно, обработает их лучше, чем вы могли бы сами, и потребует гораздо меньше усилий.
Вам не всегда нужно изобретать велосипед заново.
Простой XOR - это плохой хэш:вы найдете множество строк, которые сталкиваются.Во-первых, хэш не зависит от порядка букв в строке.
Попробуйте использовать хэш FNV http://isthe.com/chongo/tech/comp/fnv/
Это действительно просто реализовать.Он сдвигает хэш-код после каждого XOR, поэтому одни и те же буквы в другом порядке будут создавать другой хэш.
Хэш-функции не предназначены для возврата различных значений для разных строк.Однако хорошая хэш-функция должна возвращать разные значения для строк, которые выглядят одинаково.Хэш-функции используются для поиска по многим причинам, включая поиск в большой коллекции.Если хэш-функция хороша и если она возвращает значения из диапазона [0,N-1], то большая коллекция из M объектов будет разделена на N коллекций, каждая из которых содержит около M / N элементов.Таким образом, вам нужно выполнять поиск только в массиве из M / N элементов вместо поиска в массиве из M элементов.
Но, если у вас есть только 2 строки, это нет быстрее вычислять хэш-значение для них!Это так лучше чтобы просто сравнить две строки.
Интересной хэш-функцией может быть:
unsigned int hash(const char* name) {
unsigned mul=1;
unsigned val=0;
while(name[0]!=0) {
val+=mul*((unsigned)name[0]);
mul*=7; //you could use an arbitrary prime number, but test the hash dispersion afterwards
name++;
}
return val;
}
Я исправил для него подсветку синтаксиса.
Кроме того, для тех, кто не был уверен в среде или предлагал более безопасный хэш:это классический (pre-.Net) глаг, потому что .Чистая потребуются круглые скобки для звонка кому copymemory.
IIRC, для классического VB не встроено никаких защищенных хэшей.В Интернете тоже не так уж много информации, так что, возможно, это его лучший выбор.
Я не совсем понимаю, в какой обстановке вы работаете.Это .Сетевой код?Если вам действительно нужны хорошие хэш-коды, я бы рекомендовал изучить криптографические хэши (проверенные алгоритмы) вместо того, чтобы пытаться писать свои собственные.
Кстати, не могли бы вы отредактировать свой пост и вставить код в качестве примера кода (см. Панель инструментов)?Это облегчило бы чтение.
"Не делай этого".
Написание вашей собственной хэш-функции - большая ошибка, потому что в вашем языке, безусловно, уже есть реализация SHA-1, которая является совершенно хорошей хэш-функцией.Если вам нужно всего 32 бита (вместо 160, которые предоставляет SHA-1), просто используйте последние 32 бита SHA-1.
Эта конкретная хэш-функция преобразует все символы в строке в XOR.К сожалению, XOR является ассоциативным:
(a XOR b) XOR c = a XOR (b XOR c)
Таким образом, любые строки с одинаковыми входными символами приведут к одному и тому же хэш-коду.Две предоставленные строки одинаковы, за исключением расположения двух символов, поэтому они должны иметь одинаковый хэш-код.
Возможно, вам потребуется найти лучший алгоритм, MD5 был бы хорошим выбором.
Операция XOR является коммутативной;то есть, при XORing всех символов в строке порядок символов не имеет значения.Все анаграммы строки будут выдавать один и тот же хэш XOR.
В вашем примере ваша вторая строка может быть сгенерирована из вашей первой, заменив "1" после "...Gen" на первую "2", следующую за ней.
В вашей функции нет ничего плохого.Все полезные функции хеширования иногда приводят к конфликтам, и ваша программа должна быть готова к их разрешению.
Коллизия возникает, когда входные данные хэшируются со значением, уже идентифицированным с более ранними входными данными.Если бы алгоритм хеширования не мог генерировать коллизии, значения хэша должны были бы быть такими же большими, как входные значения.Такой алгоритм хеширования имел бы ограниченное применение по сравнению с простым сохранением входных значений.
-Эл.
Здесь есть реализация хеширования MD5 на Visual Basic
