Общая хеш-функция для всех STL-контейнеров - PullRequest
Новая
       49

Общая хеш-функция для всех STL-контейнеров

11 голосов
/ 01 августа 2011

Я использую std::unordered_map<key,value> в моей реализации.Я буду использовать любой из контейнеров STL в качестве ключа.Мне было интересно, возможно ли создать универсальную хеш-функцию для любого используемого контейнера.

Этот вопрос в SO предлагает общую функцию печати для всех контейнеров STL.Хотя вы можете иметь это, почему у вас не может быть что-то вроде хэш-функции, которая определяет все?И да, большое беспокойство вызывает то, что это нужно быстро и эффективно.

Я думал о создании простой хеш-функции, которая преобразует значения ключа в size_t и выполняет простую функцию, такую ​​как this .

Можно ли это сделать?

PS: Пожалуйста, не используйте boost библиотеки.Спасибо.

1 Ответ

15 голосов
/ 01 августа 2011

Мы можем получить ответ, имитируя Boost и комбинируя хеши.

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

В любом случае:

Прежде всего, нам нужна функция hash_combine.По независящим от меня причинам он не был включен в стандартную библиотеку, но он является центральным элементом всего остального: 

template <class T>
inline void hash_combine(std::size_t & seed, const T & v)
{
  std::hash<T> hasher;
  seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

Используя это, мы можем хэшировать все, что состоит из хешируемых элементов, в частности пары и кортежи(упражнение для читателя).

Однако мы также можем использовать это для хеширования контейнеров путем хеширования их элементов.Это именно то, что делает "хэш диапазона" в Boost, но просто сделать это самостоятельно, используя функцию объединения.

Как только вы закончите написание хеша диапазона, просто специализируйте std::hash и вы 'хорошо бы пойти: 

namespace std
{
  template <typename T, class Comp, class Alloc>
  struct hash<std::set<T, Comp, Alloc>>
  {
    inline std::size_t operator()(const std::set<T, Comp, Alloc> & s) const
    {
      return my_range_hash(s.begin(), s.end());
    }
  };

  /* ... ditto for other containers */
}

Если вы хотите подражать хорошему принтеру, вы могли бы даже сделать что-то более экстремальное и специализировать std::hash для всех контейнеров, но я, вероятно, был бы более осторожен с этим исоздать явный хеш-объект для контейнеров: 

template <typename C> struct ContainerHasher
{
  typedef typename C::value_type value_type;
  inline size_t operator()(const C & c) const
  {
    size_t seed = 0;
    for (typename C::const_iterator it = c.begin(), end = c.end(); it != end; ++it)
    {
      hash_combine<value_type>(seed, *it);
    }
    return seed;
  }
};

Использование: 

std::unordered_map<std::set<int>, std::string, ContainerHasher<std::set<int>>> x;
...