Лучший алгоритм хеширования с точки зрения хэш-коллизий и производительности для строк

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

Однако вот некоторые указатели:

• Начиная с объектов Вы используете в качестве входа к хешу, просто ряд строк, Вы могли просто объединить хэш-коды для каждой из тех отдельных строк. Я видел, что следующий псевдокод предложил сделать это, но я не знаю ни о каком конкретном анализе его:

  int hashCode = 0;
  
  foreach (string s in propertiesToHash) {
      hashCode = 31*hashCode + s.GetHashCode();
  }
  

  Согласно эта статья , Система. Сеть имеет внутренний метод, который комбинирует хэш-коды с помощью [1 114]

  combinedHash = ((combinedHash << 5) + combinedHash) ^ nextObj.GetHashCode();
  

  , я также видел код, что просто xor's хэш-коды вместе, но это походит на плохую идею мне (хотя у меня снова нет анализа для поддержки этого). Если ничто иное, Вы заканчиваете с коллизией, если те же строки хешируются в различном порядке.

• я использовал FNV успешно: http://www.isthe.com/chongo/tech/comp/fnv/

• у Paul Hsieh есть достойная статья: http://www.azillionmonkeys.com/qed/hash.html

• Другая хорошая статья Bob Jenkins, который был первоначально опубликован в 1997 в Журнале доктора Dobb (связанная статья имеет обновления): http://burtleburtle.net/bob/hash/doobs.html

Нет никакого единственного оптимального алгоритма хеширования. Если у Вас есть известный входной домен, можно использовать идеально хеширующий генератор такой в качестве gperf для генерации алгоритма хеширования, который получит 100%-й уровень, на котором конкретный вход установил. Иначе нет никакого 'правильного' ответа на этот вопрос.

Я собираюсь быть Ламе здесь, и дайте более теоретическому ответу скорее ответ точного определения, но примите значение в нем.

Первый существует две отличных проблемы:

a. Вероятность коллизии b. Выполнение хеширования (т.е.: время, циклы CPU и т.д.)

Эти две проблемы мягко взаимосвязаны. Они отлично не коррелируются.

проблема соглашения с различием между hashee и законченными пробелами хеша. При хешировании файла 1 КБ (1 024 байта), файл и хеш имеют 32 байта будет:

1,0907481356194159294629842447338e+2466 (т.е. число с 2 466 нулями) возможные комбинации входных файлов

и пространство хеша будут иметь

1,1579208923731619542357098500869e+77 (т.е. число с 77 нулями)

, различие ОГРОМНО. существует 2 389 нулевых различий между ними. БУДУТ КОЛЛИЗИИ (коллизия является особым случаем, когда два РАЗЛИЧНЫХ входных файла будут иметь тот же самый хеш), так как мы уменьшаем 10^2466 случаи до 10^77 случаи.

единственный способ минимизировать риск collison состоит в том, чтобы увеличить пространство хеша и поэтому сделать hahs дольше. Идеально хеш будет иметь длину файла, но это так или иначе слабоумно.

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

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

Удача;)

Простой хэш-код, используемый Строковым классом Java, мог бы показать подходящий алгоритм.

Ниже "реализация" Пути к классу GNU. (Лицензия: GPL)

  /**
   * Computes the hashcode for this String. This is done with int arithmetic,
   * where ** represents exponentiation, by this formula:<br>
   * <code>s[0]*31**(n-1) + s[1]*31**(n-2) + ... + s[n-1]</code>.
   *
   * @return hashcode value of this String
   */
  public int hashCode()
  {
    if (cachedHashCode != 0)
      return cachedHashCode;

    // Compute the hash code using a local variable to be reentrant.
    int hashCode = 0;
    int limit = count + offset;
    for (int i = offset; i < limit; i++)
      hashCode = hashCode * 31 + value[i];
    return cachedHashCode = hashCode;
  }

Можно получить оба использования хеш-функции Knuth, описанной здесь .

Это чрезвычайно быстро принимает power-2 размер хэш-таблицы - просто каждый умножается, один сдвиг, и один бит - и. Что еще более важно (для Вас) это сильно в уменьшении коллизий (см. этот анализ ).

Некоторые другие хорошие алгоритмы описаны здесь .

Я люблю Stackoverflow! Чтение этого вопроса заставило меня изучить хеш-функции немного больше, и я нашел Сумасшедший Хеш .

От статьи:

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

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