Иметь хорошую хэш-функцию для хэш-таблицы C ++?

Question

Мне нужна реализация ориентированной на производительность хеш-функции в 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 "

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

Answer 1

Теперь предположим, что вы хотите хеш и хотите что-то молниеносно , которое будет работать в вашем случае, потому что ваши строки длиной всего 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 работы для хеширования строк в набор из нескольких тысяч).

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

Answer 2

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

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

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

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

Answer 3

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

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

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

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

Answer 4

Так как вы храните английские слова, большинство ваших символов будут буквами, и в двух значимых битах ваших данных не будет большой разницы. Кроме того, я бы сделал это очень просто, просто используя 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 как реализацию хеш-таблицы? Их использование, вероятно, сэкономит много работы по сравнению с реализацией ваших собственных классов.

Answer 5

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

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

Answer 6

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

// 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 бит.

Answer 7

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

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

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

Answer 8

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

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

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

Answer 9

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

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