SıralıHarita

SıralanmışHarita

Bu derste, SortedMap arayüzünü inceleyeceğiz . Bu arabirimde görünen yeni yöntemlerin yanı sıra, SortedMap'in bir uygulamasının ( TreeMap ) özelliklerini ve uygulamalar arasındaki farkları ve bunların HashMap'e kıyasla avantajlarını keşfedeceğiz .

Harita hiyerarşisinin nasıl göründüğüne bakalım. SortedMap arayüzüne ve onun TreeMap uygulamasına özellikle dikkat edin — bugün odak noktamız bunlar:

SortedMap arayüzü , Harita arayüzünü genişletir . Birçok yönden SortedSet'e benzer (ki bu da Set öğesini genişletir ), çünkü her ikisi de sıralanmış değerleri depolamak ve kullanmak için benzer işlevleri tanımlar.

SortedSet, <TValue>ile çalışır ve depolar, ancak SortedMap,<TKey, TValue>çiftlerini depolar. Tüm öğelerini anahtarlarının artan sırasına göre saklayan bir harita.

SortedMap arabirimi , Map öğesini genişletir . Aşağıdaki yöntemleri ekler:

Ağaç Haritası sınıfı

TreeMap sınıfı , SortedMap arabiriminin bir uygulamasıdır . Yani, TreeMap, SortedMap tarafından eklenen tüm yöntemlerin yanı sıra Harita arabirimindeki standart yöntemleri de uygular .

Aşağıdaki gibi oluşturucuları kullanarak bir TreeMap nesnesi oluşturabilirsiniz :

• TreeMap() : ağaç olarak uygulanmış boş bir harita oluşturur;

• TreeMap(Map<?, TKey'i genişletir, ? TValue> haritasını genişletir) : bir ağaç oluşturur ve giriş haritasındaki tüm öğeleri ekler;

• TreeMap(SortedMap<TKey, ? extends TValue> smap) : bir ağaç oluşturur ve giriş sıralanmış haritadaki tüm öğeleri ekler;

• TreeMap(Comparator<? super TKey> comparator) : boş bir ağaç oluşturur — karşılaştırıcı, daha sonra eklenen tüm öğeleri sıralamak için kullanılacaktır.

Burada TKey, saklanan çiftlerdeki anahtarların tipidir ve TValue , TreeMap'te saklanan çiftlerdeki değerlerin tipidir .

Comparator, SortedMap / TreeMap için oldukça önemlidir. Haritamızı sıralamak veya sıralamak için kuralları belirler. Bir karşılaştırıcı sağlamazsak, bir SortedMap oluşturduğumuzda anahtarlarımızın doğal sıralaması kullanılacaktır .

Bir TreeMap'e öğe ekleme

Öğeler , put() yöntemi kullanılarak bir haritaya çiftler halinde eklenir . Anahtar ilk bağımsız değişken olarak iletilir ve değer ikinci olarak iletilir. Örneğin, öğrencilerin ve notlarının bir listesini oluşturmak istediğimizi varsayalım.

SortedMap<String, Integer> map =new TreeMap <String,Integer>();

map.put("Anthony", 5);
map.put("Sara", 5);
map.put("Roxy", 5);
map.put("Jeff", 4);
map.put("Nick", 4);
map.put("Oliver", 3);
map.put("Oliver", 5);

System.out.println(map);

Sonuç:

Bir anahtar/değer çifti eklediğimizde, eğer anahtar koleksiyonda zaten varsa eski değer yeni değerle değiştirilir. Bu davranış, örneğimizde aynı anahtara sahip iki çiftle gösterilmiştir — ("Oliver", 3) ve ("Oliver", 5) .

Oluşturduğumuz Comparator ile bir örneğe bakalım . Anahtar dizginin uzunluğuna göre sıralanmış öğeleri depolamak istediğimizi varsayalım. Tuşların uzunluğu eşitse, alfabetik olarak sıralayacağız (dizelerin doğal sıralaması):

class LengthComparator implements Comparator<String> {
  public int compare(String o1, String o2) {
    Integer lenghComparedResult = Integer.compare(o1.length(), o2.length());
    return lenghComparedResult != 0 ? lenghComparedResult : o1.compareTo(o2);
  }
}

SortedMap<String, Integer> lengthComparedMap = new TreeMap<String, Integer>(new LengthComparator());

lengthComparedMap.put("Jeff", 4);
lengthComparedMap.put("Oliver", 5);
lengthComparedMap.put("Roxy", 4);
lengthComaredMap.put("Jan", 4);

İşte ortaya çıkan sıra:

Bu davranış, bir TreeMap'i dizinleri sayılar yerine sözcükler ( String ) olan sıralanmış bir dizi veya liste gibi yapar .

TreeMap sınıfındaki SortedMap yöntemleri

1. İlk öğrencinin anahtarını almanız gerekiyorsa firstKey () yöntemini kullanabilirsiniz:

   
   String firstKey = map.firstKey();
   	System.out.println("First key → " + firstKey);
   

   Sonuç: Birinci anahtar → Anthony

2. Son öğrencinin anahtarını almanız gerekiyorsa, lastKey() yöntemini kullanabilirsiniz :

   
   String lastKey = map.lastKey();
   System.out.println("Last key → " + lastKey);
   

   Sonuç: Son Anahtar → Jeff

3. " Sara " tuşu ile nesneden sonra gelen tüm nesneleri alın :

   
   Map<String, Integer> tailMap = map.tailMap("Sara");
            	System.out.println("tailMap: " + tailMap);
   

   Sonuç: tailMap: {Sara=5, Jeff=4}

4. " Nick " tuşu ile nesneden önce gelen tüm nesneleri alın :

   
   System.out.println("headMap: " + headMap);
    Map<String, Integer> headMap = map.headMap("Nick");
   

   Sonuç: HeadMap: {Anthony=5}

5. " Oliver " tuşuyla nesneden sonra gelen ve " Sara " tuşuyla nesneden önce gelen tüm nesneleri alın :

   
   Map<String, Integer> subMap = map.subMap("Oliver", "Sara");	
   System.out.println("subMap: " + subMap);
   

   Sonuç: alt Harita: {Oliver=5, Roxy=5}

HashMap ve SortedMap/TreeMap'in Karşılaştırılması

Öğelerin nasıl sıralanıp saklandığından bahsedelim:

• HashMap iterasyon yaparken bize sıralama konusunda herhangi bir garanti vermediği için yeni elemanlar eklendiğinde sıralama tamamen değişebilir.

• TreeMap'te sıralama , CompareTo() yöntemine (veya sağladığımız bir Karşılaştırıcıya ) göre anahtarların "doğal sıralamasına" dayalıdır . Ayrıca, TreeMap'in bu sıralama düzenine bağlı yöntemleri içeren SortedMap arabirimini uyguladığını da unutmayın .

Şimdi performans ve hız değerlendirmesine dönüyoruz:

• HashMap , hashing anahtarlarına dayalı bir haritadır. O(1)eleman ekleyebilir ve alabilir. Bunu desteklemek için, anahtarlarhashCode()veequals().

• TreeMap , ağaç tabanlı bir haritadır. Ekleme ve getirme işlemleri,haritadaki öğelerin sayısına bağlı olarakO(log n)Bu, elemanların anahtarımız veya harici bir Karşılaştırıcı tarafından sağlanan bir tür karşılaştırma mekanizmasına sahip olması için gereklidir. Bu mekanizma yineleme sırasını belirler.

Ve bu faktörler, hangi koleksiyonları ne zaman kullanacağımıza karar vermemize yardımcı olur.

Değerleri belirli bir sırada saklamamız gerekirse, seçim açıktır — bir SortedMap'e ihtiyacımız var . HashMap'ten biraz daha yavaş olmasına rağmen bizim için önemli görevleri yerine getiriyor.

Daha önce bahsedildiği gibi, SortedMap, değerin ne zaman eklendiğine bakılmaksızın bize haritamızdaki ilk (veya son) anahtarı veya değeri veya anahtar-değer çiftini verebilir. HashMap uygulaması bunu yapamaz .

Örneğin, anahtarları (öğrencilerin adları) ve değerleri (notları) içeren bir harita düşünün. Diyelim ki ters alfabetik sıradaki bir listeyle çalışmak istiyoruz.

1.

SortedMap<String, Integer> sorted = new TreeMap<String,Integer>(Comparator.reverseOrder());
sorted.put("Anthony", 5);
sorted.put("Sara", 5);
sorted.put("Jeff", 4);

String firstKeyFromSortedMapVariant = sorted.firstKey();

Integer markFromSortedMap = sorted.get(firstKeyFromSortedMapVariant);
System.out.println(firstKeyFromSortedMapVariant + " - " + markFromSortedMap);

2.

HashMap<String, Integer> hash = new HashMap<String,Integer>();
hash.put("Anthony", 5);
hash.put("Sara", 5);
hash.put("Jeff", 4);

SortedSet<String> keySetOfHashMap = new TreeSet<String>(Comparator.reverseOrder());
// Or sort manually, storing elements in an array or list (preserving the insertion order)
keySetOfHashMap.addAll(hash.keySet());
String firstKeyFromHashMapVariant = keySetOfHashMap.first();


Integer markFromHashMap = hash.get(firstKeyFromHashMapVariant);
System.out.println(firstKeyFromHashMapVariant + " - " + markFromHashMap);

Örnek, bir HashMap kullanmanın görevi daha karmaşık hale getirdiğini gösteriyor, çünkü HashMap ne depolama sırasını ne de haritadan öğe alma sırasını garanti ediyor.