Hash özelliği, HashMap ve HashSet gibi hash tabanlı koleksiyonları desteklemek için tasarlanmıştır. Rust standart kütüphanesi, Eq'yi uygulayan her türün aynı zamanda Hash'ı da uygulamasını gerektirir; böylece k1 == k2 ise, hash(k1) == hash(k2) olmalıdır. Bu invariant, hash tablolarının çakışmaları doğru bir şekilde çözmesini sağlar.
Sorun, iki farklı örneğin (Eq'ye göre) eşit olarak karşılaştırılması ve farklı hash özetleri üretmesi durumunda ortaya çıkar. Bu durumda, bir HashMap, bu "eşit" anahtarları farklı kovalar içine yerleştirebilir. Ardışık arama işlemleri mevcut girişleri bulamayabilir veya eklemeler, haritanın benzersiz anahtarlar ile ilgili sözleşmesini ihlal eden çiftler oluşturabilir.
Çözüm, eşitlik ve hashing mantığı arasında bit düzeyinde senkronizasyon sağlamayı gerektirir. Belirli alanları (örneğin, zaman damgaları veya önbelleklenmiş hash'ler) yoksayıp PartialEq ve Eq özelleştirirken, o alanların Hash uygulamasından da dışlanması gerekir. Bu, eşdeğer mantıksal değerlerin her zaman aynı hash kodlarına eşlenmesini ve koleksiyon bütünlüğünün korunmasını sağlar.
Task yapılarının, tamamlanma durumunu takip eden bir HashMap'te anahtar olarak kullanıldığı dağıtık bir görev zamanlayıcısını düşünün. Her Task, bir id: Uuid, payload: Vec<u8> ve timestamp: Instant içerir. Başlangıçta, hem Hash hem de Eq otomatik olarak türetilir. Ancak gereksinimler değişir: görevler, payload veya timestamp'dan bağımsız olarak id'leri eşleştiğinde eşit kabul edilmelidir.
İlk düşünülen çözüm, her iki özelliği otomatik olarak türetmekti #[derive]. Bu yaklaşım, hashing ve eşitlik arasında yapısal tutarlılığı koruyarak tüm alanları içermişti, ancak iş mantığında işlevsel hatalara yol açtı. Özellikle, aynı kimliklere sahip ancak farklı zaman damgalarına sahip görevler farklı anahtarlar olarak kabul edildi; mevcut görevler için durum güncellemelerini önledi ve haritayı eski girişlerle doldurdu.
İkinci çözüm, zaman damgasını yoksayacak şekilde Eq'yi manuel olarak uygularken türetilen Hash'in korunmasıydı. Bu, verimli göründü ama kritik bir hata getirdi. Kimliklerine göre eşit olan iki görev, zaman damgaları farklı olduğunda farklı hash'ler üretecek ve bu da HashMap'in onları ilişkili olmayan kovalar arasında dağıtmasına sebep olacaktı:
impl PartialEq for Task { fn eq(&self, other: &Self) -> bool { self.id == other.id // Zaman damgasını yoksayar } } // #[derive(Hash)] hala zaman damgası dahil tüm alanları hash'ler
Görev durumları için yapılan aramalar, mevcut girişleri rastgele atlayabilir, bu da çift görev yürütülmesine ve kaynak tükenmesine yol açar.
Seçilen çözüm, hem Hash hem de Eq'yi manuel olarak uygulamak oldu ve ikisi de sadece id alanını göz önünde bulundurdu:
impl Hash for Task { fn hash<H: Hasher>(&self, state: &mut H) { self.id.hash(state); // Sadece ID'yi hash'le } }
Bu, mantıksal olarak eşdeğer görevlerin her zaman aynı kovada çarpışmasını garantiledi ve HashMap'in hash çakışmasından sonra eşitlik kontrolleriyle doğru bir şekilde çiftleri tanımlamasına olanak sağladı.
Sonuç, görevlerin çiftlenmesini doğru bir şekilde gerçekleştiren, iki kez yürütmeyi önleyen ve O(1) ortalama arama sürelerini koruyan kararlı bir sistemdi. Bu yaklaşım, dağıtık zamanlayıcının görev tamamlama durumunu bellek sızıntıları veya mantıksal tutarsızlıklar olmadan güvenilir bir şekilde takip etmesini sağladı. Düzeltme, farklı kimlikler arasındaki hash çakışmalarının eşitlik kontrolü tarafından doğru bir şekilde ele alındığını doğrulamak için dikkatli testler gerektirdi ve kısmi eşitlik mantığının standart kütüphanenin hash tablosu uygulamasıyla sorunsuz entegre olduğunu onayladı.
Neden Hash'ın Eq ile tutarlı olması gerekir, ancak mutlaka Ord ile değil?
Eq ile tutarlılık zorunludur çünkü HashMap, bir kovayı bulmak için hash'i kullanır ve ardından o kova içinde çakışmaları çözmek için eşitliği (==) kullanır. Eğer eşit öğeler farklı hash'lere sahip olursa, farklı kovaları işgal ederler ve bu da eşitlik kontrolünü arama sırasında anlamsız hale getirir ve benzersizlik invariantını bozar. Ord ise, sıralı koleksiyonlar için toplam bir sıralama tanımlar; BTreeMap gibi, bu hashing değil, karşılaştırma ağaçlarına dayanır; bu nedenle, Ord ve Hash arasında herhangi bir sözleşmeye dayalı ilişki yoktur. Bir tür, hash'iyle tutarsız bir şekilde sıralanabilir ve bu, bellek güvenliğini veya koleksiyona ait mantığı tehlikeye atmaz.
hash yöntemi bir HashMap'e ekleme sırasında panik olursa ne olur?
Eğer Hash panik olursa, HashMap, anahtarın kısmen işlendiği ancak tam olarak eklenmediği bir ara durumda kalır. Mutex'in aksine, HashMap zehirleme uygulamaz. Ancak, giriş için altındaki bellek ayırma gerçekleşmiş olabilir ve değer tam olarak başlatılmamış veya tablonun zincirine bağlı değildir. Bu, bellek sızıntılarına veya aşırı durumlarda, tablonun boyutunun değiştirilmesi sırasında panik oluşursa belirsiz davranışa yol açabilir. Standart kütüphane, bu durumları azaltmak için düşme koruyucuları ve dikkatli durum yönetimi kullanır, ancak kullanıcı kodu, koleksiyon tutarlılığını güvence altına almak için Hash uygulamalarının paniksiz olmasını sağlamalıdır.
BuildHasher, HashDoS saldırılarını nasıl önler ve neden SipHasher varsayılan olarak seçilmiştir?
BuildHasher, Hasher örneklerinin oluşturulmasını soyutlayarak HashMap'in her harita örneği için rastgele anahtarlarla yeni bir hash oluşturucusu türetmesine olanak tanır. Varsayılan RandomState, anahtarları işletim sisteminin rastgelelik kaynağından üretilen SipHasher-1-3 (veya benzeri bir varyant) ile oluşturur. Bu rastgelelik, bir saldırganın tüm girişlerin aynı kovaya hash'lenmesini sağlayarak O(n)'ye düşüren HashDoS saldırıları gibi saldırıları engeller. Harita her seferinde farklı bir şekilde tohumlandığında, saldırı yüzeyi ortadan kalkar; çünkü saldırgan, hangi girişlerin çarpışacağını tahmin edemez. SipHasher, anahtar kurtarmayı önleyen kriptografik güvenlik ile hız arasında bir denge sağlamak için tercih edilmiştir; MurmurHash gibi daha hızlı ama savunmasız algoritmalara veya SHA-3 gibi daha yavaş kriptografik hash'lere göre.