Хэш-функция для пары long long?

Question

Мне нужно сопоставить пару long long с double, но я не уверен, какую хеш-функцию использовать. Каждая пара может состоять из любых двух чисел, хотя на практике они обычно будут числами от 0 до 100 (но опять же, это не гарантируется).

Здесь - документация tr1::unordered_map. Я начал так:

typedef long long Int;
typedef std::pair<Int, Int> IntPair;

struct IntPairHash {
  size_t operator(const IntPair& p) const {
    return ...; // how to hash the pair?
  }
};

struct IntPairEqual {
  bool operator(const IntPair& a, const IntPair& b) const {
    return a.first == b.first 
      && a.second == b.second;
  }
};

tr1::unordered_map<IntPair, double, IntPairHash, IntPairEqual> myMap;

В общем, я никогда не уверен, какую хеш-функцию использовать. Что такое хорошая хеш-функция общего назначения?

Answer 1

Естественный способ хэширования пары состоит в том, чтобы каким-то образом объединить хэши ее компонентов. Самый простой способ - просто с помощью xor:

namespace std {
namespace tr1 {

template<typename a, typename b>
struct hash< std::pair<a, b> > {
private:
   const hash<a> ah;
   const hash<b> bh;
public:
   hash() : ah(), bh() {}
   size_t operator()(const std::pair<a, b> &p) const {
      return ah(p.first) ^ bh(p.second);
   }
};

}} // namespaces

Обратите внимание, что это хэширует пары, такие как (1,1) или (2,2), все в ноль, поэтому вы можете использовать более сложный способ объединения хэшей частей, в зависимости от ваших данных. Boost делает что-то вроде этого:

size_t seed = ah(p.first);
return bh(p.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);

Answer 2

boost :: hash функциональная библиотека форм.

или напишите свое. простейшая версия = pair.first * max_second_value + pair.second

Answer 3

Предложение: взгляните на этот пост: "Я не понимаю std::tr1::unordered_map" .

Также хорошая документация по Предикаты равенства и хеш-предикаты тоже хорошее место (как и этот пример ).

Answer 4

Вам действительно нужна карта на основе хеша? Общая карта, основанная на двоичном дереве, будет работать нормально, если сложность гарантирует, что она будет работать для решаемой вами проблемы.