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

Мне нужно сопоставить пару 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;

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

Ответы

Ответ 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);

Ответ 2

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

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

Ответ 4

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