Почему хэш-коды, сгенерированные этой функцией, не уникальны?

Question

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

"122Gen размер 1 кучи (.NET CLR w3wp памяти): mccsmtpteweb025.20833333333333E-02"

«(w3wp .NET памяти CLR) 122Gen размера 2 кучи: 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 

Answer 1

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

Несколько вещей, чтобы понять:

Во-первых, будет хэш столкновения. Бывает. Даже с действительно большими пространствами, такими как MD5 (128 бит), есть еще две строки, которые могут генерировать один и тот же результат. Вы должны иметь дело с этими столкновениями, создавая ведра.

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

В-третьих, есть библиотеки, доступные вам в Visual Basic (например.NET System.Security.Cryptography), которые будут делать гораздо более эффективную работу хэширования, чем большинство простых смертных.

Answer 2

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

Answer 3

Две строки имеют одинаковые символы. (Обратите внимание на «2» и «1», которые перевернуты)

Вот почему значение хэша такое же.

Убедитесь, что функция хеширования учитывает порядок символов.

Answer 4

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

Btw, не могли бы вы отредактировать свое сообщение и вставить код в виде кода (см. Панель инструментов)? Это упростило бы чтение.

Answer 5

«Не делай этого».

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

Answer 6

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

Перемещение на 64-битные хэши или даже 128-битные хэши на самом деле не является решением, хотя оно снижает вероятность столкновения.

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

Answer 7

Пространство имен System.Security.Cryptography содержит несколько классов, которые могут делать хэширование для вас (например, MD5), что, скорее всего, сделает их лучше, чем вы сами, и потребует гораздо меньше усилий.

Вам не всегда нужно изобретать велосипед.

Answer 8

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

Try используя FNV хэш http://isthe.com/chongo/tech/comp/fnv/

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

Answer 9

Там есть визуальная базовая реализация MD5 хэширования здесь

http://www.bullzip.com/md5/vb/md5-visual-basic.htm

Answer 10

Я установил подсветку синтаксиса для него.

Кроме того, для тех, кто не был уверен в окружающей среде или предлагал более безопасный хеш: это классический (pre-.Net) VB, потому что .Net потребует скобок для вызова CopyMemory.

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

Answer 11

Эта специфическая хэш-функция XOR содержит все символы в строке. К сожалению, XOR ассоциативен:

(a XOR b) XOR c = a XOR (b XOR c) 

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

Возможно, вам потребуется найти лучший алгоритм, MD5 - хороший выбор.

Answer 12

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

В вашем примере ваша вторая строка может быть сгенерирована с вашего первого путем замены «1» после «... Gen» с первым «2» после него.

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

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

-Al.

Answer 13

Если самая большая проблема в том, что она не учитывает позиции байтов, вы можете исправить это следующим образом:

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.

Answer 14

Хеш-функции не предназначены для возврата отдельных значений для отдельных строк. Однако хорошая хеш-функция должна возвращать разные значения для строк, которые выглядят одинаково. Функции хэша используются для поиска многих причин, включая поиск в большой коллекции. Если хеш-функция хороша и если она возвращает значения из диапазона [0, N-1], то большая коллекция объектов M будет разделяться в N коллекциях, каждая из которых имеет около M/N элементов. Таким образом, вам нужно искать только в массиве элементов M/N вместо поиска в массиве из M элементов.

Но, если у вас всего 2 строки, это не быстрее вычислить значение хэша для этих! Это лучше, чтобы просто сравнить две строки.

interresing хэш-функция может быть:

    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; 
    }