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

Question

Я тестирую функцию 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

Answer 1

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

Несколько вещей, которые нужно осознать:

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

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

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

Answer 2

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

Вот почему значение хеш-функции одинаково.

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

Answer 3

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

Answer 4

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

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 5

Хеш-функции не предназначены для возврата разных значений для разных строк. Однако хорошая хеш-функция должна возвращать разные значения для одинаковых строк. Хеш-функции используются для поиска по многим причинам, включая поиск в большой коллекции. Если хеш-функция хороша и если она возвращает значения из диапазона [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;
    }

Answer 6

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

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

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

Answer 7

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

Попробуйте использовать хэш FNV http://isthe.com/chongo/tech/comp/fnv/

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

Answer 8

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

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

Answer 9

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

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

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

Answer 10

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

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

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

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

-Аль.