Hash-Funktion für ein Paar lange lang?

Ich brauche die Karte ein paar long long zu einem doubleaber ich bin mir nicht sicher, was hash-Funktion zu verwenden. Jedes paar besteht aus zwei zahlen, obwohl Sie in der Praxis wird in der Regel zahlen zwischen 0 und über 100 (aber auch das ist nicht garantiert).

Hier ist die tr1::unordered_map Dokumentation. Ich begann so:

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;

Im Allgemeinen, ich bin mir nie sicher, was hash-Funktion zu verwenden. Was ist ein guter Allzweck-hash-Funktion?

InformationsquelleAutor der Frage | 2009-04-10

  1. 11

    Den natürlichen Weg, um hash-paar kombinieren Sie die hashes der Komponenten in irgendeiner Weise. Die am meisten einfache Weise ist nur mit 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

    Beachten Sie, dass diese hashes Paare wie (1,1) oder (2,2) alle auf null, so möchten Sie vielleicht noch etwas komplexer Weise zu kombinieren, die hashes von den teilen, je auf Ihre Daten. Boost macht etwas in dieser Art:

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

    InformationsquelleAutor der Antwort sth

  2. 10

    boost::hash form funktionale Bibliothek.

    oder schreiben Sie Ihre eigenen. einfachste version = pair.erste * max_second_value + pair.zweite

    InformationsquelleAutor der Antwort bayda

  3. 2

    Einen Vorschlag: werfen Sie einen Blick auf dieser post SO: "Ich verstehe nicht, std::tr1::unordered_map".

    Auch, die Boost-Dokumentation auf Gleichheit von Prädikaten und Hash-Prädikate ist ein guter Ort zu (sowie diese Beispiel).

    InformationsquelleAutor der Antwort dirkgently

  4. 1

    Brauchen Sie wirklich einen hash-basierten Karte? Die übersichtskarte basiert auf einer binären Struktur funktioniert gut, solange die Komplexität garantiert, es macht die Arbeit für das problem, das Sie lösen müssen.

    InformationsquelleAutor der Antwort lothar

Schreibe einen Kommentar