Giriş
Bir çok programlama dilinde HashMap, HashSet gibi veri yapıları hazır geliyor. Gömülü ortamlarda ise bu veriyapılarını kodlamak gerekebiliyor. Aşağıda bu tür veriyapılarını geliştirirken aldığım notlar var
HashMap
Mükemmel hash fonksiyonu olmadığı için iki farklı değerin aynı hash sonucunu üretmesi çok mümkün. Bu durumda Çarpışma Çözümü (Collision Resolution) yapmak gerekiyor. Çözüm olarak iki farklı yöntem yaygınca kullanılıyor. İlki Open Addressing ve Separate Chaining.
OpenAddressing
Bu yöntem lookup tablosu gibi salt okunur veriyapılarında kullanışlı. Eğer bucket dolu ise bir sonraki boş bucket aranır. Kodlaması kolaydır. HashMap bucket büyüklüğü yeterince büyük tutulursa çok fazla çakışma olmayacağı için performansı da iyidir.
Separate Chaining
Bu yöntem eğer veriyapısı salt okunur değilse tercih etmek lazım. Ekleme silme işlemlerini daha iyi yerine getirir. Hash metodunun denk geldiği bucket bir LinkedList tutar. Yeni veri liste üzerinde yürünerek sona eklenir. Çarpışma Çözümü (Collision Resolution) için ikili ağaç (binary tree) kullanılabileceği de yazılı ancak ben hiç denk gelmedim.
HashSet
HashSet -> Buckets ->LinkedList ->ListNode şeklinde Separate Chaining kullanılır. Eğer Object Oriented bir yöntem izlenirse nesnenin HashValue() ve Equals metodları da olması beklenir.
Bir çok programlama dilinde HashMap, HashSet gibi veri yapıları hazır geliyor. Gömülü ortamlarda ise bu veriyapılarını kodlamak gerekebiliyor. Aşağıda bu tür veriyapılarını geliştirirken aldığım notlar var
HashMap
Mükemmel hash fonksiyonu olmadığı için iki farklı değerin aynı hash sonucunu üretmesi çok mümkün. Bu durumda Çarpışma Çözümü (Collision Resolution) yapmak gerekiyor. Çözüm olarak iki farklı yöntem yaygınca kullanılıyor. İlki Open Addressing ve Separate Chaining.
OpenAddressing
Bu yöntem lookup tablosu gibi salt okunur veriyapılarında kullanışlı. Eğer bucket dolu ise bir sonraki boş bucket aranır. Kodlaması kolaydır. HashMap bucket büyüklüğü yeterince büyük tutulursa çok fazla çakışma olmayacağı için performansı da iyidir.
Separate Chaining
Bu yöntem eğer veriyapısı salt okunur değilse tercih etmek lazım. Ekleme silme işlemlerini daha iyi yerine getirir. Hash metodunun denk geldiği bucket bir LinkedList tutar. Yeni veri liste üzerinde yürünerek sona eklenir. Çarpışma Çözümü (Collision Resolution) için ikili ağaç (binary tree) kullanılabileceği de yazılı ancak ben hiç denk gelmedim.
HashSet
HashSet -> Buckets ->LinkedList ->ListNode şeklinde Separate Chaining kullanılır. Eğer Object Oriented bir yöntem izlenirse nesnenin HashValue() ve Equals metodları da olması beklenir.
Hiç yorum yok:
Yorum Gönder