Bildiğimiz üzere, çarpışma çözümüne yönelik 2 klasik strateji vardır: Ayrı zincirleme ve Açık adresleme.. Net'de HashTable/Dictionary uygulaması için ne tür bir çarpışma çözünürlüğü seçildi?
Hangisinin Hashnet/Dictionary'de .net için seçildiğini merak ediyorum.
Ya da başka bir strateji kullanıldı?
Tüm MSDN'de bu yazıda anlatılan oluyor: .NET Framework'ün Hashtable sınıfı tarafından kullanılan tekniktir rehasing denilen An Extensive Examination of Data Structures Using C# 2.0
... çarpışma çözünürlük tekniği. Son bölümünde, zincirleme olarak bilinen bir çarpışma çözünürlük tekniğini kullanan Dictionary sınıfına bakacağız. aşağıdaki gibi ....
... Rehasing çalışır: karma farklı fonksiyonları, H1 bir dizi var ... Hn ve ekleme veya gelen karma tablosunu bir öğeyi almak, başlangıçta H1 karma işlev kullanılır. Bu, 'u bir çarpışmaya götürürse, bunun yerine H2 denenir ve gerekirse Hn'ye kadar devam eder. Önceki bölüm, başlangıç karma işlevi (H1) olan yalnızca bir karma işlevi gösterdi. Diğer hash fonksiyonları bu fonksiyona çok benzer , sadece çarpımsal bir faktörle farklılaşıyor.
Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize
Dictionary sınıfı fazla yolla birden hashtable'a sınıfından farklıdır: sıra genel olarak, hızlı arama fonksiyonu Hk tanımlanır. Güçlü bir şekilde yazılmasının yanı sıra, Sözlük de zincirleme olarak adlandırılan bir teknik kullanarak Hashtable sınıfından farklı bir çarpışma çözümleme stratejisi kullanır. tarama ile, bir çarpışma durumunda kepçeler listesinde başka bir yuva denendiğini hatırlayın. (Rehashing ile, karma yeniden ve yeni slot denenir.) Ancak zincirleme ile herhangi bir çarpışma tutmak için ikincil bir veri yapısı kullanılır. Özellikle, Sözlüğündeki her bir yuvanın, o kola eşlenen bir dizi öğe vardır. Bir çarpışma durumunda olayında, çarpışma elemanı kepçelerin listesine eklenir.
sadece ilk cümlesini hatırla aslında gerçekten ilginç bir soru benim kendi :-)
A 'Dictionary', çarpışmaları tutacak ikincil bir veri yapısına sahip değil. En azından C# 4'de değil. – Gabe
@Gabe: Belki başka bir açıklama veya link verebilir misiniz? – Seb
@Gabe: Detaylandırır mısınız? Bu bana sözlük
olduğu; Ben sadecesahne arkasında uygulanan bir blog post yaptım. Daha sonra bir tane Hashtable'u kapsayabilir.
İyi soru. Bu soruyu göndermemiş olsaydın muhtemelen o gazeteye bakmazdım. –