HashMap,LinkedHashMap ve TreeMap çalışma yapısı

LinkedHashMap ve TreeMap, Java'da kullanılan iki farklı türde harita (map) yapısıdır ve farklı çalışma prensiplerine sahiptirler. İkisi arasındaki temel farklar şunlardır:

Sıralama ve İç Yapı:

LinkedHashMap:

LinkedHashMap, elemanları eklendiği sırayla saklar. Yani, bir anahtar-değer çifti eklediğinizde, bu çiftin sırası korunur.

İç yapısı, HashMap ile benzerdir ama ek olarak bir çift yönlü bağlı liste (doubly linked list) kullanarak sıralama bilgisini tutar.

TreeMap:

TreeMap, elemanları bir karşılaştırma mantığına göre sıralar. Varsayılan olarak doğal sıralama kullanılır (örneğin, sayısal veya alfabetik sıralama), ama özel bir Comparator da belirtilebilir.

İç yapısı kırmızı-siyah ağaç (red-black tree) temellidir. Bu, elemanların dengeli bir şekilde saklanmasını ve verimli arama/sıralama operasyonlarını sağlar.

Performans:

LinkedHashMap:

Ekleme, silme ve erişim işlemleri HashMap ile benzer hızdadır çünkü ana işlemler HashMap üzerinden yapılır.

İterasyon, eleman sayısıyla doğru orantılıdır çünkü elemanlar bağlı listede saklanır.

TreeMap:

Ekleme, silme ve arama işlemleri logaritmik zamanda (

O(logn)) gerçekleşir çünkü kırmızı-siyah ağaç yapısı kullanılır.

İterasyon, sıralı erişim gerektiğinde daha verimlidir.

Kullanım Senaryoları:

LinkedHashMap:

Sıralı erişim gereken ama sıralama kriteri eklenme sırası olan durumlar için uygundur.

Örneğin, bir önbellek (cache) yapısı olarak kullanılabilir, burada en eski elemanlar kolayca bulunup silinebilir.

TreeMap:

Doğal sıralamaya veya özel bir sıralama kriterine ihtiyaç duyulan durumlar için idealdir.

Örneğin, bir anahtar kümesinin sıralı tutulması gereken durumlarda kullanışlıdır.

Her iki yapı da Java Collections Framework'ün bir parçasıdır ve Map arayüzünü uygular. Hangisinin kullanılacağı, uygulamanın ihtiyaçlarına ve spesifik performans gereksinimlerine bağlıdır.

User

LinkedHashMap'de bağlı listede key'ler mi saklanır?

ChatGPT

Evet, LinkedHashMap'de bağlı listede anahtarlar (keys) saklanır. Ancak, bu sadece anahtarların saklandığı anlamına gelmez; aslında, LinkedHashMap'de her bir anahtar-değer çifti (entry), hem HashMap'in iç yapısında hem de içsel bir çift yönlü bağlı liste (doubly linked list) yapısında tutulur. Bu yapının amacı, elemanların ekleme sırasına göre sıralanmasını ve hızlı erişimini sağlamaktır.

İşleyişi şu şekildedir:

Her bir anahtar-değer çifti, HashMap'in hash tablosunda saklanır. Bu, anahtar üzerinden hızlı erişim ve arama operasyonlarını sağlar.

Aynı zamanda, her çift bir çift yönlü bağlı listeye de eklenir. Bu liste, elemanların eklendiği sırayı korur.

İterasyon yapılırken veya sıralı erişim gerektiğinde, bu çift yönlü bağlı liste kullanılır, böylece elemanlar eklendiği sırayla erişilebilir.

Bu yapı, LinkedHashMap'in hem hızlı anahtar bazlı erişim sağlamasını hem de elemanların eklendiği sırayı korumasını mümkün kılar. Bu özellik, özellikle belirli türde önbellekleme sistemleri veya sıra önemli olan veri yapıları için yararlıdır.

Yani hem hah table hem de bağlı listede ayrı auyrı tutuyor

Evet, doğru. LinkedHashMap hem hash tablosu hem de çift yönlü bağlı liste (doubly linked list) kullanarak anahtar-değer çiftlerini (entries) saklar. Bu iki yapı birlikte çalışarak LinkedHashMap'in benzersiz işlevselliğini oluşturur:

Hash Tablosu:

Hash tablosu, HashMap ile aynı prensiple çalışır.

Anahtarların hash kodları hesaplanır ve bu kodlara göre anahtar-değer çiftleri tabloda saklanır.

Bu yapı, anahtarlar üzerinden hızlı erişim (arama, ekleme, silme) sağlar.

Çift Yönlü Bağlı Liste:

Her anahtar-değer çifti, ayrıca bir çift yönlü bağlı listede de tutulur.

Bu liste, elemanların eklendiği ya da son erişildiği sıraya göre düzenlenir (bu, LinkedHashMap'in oluşturulma şekline bağlıdır).

Liste, iterasyon sırasında sıralı erişim için kullanılır, böylece elemanlar ekleme sırasına göre döndürülür.

Bu iki yapı bir arada, LinkedHashMap'e hem hızlı anahtar bazlı erişim hem de elemanların sıralı tutulmasını sağlama yeteneği kazandırır. Bu, LinkedHashMap'i özellikle önbellekleme gibi sıralı erişimin önemli olduğu uygulamalar için uygun bir seçim yapar.

HashMap'de bağlı liste kullanılır mı?

HashMap'de bağlı liste kullanılır, ancak bu LinkedHashMap'deki kullanımından farklı bir amaç için kullanılır. HashMap'in iç yapısında, çakışmaları (collisions) yönetmek için bağlı listeler kullanılır. İşte bu kullanımın ayrıntıları:

Hash Çakışmaları ve Bağlı Listeler:

HashMap bir anahtarı hash koduna dönüştürerek, bu kodu kullanarak anahtar-değer çiftini bir dizinde saklar.

Farklı anahtarlar aynı hash kodunu üretebilir (bu duruma "hash çakışması" denir). Böyle bir durumda, HashMap aynı dizin içindeki elemanları bir bağlı liste şeklinde saklar.

Bu bağlı liste, çakışan tüm anahtar-değer çiftlerini birbirine bağlar, böylece aynı hash koduna sahip çiftler aynı "kova" (bucket) içinde yönetilebilir.

Java 8'den İtibaren Geliştirmeler:

Java 8 ile birlikte, HashMap'in bu yapısında bir iyileştirme yapıldı. Eğer bir kovadaki eleman sayısı belirli bir eşiği aşarsa, bağlı liste yapısı, daha verimli aramalar sağlayan dengeli bir ağaca (red-black tree) dönüştürülür.

Bu değişiklik, büyük ve yoğun HashMap yapılarında performansı önemli ölçüde iyileştirmektedir.

HashMap ve LinkedHashMap arasındaki önemli bir fark, LinkedHashMap'in elemanları eklenme sırasına göre saklaması ve iterasyon sırasında bu sırayı korumasıdır. Buna karşın, HashMap'de elemanlar sırasız bir şekilde saklanır ve iterasyon sırası öngörülemezdir. Bu farklılıklar, her iki yapının farklı kullanım senaryolarına uygun olmasını sağlar.