есть ли в C ++ функция, которая вычисляет отпечаток или хэш строки, ширина которой гарантированно не менее 64 бит?

Question

есть ли в C ++ функция, которая вычисляет отпечаток или хэш строки, ширина которой не менее 64 битов?

Я бы хотел заменить unordered_map<string, int> на unordered_map<long long, int>.

Учитывая ответы, которые я получаю (спасибо сообществу Stack Overflow ...), метод, который я описываю, не очень известен. Причина, по которой я хочу неупорядоченную карту отпечатков пальцев вместо строк, заключается в пространстве и скорости. Вторая карта не должна хранить строки, и при поиске она не приводит к дополнительным потерям кэша для извлечения этих строк. Единственным недостатком является небольшая вероятность столкновения. Вот почему ключ должен быть 64 бит: вероятность 2 ^ (- 64) в принципе невозможна. Конечно, это основано на хорошей хэш-функции, и это именно то, что ищет мой вопрос.

Еще раз спасибо, переполнение стека.

Answer 1

unordered_map всегда хэширует ключ в переменной size_t. Это не зависит от типа ключа и зависит исключительно от архитектуры, с которой вы работаете.

Answer 2

c ++ не имеет собственного 128-битного типа и не имеет встроенной поддержки хеширования. Такие расширения для хеширования должны быть добавлены в TR1, но, насколько я знаю, 128-битные целочисленные значения не поддерживаются многими моими компиляторами. (Microsoft поддерживает тип __int128 - только на платформах x64)

Я ожидаю, что функции, включенные в unordered_map, будут быстрее в любом случае.

Если вы действительно хотите так поступить, MD5 предоставляет хороший 128-битный хэш.

Answer 3

Если вы хотите сопоставить любую строку с уникальным целым числом:

typedef std::map<string,long long> Strings;
static Strings s_strings;
long long s_highWaterMark = 0;
long long my_function(const string& s)
{
  Strings::const_iterator it = s_strings.find(s);
  if (it != s_strings.end())
  {
    //we've previously returned a fingerprint for this string
    //now return the same fingerprint again
    return it->second;
  }
  //else new fingerprint
  long long rc = ++s_highWaterMark;
  //... remember it for next time
  s_strings.insert(Strings::value_type(s, rc));
  //... and return it this time
  return rc;
}

Answer 4

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