c++ - resolucion - tablas hash en java

¿Función hash para un par de largos largos?

Question

Necesito asignar un par de long long a double , pero no estoy seguro de qué función hash usar. Cada par puede constar de dos números cualquiera, aunque en la práctica generalmente serán números entre 0 y aproximadamente 100 (pero, de nuevo, eso no está garantizado).

Here está la documentación de tr1::unordered_map . Comencé así:

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;

En general, nunca estoy seguro de qué función hash usar. ¿Qué es una buena función hash de propósito general?

Answer 1

¿Realmente necesitas un mapa basado en hash? El mapa general basado en un árbol binario funcionará bien siempre y cuando la complejidad garantice que funciona para el problema que está resolviendo.

Answer 2

La forma natural de hacer hash en un par es combinar los hashes de sus componentes de alguna manera. La forma más sencilla es solo con 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

Tenga en cuenta que este hash pares como (1,1) o (2,2) todos a cero, por lo que es posible que desee utilizar una forma más compleja de combinar los hashes de las partes, según sus datos. Boost hace algo como esto:

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

Answer 3

Una sugerencia: eche un vistazo a esta publicación SO: "No entiendo std::tr1::unordered_map " .

Además, la Documentación de Boost sobre los Predicados de Igualdad y los Predicados de Hash también es un buen lugar (así como este example ).

Answer 4

boost::hash forma la biblioteca funcional.

o escribe el tuyo. versión más sencilla = pair.first * max_second_value + pair.second