So finden/implementieren Sie eine gute Hash -Funktion für Bitset ⇐ C++

[Anonymous]

Ich versuche, nicht ordnungsgemäß zu verwenden, in dem der Schlüssel (in Bitset gespeichert) durch Morton -Codierung erzeugt wird. Ich habe mehrere Fälle getestet, in denen sich der Schlüssel im Bereich von 2^0-2^6, 2^3-2^9 befindet (die letzten 3 Bit sind Null), 2^6-2^12 (die letzten 6 Bits sind Null) und 2^9-2^15 (die letzten 9 Bits sind Null). Die Zeit, um ein Element in der nicht ordnungsgemäßen Fälle für alle Fälle zu suchen, liegt in der gleichen Reihenfolge und erhöht sich monoton mit der Größe des Containers. Ich benutze die Hash -Funktion < /p>

class my_bitset_hash
{
public:
size_t operator()(const bitset& key) const
{
size_t hashVal = 0;
hashVal = key.to_ullong();
return hashVal;
}
};
< /code>

Die Zeit für die Suche nach einem Element, in dem der Schlüssel im Bereich von 2^9-2^15 liegt, beträgt mindestens zwei Ordnungen von Größen, die größer sind als der, wenn sich der Schlüssel im Bereich von 2^0-2^6 befindet, auch wenn die Größe des Entlassenen_Map gleich ist. Soweit ich weiß, sollte, wenn es keine Kollision gibt, der Zeitverbrauch für das Nachschlagen am niedrigsten und die Zeitkomplexität O (1) sein. Darüber hinaus benötigen alle Fälle mehr Zeit, um nach der Standardfunktion zu suchen.>