C++: hash tablosunda

Question

kepçelerin sayısını kullanan unordered_set için özel bir hash işlevi yazmak Coord sınıfı (2 boyutlu koordinatlar) için özel bir karma işlevi yazıyorum.

Aşağıdaki karma işlevini değiştirmek mümkün mü, unordered_set hash tablosundaki geçerli geçerli küme sayısıdır ve kepçelerin sayısı değiştirilirse değişir mi?

namespace std 
{ 
    template <> 
    struct hash<Coord> 
    { 
     size_t operator()(const Coord &k) const 
     { 
      int b = 11; 

      int a1 = static_cast<int> (pow(b,(1.0/3.0))); 
      int a2 = static_cast<int> (pow(b,(2.0/3.0))); 

      return ((a1*k.getX() + a2*k.getY()) % b); 
     } 
    }; 
} 

Answer 1

Bunun iyi bir fikir olduğunu sanmıyorum çünkü karma tablosu büyüdüğünde, tüm karmalarınız mevcut öğeleri etkileyecek. Sadece a1*k.getX() + a2*k.getY()'a dönün ve karma tablosu uygulaması sizin için gerekli modulo parçasını yapacağız.

struct MyHash { 
    std::size_t bucket_count; 
    size_t operator()(const Coord &k) const { 
    int a1 = static_cast<int> (pow(b,(1.0/3.0))); 
    int a2 = static_cast<int> (pow(b,(2.0/3.0))); 
    return ((a1*k.getX() + a2*k.getY()) % bucket_count); 
    } 
}; 

Answer 2

sadece taşınabilir ve etkili yöntemdir hesaplamak şudur: (sadece resimde, bunu yapmayın) std::unordered_map::bucket_count() yoluyla bölüm sayısını almak ve karma nesnesinde saklayabilirsiniz söyledi

std :: size_t aralığından olabildiğince eşit dağıtılan karmalar. Belirli bir anahtar için, karma işlevinin, programın süresi boyunca aynı karma kodunu döndürmesi önemlidir. Sırasız harita arttıkça, kendini yeniden şekillendirecektir. Anahtarlar değiştirilemediğinden, yeni kepçelerin hesaplanması için yeni kepçe sayımının anahtarlara iletilmesi mümkün olmayacaktır (ki bu durumda her durumda haritada modüle tabi olacaktır).

ileri giderek:

(örneğin, referanslar veya değişken veri üyeleri aracılığıyla) tuşuna bir kova sayımını iletişim Aradığınız sadece gözyaşları içinde sona erecek ve bir hata olacaktır.

Bir sorun bu çift haritası sınıfına bu tuş sınıf olur o - o bunu Rehash üzere olduğunu uyarmaya ile

hala

kötüsü, sırasız haritası iletişim kurmaz ... yeterince kötü ama . Bir öğeyi ekledikten sonra bunu keşfetmeniz gerekir. Bu, haritadaki tüm öğelerin artık eski bir kova sayısına bağlı olarak karma olduğunu gösterir. Haritaya çoğaltmayı denemek, büyük olasılıkla haritanın semantiğini bozarak işe yarıyor!

Bunu yapmak için, her ekleme işleminden sonra, tüm öğeleri bir vektör içine almanız gerekir, bunların karmalarını yeniden hesaplayın ve sonra yeniden takın.

Horrific !!!

Lütfen bana, sizi bu kıyamet yolunda yürümemeye ikna ettiğimi söyleyin.