Почему хэш-коды, генерируемые этой функцией, не являются уникальными?
Я тестирую функцию VB ниже, которую я получил от поиска Google. Я планирую использовать его для генерации хеш-кодов для быстрого сравнения строк. Однако бывают случаи, когда две разные строки имеют одинаковый хэш-код. Например, эти строки
"Размер кучи 122Gen 1 (.NET CLR Memory w3wp): mccsmtpteweb025.20833333333333E-02"
"Размер кучи 122Gen 2 (.NET CLR Memory w3wp):mccsmtpteweb015.20833333333333E-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
14 ответов
Могу поспорить, что есть больше, чем просто "случаи", когда две строки генерируют один и тот же хэш с помощью вашей функции. На самом деле, это, вероятно, случается чаще, чем вы думаете.
Несколько вещей для реализации:
Во-первых, будут хеш-коллизии. Такое случается. Даже с очень, очень большими пробелами, такими как MD5 (128 бит), есть две строки, которые могут генерировать один и тот же результирующий хеш. Вы должны справиться с этими столкновениями, создавая ведра.
Во-вторых, длинное целое число на самом деле не большое хеш-пространство. Вы получите больше столкновений, чем если бы вы использовали больше битов.
В-третьих, есть библиотеки, доступные вам в Visual Basic (например,.NET System.Security.Cryptography namespace), которая сделает хэширование намного лучше, чем большинство простых смертных.
Две строки имеют одинаковые символы. (Обратите внимание на "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.
Я исправил подсветку синтаксиса для него.
Кроме того, для тех, кто не был уверен в среде или предлагал более безопасный хеш: это классический (до.Net) VB, потому что.Net потребовал бы скобки для вызова CopyMemory.
IIRC, в Classic VB нет встроенных безопасных хэшей. В интернете тоже не так много, так что это может быть его лучшим выбором.
Хеш-функции не предназначены для возврата разных значений для разных строк. Однако хорошая хеш-функция должна возвращать разные значения для одинаковых строк. Хеш-функции используются для поиска по многим причинам, включая поиск в большой коллекции. Если хеш-функция хороша и если она возвращает значения из диапазона [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;
}
Простой XOR - плохой хеш: вы найдете много строк, которые сталкиваются. Хеш не зависит от порядка букв в строке, с одной стороны.
Попробуйте использовать хэш FNV http://isthe.com/chongo/tech/comp/fnv/
Это действительно просто реализовать. Он сдвигает хеш-код после каждого XOR, поэтому одни и те же буквы в другом порядке будут создавать разные хэши.
Никакая хеш-функция не может гарантировать уникальность. Существует около 4 миллиардов 32-битных целых чисел, поэтому даже лучшая хеш-функция будет генерировать дубликаты, когда представлено ~4 миллиарда и 1 строкой (и, скорее всего, задолго до этого).
Переход к 64-битным хешам или даже 128-битным хешам на самом деле не является решением, хотя снижает вероятность коллизии.
Если вам нужна более качественная хеш-функция, вы можете посмотреть криптографические хеши, но было бы лучше пересмотреть ваш алгоритм и решить, сможете ли вы справиться с коллизиями другим способом.
Пространство имен System.Security.Cryptography содержит несколько классов, которые могут выполнять хеширование для вас (например, MD5), которые, вероятно, будут хэшировать их лучше, чем вы сами, и потребуют гораздо меньше усилий.
Вам не всегда нужно изобретать велосипед.
"Не делай этого".
Написание вашей собственной хеш-функции - большая ошибка, потому что ваш язык, безусловно, уже имеет реализацию SHA-1, которая является совершенно хорошей хеш-функцией. Если вам нужно только 32 бита (вместо 160, которые предоставляет SHA-1), просто используйте последние 32 бита SHA-1.
Операция XOR является коммутативной; то есть, когда XOR все символы в строке, порядок символов не имеет значения. Все анаграммы строки будут создавать один и тот же хэш XOR.
В вашем примере, ваша вторая строка может быть сгенерирована из вашей первой, поменяв местами "1" после "...Gen " с первой "2" после нее.
В вашей функции нет ничего плохого. Все полезные функции хеширования иногда генерируют коллизии, и ваша программа должна быть готова к их устранению.
Столкновение происходит, когда вход хэширует к значению, уже идентифицированному с более ранним входом. Если алгоритм хеширования не может генерировать коллизии, хеш-значения должны быть такими же большими, как входные значения. Такой алгоритм хеширования будет иметь ограниченное применение по сравнению с простым хранением входных значений.
-Аль.
Я не совсем вижу среду, в которой вы работаете. Это код.Net? Если вам действительно нужны хорошие хэш-коды, я бы порекомендовал изучать криптографические хеши (проверенные алгоритмы), а не пытаться писать свои собственные.
Кстати, не могли бы вы отредактировать свой пост и вставить код в качестве примера кода (см. Панель инструментов)? Это облегчит чтение.
Этот конкретный хэш-функции XOR все символы в строке. К сожалению, XOR является ассоциативным:
(a XOR b) XOR c = a XOR (b XOR c)
Таким образом, любые строки с одинаковыми входными символами приведут к одному и тому же хеш-коду. Две предоставленные строки одинаковы, за исключением расположения двух символов, поэтому они должны иметь одинаковый хэш-код.
Вам может понадобиться найти лучший алгоритм, MD5 будет хорошим выбором.
Здесь есть визуальная базовая реализация хеширования MD5.