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

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

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

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

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

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

Кстати, не могли бы вы отредактировать свой пост и вставить код как образец кода (см. Панель инструментов)? Так было бы легче читать.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-Ал.

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

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.

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