Есть хорошая хэш-функция для хеш-таблицы С++?

Ответ 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 хорошо работает для хеширования строк в набор из нескольких тысяч).

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

Ответ 2

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

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

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

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

Ответ 3

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

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

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

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

Ответ 4

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

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

Ответ 5

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

Ответ 6

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

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

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

Ответ 7

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

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

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

Ответ 8

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

// 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-битные int. Он использует 5 бит на символ, поэтому хеш-значение содержит только 30 бит. Вы могли бы исправить это, возможно, путем генерации шести бит для первого или двух символов. Если набор символов достаточно мал, вам может потребоваться не более 30 бит.

Ответ 9

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

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