Java'da Ağaç Haritası

Bu makaleyi okuyorsanız, muhtemelen Harita arayüzüne ve uygun şekilde uygulanabileceği yerlere aşinasınızdır. Değilse, o zaman buraya gel . Bugün Java TreeMap uygulamasının özelliklerinden ve daha spesifik olarak HashMap'ten ne kadar farklı olduğundan ve nasıl doğru kullanılacağından bahsedeceğiz.

TreeMap, HashMap ve LinkedHashMap'i Karşılaştırma

Harita arayüzünün en çok kullanılan uygulaması HashMap'tir. Kullanımı kolaydır ve verilere hızlı erişimi garanti eder, bu nedenle çoğu sorunu çözmek için en iyi adaydır. Çoğu, ama hepsi değil. Bazen verileri yapılandırılmış bir şekilde depolamanız ve bunlar arasında gezinebilmeniz gerekir. Bu durumda, Harita arayüzünün (TreeMap) başka bir uygulaması imdada yetişir. TreeMap, Sırasıyla Harita arabirimini devralan SortedMap öğesini devralan NavigableMap arabirimini uygular . TreeMap, NavigableMap ve SortedMap arayüzlerini uygulayarak HashMap'te bulunmayan ek işlevler alır, ancak performans açısından bir bedel öder. Ayrıca LinkedHashMap varAyrıca, verileri belirli bir sırayla (haritaya eklediğiniz sırayla) depolamanıza olanak tanıyan class . Bu üç sınıf arasındaki farkları anlamak için şu tabloya bakın: Gördüğünüz gibi, bu sınıfların pek çok ortak noktası var, ancak aynı zamanda birkaç farklılık da var. TreeMap sınıfı en çok yönlü olmasına rağmen, null'u her zaman bir anahtar olarak depolayamaz . Ek olarak, bir TreeMap'in öğelerine erişmek en uzun süreyi alır. Bu nedenle, verileri belirli bir düzende depolamanız gerekmiyorsa, HashMap veya LinkedHashMap kullanmak daha iyidir .

kırmızı-siyah ağaç

Muhtemelen, TreeMap'in kaputun altında kırmızı-siyah ağaç adı verilen bir veri yapısı kullandığını fark etmişsinizdir. Verilerin bu yapıda saklanması, tam olarak veri sıralamasını sağlayan şeydir. Peki bu ne tür bir ağaç? Hadi çözelim! Number-String çiftlerini saklamanız gerektiğini düşünün. 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93 ve 101 sayıları anahtar olacaktır. Verileri geleneksel bir listede saklıyorsanız ve 101 anahtarına sahip öğeyi bulmanız gerekiyorsa, onu bulmak için 13 öğenin tümünü adım adım tamamlamanız gerekir. 13 element için bu çok büyük bir sorun değil ama bir milyonla çalışırken büyük sorunlarımız olacak. Bu sorunları çözmek için programcılar biraz daha karmaşık veri yapıları kullanırlar. Kırmızı-siyah ağacın sahneye girdiği yer burası!Bir öğeyi aramak, bizim durumumuzda 61 olan ağacın kökünde başlar. Ardından, düğüm değerlerini aradığımız değerle karşılaştırırız. Değerimiz daha az ise sola gidiyoruz; daha büyükse, sağa gideriz. Bu süreç, istenen değeri bulana veya değeri boş olan bir öğeyle (ağacın bir yaprağı) karşılaşana kadar tekrar eder. Ağaçta gezinmeyi ve dengeyi basitleştirmek için kırmızı ve siyah renkler kullanılmıştır. Kırmızı-siyah bir ağaç inşa ederken her zaman uyulması gereken kurallar vardır:

• Kök siyah olmalıdır.
• Ağacın yaprakları siyah olmalıdır.
• Bir kırmızı düğümün iki siyah alt düğümü olmalıdır.
• Siyah bir düğüm, herhangi bir renkteki alt düğümlere sahip olabilir.
• Bir düğümden yapraklarına giden yol, aynı sayıda siyah düğüm içermelidir.
• Yapraklara yeni düğümler eklenir.

Kural 3, 4 ve 5'i birlikte ele alırsanız, düğüm renginin ağaçta daha hızlı gezinmemizi nasıl sağladığını anlayabilirsiniz: siyah düğümlerden geçen bir yol her zaman kırmızı düğümlerden geçen yoldan daha kısadır. Buna göre ağacın toplam boyutu, "siyah yükseklik" olarak adlandırılan siyah düğümlerin sayısına göre belirlenir. Kırmızı-siyah ağaç veri yapısı, çeşitli programlama dillerinde uygulanmaktadır. İnternette pek çok Java uygulaması var, bu yüzden burada oyalanmayacağız. Bunun yerine, TreeMap'in işlevselliğini tanımaya devam edelim.

SortedMap ve NavigableMap arayüzlerinden gelen yöntemler

HashMap gibi, TreeMap de Harita arayüzünü uygular, bu da TreeMap'in HashMap'te bulunan tüm yöntemlere sahip olduğu anlamına gelir. Ancak TreeMap, SortedMap ve NavigableMap arayüzlerini de uygular ve böylece bunlardan ek işlevsellik kazanır. SortedMap , Haritayı genişleten ve sıralanmış bir veri kümesiyle ilgili yöntemler ekleyen bir arabirimdir :

• firstKey() : haritadaki ilk öğenin anahtarını döndürür
• lastKey() : son öğenin anahtarını döndürür
• headMap(K end) : geçerli haritanın tüm öğelerini baştan anahtar uçlu öğeye kadar içeren bir harita döndürür
• tailMap(K start) : geçerli haritanın başlangıç ​​öğesinden sonuna kadar tüm öğelerini içeren bir harita döndürür
• subMap(K start, K ​​end) : başlangıç ​​öğesinden anahtar uçlu öğeye kadar geçerli haritanın tüm öğelerini içeren bir harita döndürür.

NavigableMap , SortedMap'i genişleten ve bir haritanın öğeleri arasında gezinmek için yöntemler ekleyen bir arabirimdir:

• firstEntry() : ilk anahtar/değer çiftini döndürür
• lastEntry() : son anahtar/değer çiftini döndürür
• pollFirstEntry() : ilk çifti döndürür ve siler
• pollLastEntry() : son çifti döndürür ve siler
• tavanKey(K nesne) : anahtar nesneden büyük veya ona eşit olan en küçük k anahtarını döndürür. Böyle bir anahtar yoksa, null döndürür
• floorKey(K nesne) : anahtar nesneden küçük veya ona eşit olan en büyük k anahtarını döndürür. Böyle bir anahtar yoksa, null döndürür
• lowerKey(K nesne) : anahtar nesneden küçük olan en büyük k anahtarını döndürür. Böyle bir anahtar yoksa, null döndürür
• highKey(K nesne) : anahtar nesneden daha büyük olan en küçük k anahtarını döndürür. Böyle bir anahtar yoksa, null döndürür
• tavanEntry(K obj) : tavanKey(K obj) yöntemine benzer, yalnızca bir anahtar/değer çifti (veya boş) döndürür
• floorEntry(K obj) : floorKey(K obj) yöntemine benzer, yalnızca bir anahtar/değer çifti (veya null) döndürür
• lowerEntry(K obj) : lowerKey(K obj) yöntemine benzer, yalnızca bir anahtar/değer çifti (veya null) döndürür
• highEntry(K obj) : highKey(K obj) yöntemine benzer, yalnızca bir anahtar/değer çifti (veya null) döndürür
• azalanKeySet() : ters sırada sıralanmış tüm anahtarları içeren bir NavigableSet döndürür
• azalanMap() : ters sırada sıralanmış tüm çiftleri içeren bir NavigableMap döndürür
• navigableKeySet() : saklandıkları sırayla tüm anahtarları içeren bir NavigableSet nesnesi döndürür
• headMap(K UpperBound, boolean incl) : Baştan UpperBound öğesine kadar çiftler içeren bir harita döndürür. incl parametresi, üst Sınır öğesinin döndürülen haritaya dahil edilip edilmeyeceğini belirtir.
• tailMap(K lowerBound, boolean incl) : önceki yönteme benzer işlevsellik, yalnızca lowerBound'dan sona çiftleri döndürür
• subMap(K lowerBound, boolean lowIncl, K UpperBound, boolean highIncl) : önceki yöntemlerde olduğu gibi, lowerBound'dan UpperBound'a çiftler döndürür; lowIncl ve highIncl bağımsız değişkenleri, sınır öğelerinin yeni haritaya dahil edilip edilmeyeceğini belirtir.

Olağan oluşturuculara ek olarak, TreeMap'in bir karşılaştırıcı örneğini kabul eden başka bir oluşturucusu vardır. Bu karşılaştırıcı, öğelerin depolanma sırasından sorumludur.

Ağaç Haritası örnekleri

Bu fazladan yöntem bolluğu gereksiz görünebilir, ancak ilk bakışta fark edebileceğinizden çok daha yararlı oldukları ortaya çıkar. Aşağıdaki örneği birlikte inceleyelim. Büyük bir şirketin pazarlama departmanında çalıştığımızı ve reklam göstermek istediğimiz kişilerden oluşan bir veri tabanımız olduğunu hayal edin. Akılda tutulması gereken iki ayrıntı vardır:

• Her kişi için gösterim sayısını takip etmemiz gerekiyor
• Reşit olmayanlara reklam gösterme algoritması farklıdır.

Her kişiyle ilgili tüm bilgileri depolayacak bir Kişi sınıfı oluşturalım :

public class Person {
   public String firstName;
   public String lastName;
   public int age;

   public Person(String firstName, String lastName, int age) {
       this.firstName = firstName;
       this.lastName = lastName;
       this.age = age;
   }
}

Mantığı Main sınıfında uyguluyoruz :

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class Main {
   public static void main(String[] args) {
      TreeMap<Person, Integer> map = new TreeMap<>(Comparator.comparingInt(o -> o.age));
      map.put(new Person("John", "Smith", 17), 0);
      map.put(new Person("Ivan", "Petrenko", 65), 0);
      map.put(new Person("Pedro", "Escobar", 32), 0);
      map.put(new Person("Shirley", "Hatfield", 14), 0);
      map.put(new Person("Abby", "Parsons", 19), 0);

      Person firstAdultPerson = map.navigableKeySet().stream().filter(person -> person.age>18).findFirst().get();

       Map<Person, Integer> youngPeopleMap = map.headMap(firstAdultPerson, false);
       Map<Person, Integer> adultPeopleMap = map.tailMap(firstAdultPerson, true);
       showAdvertisementToYoung(youngPeopleMap);
       showAdvertisementToAdult(adultPeopleMap);
   }

   public static void showAdvertisementToYoung(Map map) {}
   public static void showAdvertisementToAdult(Map map) {}
}

Ana sınıfta, her anahtarın belirli bir kişiyi temsil ettiği ve her değerin bu ayki reklam gösterimlerinin sayısı olduğu bir Ağaç Haritası oluşturun. Yapıcıya, insanları yaşa göre sıralayan bir karşılaştırıcı aktarıyoruz. Haritayı keyfi değerlerle dolduruyoruz. Şimdi küçük veri havuzumuzdaki ilk yetişkine bir referans almak istiyoruz. Bunu Stream API kullanarak yapıyoruz. Ardından reklam gösteren yöntemlere geçtiğimiz iki ayrı harita elde ediyoruz. Bu görevi başarabilmemizin birçok yolu var. TreeMap sınıfının yöntem cephaneliği, her ihtiyaç için özel çözümler oluşturmamızı sağlar. Hepsini hatırlamanıza gerek yok, çünkü IDE'nizdeki belgeleri veya ipuçlarını her zaman kullanabilirsiniz. Öğrendiklerinizi pekiştirmek için Java Kursumuzdan bir video dersi izlemenizi öneririz. Şimdilik bu kadar! Umarım TreeMap sınıfı artık sizin için anlaşılırdır ve onu pratik kodlama görevlerini çözerken doğru şekilde uygulayabilirsiniz.