Хэш-функция для строки

Ответ 1

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

Но если вам действительно все равно, вы должны знать, что это предмет исследования сам по себе. Об этом говорится в тысячах статей. Вы все еще можете получить PhD сегодня, изучая и разрабатывая алгоритмы хеширования.

Ваша вторая хэш-функция может быть немного лучше, потому что она, вероятно, должна отделить строку "ab" от строки "ba". С другой стороны, он, вероятно, менее быстрый, чем первая хэш-функция. Он может или не может быть релевантным для вашего приложения.

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

Многие библиотеки программного обеспечения предоставляют вам достаточно хорошие хеш-функции, например. Qt имеет qhash, а С++ 11 std:: hash в <functional>, Glib имеет несколько хэш-функций на C, а POCO имеет функцию hash.

У меня довольно часто есть хеширующие функции, содержащие простые числа (см. Bézout identity) и xor, например,

#define A 54059 /* a prime */
#define B 76963 /* another prime */
#define C 86969 /* yet another prime */
#define FIRSTH 37 /* also prime */
unsigned hash_str(const char* s)
{
   unsigned h = FIRSTH;
   while (*s) {
     h = (h * A) ^ (s[0] * B);
     s++;
   }
   return h; // or return h % C;
}

Но я не претендую на роль хеш-эксперта. Конечно, значения A, B, C, FIRSTH должны быть предпочтительно простыми, но вы могли бы выбрать другие простые числа.

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

В большинстве хороших книг по алгоритмике есть по крайней мере целая глава, посвященная хешированию. Начните с wikipages на хеш-функции и хеш-таблица.

Ответ 2

- путь в эти дни -

Используйте SipHash. Для вашей собственной защиты.

- Старый и опасный -

unsigned int RSHash(const std::string& str)
{
    unsigned int b    = 378551;
    unsigned int a    = 63689;
    unsigned int hash = 0;

    for(std::size_t i = 0; i < str.length(); i++)
    {
        hash = hash * a + str[i];
        a    = a * b;
    }

    return (hash & 0x7FFFFFFF);
 }

 unsigned int JSHash(const std::string& str)
 {
      unsigned int hash = 1315423911;

      for(std::size_t i = 0; i < str.length(); i++)
      {
          hash ^= ((hash << 5) + str[i] + (hash >> 2));
      }

      return (hash & 0x7FFFFFFF);
 }

Задайте google для "хэш-функции общего назначения"

Ответ 3

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

если ваши значения являются строками, вот несколько примеров для плохих хеш-функций:

• string[0] - символы ASCII a-Z намного чаще, чем другие.
• string.lengh() - наиболее вероятное значение - 1

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

Ответ 4

Используйте boost:: hash

#include <boost\functional\hash.hpp>

...

std::string a = "ABCDE";
size_t b = boost::hash_value(a);

Ответ 5

Java String реализует hashCode как это:

public int hashCode()

Returns a hash code for this string. The hash code for a String object is computed as

     s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

using int arithmetic, where s[i] is the ith character of the string, n is the length of the string, and ^ indicates exponentiation. (The hash value of the empty string is zero.) 

Так что-то вроде этого:

int HashTable::hash (string word) {
    int result = 0;
    for(size_t i = 0; i < word.length(); ++i) {
        result += word[i] * pow(31, i);
    }
    return result;
}