Eine gute hash-Funktion für einen Vektor

Habe ich einige Vektor von integer, die ich speichern möchten effizient in einer unordered_map in c++11 meine Frage ist:

Wie kann ich Sie am besten speichern Sie diese und optimieren Sie für .find Abfragen?

Ich kam mit der folgenden hasher:

class uint32_vector_hasher {
public:
  std::size_t operator()(std::vector<uint32_t> const& vec) const {
    std::size_t ret = 0;
    for(auto& i : vec) {
      ret ^= std::hash<uint32_t>()(i);
    }
    return ret;
  }
};

und speichern Sie dann die Objekte in eine unordered_map ich haben jedoch ein paar Fragen

  1. wie oft wird der hash berechnet bekommen, nur eine, einige zufällige Anzahl oder die Zeiten?
  2. Würde es Sinn machen, erstellen Sie ein wrapper-Objekt mit == - und hash-Funktionen zu machen, merken Sie sich den hash und vermeiden Sie berechnet werden, mehr als einmal?

Beim profiling ich habe bemerkt, dass eine ziemlich große Menge von meinem cpu-Zeit verbringen zu tun lookups auf die ungeordneten Karten, das ist nicht gerade optimal 🙁

InformationsquelleAutor der Frage Martin Kristiansen | 2013-12-11

  2. 18

    So, wenn Sie nicht wollen, um boost, Michael Unschärfe Kommentar führte zu der folgenden hash-Funktion Implementierung:

    std::size_t operator()(std::vector<uint32_t> const& vec) const {
  std::size_t seed = vec.size();
  for(auto& i : vec) {
    seed ^= i + 0x9e3779b9 + (seed << 6) + (seed >> 2);
  }
  return seed;
}

    Scheint zu funktionieren.

    InformationsquelleAutor der Antwort HolKann

Schreibe einen Kommentar