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

Question

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

Первый:

int HashTable::hash (string word)   
// POST: the index of entry is returned
{       int sum = 0;
        for (int k = 0; k < word.length(); k++)
            sum = sum + int(word[k]);
        return  sum % SIZE; 
}

Второе:

int HashTable::hash (string word)
{
   int seed = 131; 
   unsigned long hash = 0;
   for(int i = 0; i < word.length(); i++)
   {
      hash = (hash * seed) + word[i];
   }
   return hash % SIZE;
}

Где SIZE - 501 (размер хеш-таблицы), а ввод поступает из текстового файла, содержащего более 20 000 слов.

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

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

Answer 1

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

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

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

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

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

У меня довольно часто есть функции хеширования, включающие простые числа (см. идентификатор Безу ) и 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 , чтобы понять, какими могут быть хеш-функции.

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

Answer 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 о "хэш-функции общего назначения"

Answer 3

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

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

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

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

Answer 4

Использование boost :: hash

#include <boost\functional\hash.hpp>

...

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

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