Ха sh алгоритмы, используемые в C ++ std - PullRequest
Новая
       4

Ха sh алгоритмы, используемые в C ++ std

1 голос
/ 28 марта 2020

Я ищу информацию о том, какой алгоритм sh используется в специализации C ++ std::hash<std::string>. Самое близкое, что я мог получить, - это информация из моего include/c++/7/bits/basic_string.h: 

  /// std::hash specialization for string.
  template<>
    struct hash<string>
    : public __hash_base<size_t, string>
    {
      size_t
      operator()(const string& __s) const noexcept
      { return std::_Hash_impl::hash(__s.data(), __s.length()); }
    };

Затем include/c++/7/bits/functional_hash.h: 

  struct _Hash_impl
  {
    static size_t
    hash(const void* __ptr, size_t __clength,
     size_t __seed = static_cast<size_t>(0xc70f6907UL))
    { return _Hash_bytes(__ptr, __clength, __seed); }

    template<typename _Tp>
      static size_t
      hash(const _Tp& __val)
      { return hash(&__val, sizeof(__val)); }

    template<typename _Tp>
      static size_t
      __hash_combine(const _Tp& __val, size_t __hash)
      { return hash(&__val, sizeof(__val), __hash); }
  };

И наконец include/c++/7/bits/hash_bytes.h: 

  // Hash function implementation for the nontrivial specialization.
  // All of them are based on a primitive that hashes a pointer to a
  // byte array. The actual hash algorithm is not guaranteed to stay
  // the same from release to release -- it may be updated or tuned to
  // improve hash quality or speed.
  size_t
  _Hash_bytes(const void* __ptr, size_t __len, size_t __seed);

На самом деле есть два вопроса:

  1. Означает ли это, что C ++ использует одни и те же алгоритмы ha sh для всех нетривиальных типов данных?
  2. Какой алгоритм использует C ++ использует для _Hash_bytes?

1 Ответ

2 голосов
/ 28 марта 2020

Детали га sh функции оставлены как детали реализации. Ха sh должен возвращать одно и то же значение во время выполнения программы для двух одинаковых значений, и возвращаемые хэши должны быть равномерно распределены по диапазону возвращаемого значения. (Не требуется, чтобы ha sh возвращала одно и то же значение в разных исполнениях, позволяет использовать соленые хэши.)

Поскольку функция Hash_bytes является функцией c, определяемой реализацией (имя, начинающееся с с и подчеркиванием, за которым следует заглавная буква (является зарезервированным идентификатором реализации), поэтому вам придется поискать это в исходном коде библиотеки вашей реализации, чтобы увидеть, что он делает.

...