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

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

Первый:

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

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

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

Источник

6 ответов

Решение

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

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

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

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

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

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

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

Источник

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

Используйте 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 о "хэш-функции общего назначения"

Источник

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

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

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

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

Источник

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

#include <boost\functional\hash.hpp>

...

std::string a = "ABCDE";
size_t b = boost::hash_value(a);
Источник

В 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;
}
Источник

В C++ уже реализован хеш для std::string:

std :: hash<std :: string> // из заголовка 

      #include <iostream> // not actually required for the hash
#include <string>

auto main() ->int
{
    const std::string input = "Hello World!";
    const std::hash<std::string> hasher;
    const auto hashResult = hasher(input);
    
    std::cout << "Input hash is: " << hashResult << std::endl;
}

Запустите этот код здесь: https://onlinegdb.com/33KLb91ku

Источник
Другие вопросы по тегам