Функция хэша для пары длинного длинного?

Question

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

Here - это документация 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

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

Answer 2

Предложение: Взгляните на это сообщение SO: "I don't understand std::tr1::unordered_map".

Кроме того, документация Boost на Equality Predicates and Hash Predicates также является хорошим местом (также как и example).

Answer 3

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

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

Answer 4

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

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) все к нулю, так что вы можете использовать некоторые более сложный способ объединить хэшей частей, в зависимости от ваших данных. Подталкивания делает что-то вроде этого:

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