У вас есть хорошая хеш-функция для хеш-таблицы C++?

StackOverflow https://stackoverflow.com/questions/628790

  •  07-07-2019
  •  | 
  •  

Вопрос

Мне нужна реализация хэш-функции, ориентированная на производительность, на C++ для хеш-таблицы, которую я буду кодировать.Я уже осмотрелся и нашел только вопросы о том, что такое хорошая хеш-функция «в целом».Я рассмотрел CRC32 (но где найти хорошую реализацию?) и несколько алгоритмов шифрования.Однако к моему столу предъявляются весьма специфические требования.

Вот какая будет таблица:

100,000 items max
200,000 capacity (so the load is 0.5)
hashing a 6-character string which is a part of English sentence
     examples: "become"    "and he"    ", not "

А приоритет номер один моей хеш-таблицы — быстрый поиск (извлечение).Быстрая вставка не важна, но она будет сопровождаться быстрым поиском.Удаление не важно, и я не буду рассматривать повторное хеширование.Для обработки коллизий я, вероятно, буду использовать отдельная цепочка как описано здесь.я уже посмотрел Эта статья, но хотелось бы услышать мнение тех, кто уже решал такую ​​задачу.

Это было полезно?

Решение

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

size_t precision = 2; //change the precision with this
size_t hash(const char* str)
{
   return (*(size_t*)str)>> precision;
}

CRC для медленных людей ;)

Объяснение:Это работает путем преобразования содержимого указателя строки так, чтобы оно выглядело как size_t (int32 или int64 в зависимости от оптимального соответствия вашему оборудованию).Таким образом, содержимое строки интерпретируется как необработанное число, больше не нужно беспокоиться о символах, а затем вы выполняете битовый сдвиг с необходимой точностью (вы настраиваете это число до наилучшей производительности, я обнаружил, что 2 хорошо подходит для хеширования строк в набор в несколько тысяч).

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

Другие советы

Этот простой многочлен работает на удивление хорошо. Я получил его от Пола Ларсона из Microsoft Research, который изучал множество хеш-функций и хеш-множителей. 

unsigned hash(const char* s, unsigned salt)
{
    unsigned h = salt;
    while (*s)
        h = h * 101 + (unsigned) *s++;
    return h;
}

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

Размер таблицы также важен, чтобы минимизировать коллизии. Похоже, у тебя все хорошо.

Boost.Functional / Hash может быть использовать для вас. Я не пробовал, поэтому я не могу поручиться за его производительность.

Boost также имеет библиотеку CRC .

Я бы сначала посмотрел Boost.Unordered (т. е. boost :: unordered_map < >). Он использует хеш-карты вместо двоичных деревьев для контейнеров.

Я считаю, что некоторые реализации STL имеют hash_map < > контейнер в пространстве имен stdext.

Размер вашей таблицы будет определять, какой размер хеша вы должны использовать. Вы хотели бы свести к минимуму столкновения, конечно. Я не уверен, что вы указываете по максимальному количеству элементов и емкости (мне они кажутся одинаковыми). В любом случае, любое из этих значений предполагает, что 32-битного хэша будет достаточно. Вы могли бы избежать использования CRC16 (~ 65 000 возможностей), но вам, вероятно, придется столкнуться с множеством коллизий. С другой стороны, коллизия может быть быстрее обработана, чем хеш CRC32.

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

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

size_t hash(const std::string &data) {
  size_t h(0);
  for (int i=0; i<data.length(); i++)
    h = (h << 6) ^ (h >> 26) ^ data[i];
  }
  return h;
}

Кроме того, рассматривали ли вы std :: tr1 :: hash как хеш-функцию и / или std :: tr1 :: unordered_map как реализацию хеш-таблицы? Их использование, вероятно, сэкономит много работы по сравнению с реализацией ваших собственных классов.

  

Приоритет номер один в моей хеш-таблице - быстрый поиск (поиск).

Ну, тогда вы используете правильную структуру данных, поскольку поиск в хеш-таблице - это O (1)! :)

CRC32 должен работать нормально. Реализация не так сложна, в основном она основана на XOR. Просто убедитесь, что он использует хороший полином.

Как насчет чего-то простого: 

// Initialize hash lookup so that it maps the characters
// in your string to integers between 0 and 31
int hashLookup[256];

// Hash function for six character strings.
int hash(const char *str)
{
    int ret = 0, mult = 1;
    for (const char *p = str; *p; *p++, mult *= 32) {
        assert(*p >= 0 && *p < 256);
        ret += mult * hashLookup[*p];
    }

    return ret;
}

Это предполагает 32-битные целые. Он использует 5 бит на символ, поэтому значение хеша содержит только 30 бит. Вы можете исправить это, возможно, сгенерировав шесть битов для первого или двух символов. Если ваш набор символов достаточно мал, вам может потребоваться не более 30 бит.

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

Вы могли бы сделать это, поместив букву в каждом узле, чтобы сначала проверить узел " a " ;, а затем проверить " a " это потомки для " p " и потомки для " p " ;, а затем " l " а затем " e " ;. В ситуациях, когда у вас есть & Quot; apple & Quot; и " применить " вам нужно искать последний узел (поскольку единственная разница заключается в последнем " e " и " y ")

Но в большинстве случаев вы сможете получить слово через несколько шагов (" ксилофон " = > " x " - > " ylophone "), так что вы можете оптимизировать вот так. Это может быть быстрее, чем хеширование

Начиная с C ++ 11, C ++ предоставил std::hash< string >( string ) . Вероятно, это будет эффективная функция хеширования, обеспечивающая хорошее распределение хеш-кодов для большинства строк.

Кроме того, если вы думаете о реализации хеш-таблицы, вам следует подумать об использовании C ++ std::unordered_map .

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top