Bölüm 5: Koleksiyonlar

5.1Koleksiyon Çerçevesi

Dizi, aynı tipten değerleri art arda tutan en temel yapıdır. Hızlıdır ve indisle her öğeye anında ulaşır. Ama iki büyük eksiği vardır. Birincisi boyutudur: new int[3] ile oluşturulan dizi ömrü boyunca üç öğe tutar. İkincisi hazır işlem eksikliğidir: bir öğenin dizide olup olmadığını sormak, ortadan bir öğe silmek ya da diziyi sıralamak için her seferinde döngü yazmak gerekir. Bu kesim, bu iki eksiği kapatan kütüphaneyi ve onun temel fikirlerini tanıtır.

5.1.1Neden koleksiyonlar?

Koleksiyonun diziden ilk farkı boyutun dinamik olmasıdır. Öğe eklendikçe koleksiyon büyür, öğe silindikçe küçülür. İkinci fark hazır metotlardır: add ekler, remove siler, contains bir öğenin var olup olmadığını söyler, size öğe sayısını verir. Bu metotlar yıllardır milyonlarca programda kullanılmış ve sınanmıştır. Aynı işi elle yazan bir programcının hata yapma olasılığı, kütüphaneyi kullananınkinden çok daha yüksektir.

Farkı somut görmek için dört sayı saklamayı deneyelim. Dizi üç hücreyle oluşturulmuşsa dördüncü değer sığmaz:

int[] dizi = new int[3];      // boyut sabit: 3
dizi[0] = 10;
dizi[1] = 20;
dizi[2] = 30;
// dizi[3] = 40;  → ArrayIndexOutOfBoundsException

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 3 out of bounds for length 3

Yorum satırı olarak gösterilen dizi[3] = 40; çalıştırıldığında Java ArrayIndexOutOfBoundsException fırlatır. İleti sorunu açıkça söyler: uzunluğu 3 olan dizide 3 numaralı indis yoktur. Geçerli indisler 0, 1 ve 2'dir. Aynı dört değer bir listeye ise sorunsuz girer:

List<Integer> liste = new ArrayList<>();
liste.add(10);
liste.add(20);
liste.add(30);
liste.add(40);       // sorun yok: büyür
System.out.println(liste);
System.out.println("boyut: " + liste.size());

[10, 20, 30, 40]
boyut: 4

Burada List<Integer> değişkenin tipidir: “tam sayılardan oluşan bir liste”. new ArrayList<>() ise gerçek nesneyi oluşturur. Başlangıçta liste boştur ve her add çağrısı değeri sona ekler. println listeyi köşeli parantez içinde, öğeleri virgülle ayırarak yazar; bu biçimi listenin kendi toString metodu üretir. size() o anda listede kaç öğe bulunduğunu verir.

Sunumdaki benzetme bu farkı iyi anlatır. Dizi, koltuk sayısı sabit bir otobüse benzer: koltuklar dolunca yeni yolcu binemez. ArrayList ise yolcu arttıkça büyüyen bir otobüstür. Büyümenin nasıl olduğu, yani otobüsün içeride nasıl genişlediği, listeler kesiminde ayrıntılı izlenir.

5.1.2Dört temel tür

Çerçevedeki onlarca sınıf dört temel türde toplanır. Şekil 5.1 her türü küçük bir örnekle gösterir.

• Liste (list): öğeler belirli bir sırayla tutulur ve her birinin bir indisi vardır. Aynı öğe birden çok kez bulunabilir. Örnekler ArrayList ve LinkedList'tir.
• Küme (set): yalnızca tekil öğeler bulunur. Var olan bir öğe ikinci kez eklenmez. Örnekler HashSet ve TreeSet'tir.
• Eşleme (map): anahtar → değer çiftleri tutulur. Her anahtar bir kez bulunur, değerler tekrar edebilir. Örnekler HashMap ve TreeMap'tir.
• Kuyruk (queue): işlenmeyi bekleyen öğeler tutulur. Genellikle ilk giren ilk çıkar (First In, First Out, FIFO). Örnekler LinkedList ve PriorityQueue'dur.

Çerçeve bu türlerle birlikte bazı ortak hedefler gözetir. Temel işlemler (ekleme, çıkarma, güncelleme, arama) her türde benzer adlarla yapılır ve hepsinde for-each döngüsüyle gezinilebilir. API sade ve tutarlıdır; bir türü öğrenen öteki türleri kolayca kullanır. Her sınıf belirli bir veri hacmine ve erişim biçimine göre ayarlanmıştır. Jenerik tipler sayesinde yanlış tipteki öğe derleme zamanında yakalanır. Sıralama, arama ve karıştırma gibi algoritmalar hazırdır ve hatalı kullanım bir istisnayla bildirilir. Sonuçta daha az kod yazılır ve yazılan kod daha güvenilir olur.

5.1.3Arayüz ve sınıf hiyerarşisi

Çerçevenin iskeleti arayüzlerden oluşur. Arayüz, bir tipte hangi metotların bulunacağını söyler, ama bu metotların gövdesini yazmaz. Şekil 5.2 temel arayüzleri ve aralarındaki genişletme ilişkisini gösterir.

Hiyerarşinin en üstünde Iterable durur. Bu arayüzün tek zorunlu metodu iterator()'dır. Bir tip Iterable ise for-each döngüsüyle gezilebilir. Collection, bütün koleksiyonların ortak metotlarını toplar: add, remove, size, contains ve ötekiler. List, Queue ve Set bu ortak metotları devralır ve kendi metotlarını ekler. Örneğin indisle erişim (get(i)) yalnız List'te vardır.

Map ise ayrı bir daldır. Bir eşlemenin öğesi tek bir değer değil, anahtar-değer çiftidir. add(e) gibi tek öğe alan bir metot eşlemeye uymaz; eşlemede ekleme put(anahtar, değer) ile yapılır. Bu yüzden Map Collection'dan türemez ve Iterable da değildir. Bunun önemli bir sonucu vardır: bir eşleme doğrudan for-each döngüsüne verilemez. Eşlemenin anahtarları, değerleri ya da çiftleri ayrı görünümler olarak alınıp onlar gezilir.

Arayüzlerin altında onları uygulayan sınıflar bulunur. Şekil 5.3 en sık kullanılan sınıfları ve hangi arayüzü uyguladıklarını toplu olarak verir.

Şekilde dikkat çeken nokta, bir sınıfın birden çok arayüzü uygulayabilmesidir. LinkedList hem bir listedir (indisle erişim) hem de çift uçlu bir kuyruktur (baştan ve sondan ekleme, çıkarma). Aynı nesne, hangi arayüz tipindeki değişkenle kullanılırsa o arayüzün metotlarını sunar. Arayüz tipinden nesne ise oluşturulamaz: new List<>() yazılırsa derleyici durur.

ListNew.java:4: error: List is abstract; cannot be instantiated
        List<Integer> a = new List<>();
                          ^
1 error

İleti, List'in soyut (abstract) olduğunu söyler. Soyut bir tipin metot gövdeleri yoktur; nesneyi her zaman somut bir sınıf (ArrayList, LinkedList) verir.

5.1.4Çerçevenin üç unsuru

Koleksiyon Çerçevesi üç unsurdan oluşur ve her birinin ayrı bir görevi vardır.

Arayüz (interface)

Bir veri yapısının nasıl davranması gerektiğini tanımlar, yani ne yapılacağını söyler. List sıralı bir listeyi temsil eder: öğeler bir sıradadır, indisle erişilir, tekrar olabilir.

Gerçekleme (implementation)

Arayüzü uygulayan somut sınıftır, yani işin nasıl yapıldığını belirler. ArrayList, List arayüzünü dinamik bir diziyle uygular; LinkedList aynı arayüzü bağlı düğümlerle uygular.

Algoritma (algorithm)

Sıralama, arama, karıştırma gibi işleri yapan hazır metotlardır. Çoğu Collections sınıfında static metot olarak bulunur. Collections.sort() bir listeyi sıralar.

Üç unsur kısa bir kodda bir arada görülür:

List<String> liste = new ArrayList<>();  // arayüz ← sınıf
liste.add("Mavi");
liste.add("Kırmızı");
Collections.sort(liste);                  // algoritma
System.out.println(liste);

[Kırmızı, Mavi]

İlk satırda solda arayüz (List<String>), sağda gerçekleme (ArrayList) vardır. Collections.sort algoritmadır ve listeyi doğal sırasına, yani dizgiler için alfabetik sıraya dizer. “Kırmızı” K ile, “Mavi” M ile başladığı için K önce gelir. Algoritma listenin hangi sınıftan olduğunu bilmek zorunda değildir; List arayüzünün sunduğu metotlarla çalışır. Aynı sort çağrısı bir LinkedList üzerinde de çalışır.

Bu düzen modüler bir tasarımdır. Her bileşenin belirli bir rolü ve sorumluluğu vardır. Farklı gerçeklemeler ve algoritmalar aynı arayüz üzerinden birlikte kullanılabilir. Yeni bir liste sınıfı yazan biri, List arayüzünü uyguladığı anda bütün hazır algoritmalardan yararlanır.

5.1.5Arayüze göre programlama

Arayüz bir davranışı tanımlar; sınıflar bu davranışı kendi metotlarıyla uygular. Her sınıf farklı bir depolama biçimi kullanır: ArrayList dinamik dizi, LinkedList çift yönlü bağlı liste, HashMap anahtar-değer tablosu. Her biri belirli bir veri yapısının gereksinimlerini karşılar. Programcı için iyi alışkanlık, değişkeni ve parametreyi arayüz tipinde tanımlamaktır.

public class ListeYazdir {
    // Parametre türü arayüz: her List ile çalışır
    static void yazdir(List<String> liste) {
        for (String s : liste) {
            System.out.print(s + " ");
        }
        System.out.println("(" + liste.size() + " öğe)");
    }

    public static void main(String[] args) {
        List<String> a = new ArrayList<>();
        a.add("Elma");
        a.add("Armut");
        List<String> b = new LinkedList<>(a);  // aynı öğeler
        b.add("Kiraz");
        yazdir(a);
        yazdir(b);
    }
}

Elma Armut (2 öğe)
Elma Armut Kiraz (3 öğe)

yazdir metodunun parametresi List<String> tipindedir. Metot, kendisine verilen listenin ArrayList mi, LinkedList mi olduğunu bilmez ve bilmesi de gerekmez. İçerideki for-each döngüsü ve size() çağrısı her listede vardır. main'de a bir ArrayList, b ise bir LinkedList'tir. new LinkedList<>(a) yazımı, a'nın öğeleriyle doldurulmuş yeni bir liste oluşturur; bu yüzden b önce Elma ve Armut'u içerir, sonra Kiraz eklenir. İki çağrı aynı metoda gider ve iki farklı sınıfın nesnesini aynı biçimde yazar.

Bu yaklaşımın asıl kazancı değişiklik anında görülür. Bir gün listenin başına çok sık ekleme yapıldığı ve ArrayList'in yavaş kaldığı anlaşılırsa, yalnız new satırı değiştirilir. Değişkenin tipi zaten List olduğu için kodun geri kalanı aynı kalır. Değişken ArrayList tipinde tanımlanmış olsaydı, o tipi kullanan her metot imzasının da değişmesi gerekirdi. Joshua Bloch'un Effective Java kitabı bu ilkeyi “nesnelere arayüzleriyle başvurun” diye özetler.

5.1.6Jenerik tipler ve tip güvenliği

List<String> isimler = new ArrayList<>();
isimler.add("Ali");
// isimler.add(42);           // derleme hatası
String ilk = isimler.get(0);  // tür dönüşümü gerekmez

List<Integer> notlar = new ArrayList<>();  // List<int> olmaz
notlar.add(85);               // kutulama: int → Integer
int n = notlar.get(0);        // kutudan çıkarma → int
System.out.println(ilk + " " + n);

Ali 85

Köşeli ayraçlar (<>) içine öğe tipi yazılır. isimler yalnız String kabul eder. Yorum satırındaki isimler.add(42) açılırsa program derlenmez:

YanlisTip.java:5: error: incompatible types: int cannot be converted to String
        isimler.add(42);
                    ^
Note: Some messages have been simplified; recompile with -Xdiags:verbose to get full output
1 error

Hata çalışma anına kalmaz; program hiç çalışmadan önce yakalanır. İkinci kazanç get tarafındadır. isimler.get(0)'ın sonucu doğrudan String'dir; tip dönüşümü (cast) yazmak gerekmez.

Jenerikler Java 5 ile gelmiştir. Önceki “ham” (raw) kullanımda koleksiyon her öğeyi Object olarak tutar ve yanlış tip ancak çalışma anında, okunan öğe dönüştürülürken ClassCastException olarak ortaya çıkar. Jenerik tip aynı yanlışı derleme anında yakalar.

Sağ taraftaki boş <> işaretine elmas (diamond) işleci denir ve Java 7'den beri kullanılır. Derleyici tipi soldaki bildirimden çıkarır: List<String> isimler = new ArrayList<>(); ile new ArrayList<String>() aynı anlamdadır. Elmas yalnız new tarafında yazılır; ArrayList<> a = … derlenmez.

Koleksiyonlar yalnızca nesne tutar

Tip parametresi bir referans tipi olmalıdır; int, double gibi ilkel tipler buraya yazılamaz. List<int> denemesinin iletisi şudur:

IlkelTip.java:4: error: unexpected type
        List<int> notlar = new ArrayList<>();
             ^
  required: reference
  found:    int
1 error

İleti “referans tipi bekleniyordu, int bulundu” der. İlkel tipler için her birine karşılık gelen bir sarmalayıcı sınıf (wrapper class) kullanılır. Tablo 5.1 en sık kullanılanları verir.

İlkel değer ile sarmalayıcı nesne arasındaki dönüşüm kendiliğinden olur. notlar.add(85) satırında 85 bir int'tir, ama liste Integer bekler. Derleyici bu çağrıyı notlar.add(Integer.valueOf(85))'e çevirir; buna otomatik kutulama (autoboxing) denir. int n = notlar.get(0) satırında ters yönde bir dönüşüm olur: Integer nesnesinin içindeki değer intValue() ile alınır. Buna kutudan çıkarma (unboxing) denir.

Kutudan çıkarmanın bir tuzağı vardır. Sarmalayıcı referans null ise içinden çıkarılacak bir değer yoktur. Bir eşlemede bulunmayan anahtarın değeri null döner ve bu değer int'e atanınca program çöker:

import java.util.*;
public class BosKutu {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        int n = m.get("yok");
    }
}

Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Map.get(Object)" is null

İleti hatanın kaynağını tam gösterir: Map.get'in döndürdüğü değer null'dır, dolayısıyla intValue() çağrılamaz. Bu satırda gözle görülen bir metot çağrısı yoktur; intValue() çağrısını derleyici kendisi eklemiştir. Böyle hatalar bu yüzden ilk bakışta şaşırtır.

İlk örnekler: liste ve eşleme

İki temel yapıyı yan yana görmek için bir isim listesi ve bir telefon rehberi kuralım:

// İsim listesi (ArrayList)
List<String> isimListesi = new ArrayList<>();
isimListesi.add("Ahmet");
isimListesi.add("Ayşe");
System.out.println(isimListesi);

// Telefon rehberi (HashMap)
Map<String, String> telefonRehberi = new HashMap<>();
telefonRehberi.put("Ahmet", "555-1234");
telefonRehberi.put("Ayşe", "555-9876");
System.out.println(telefonRehberi.get("Ahmet"));

[Ahmet, Ayşe]
555-1234

ArrayList öğeleri eklenme sırasıyla tutar; add her seferinde sona ekler. HashMap ise bir anahtarı (isim) bir değere (numara) eşler. Eşlemeye put(anahtar, değer) ile ekleriz, get(anahtar) ile değeri buluruz. telefonRehberi.get("Ahmet") rehberi baştan sona taramaz; anahtardan hesaplanan bir konuma doğrudan gider. Bu hızın nasıl sağlandığı kümeler ve eşlemeler kesimlerinde açıklanır.

5.1.7Collection arayüzünün metotları

Collection arayüzü bütün listelerin, kümelerin ve kuyrukların ortak metotlarını tanımlar. Tablo 5.2 bu metotları, görevlerini ve dönüş tiplerini verir.

add'in boolean döndürmesi ilk bakışta gereksiz görünebilir. Bir listeye ekleme her zaman başarılı olur ve add hep true döndürür. Ama kümede durum farklıdır: öğe zaten varsa eklenmez ve add false döndürür. Ortak arayüz her iki durumu da karşılayacak biçimde tasarlanmıştır. remove ve contains parametresini Object olarak alır; öğelerin eşitliğini equals metoduyla sınar.

Aşağıdaki örnekte değişkenin tipi bilinçli olarak Collection seçilmiştir:

Collection<String> renkler = new ArrayList<>();
renkler.add("kırmızı");
renkler.add("yeşil");
renkler.add("mavi");
System.out.println(renkler.size());
System.out.println(renkler.contains("yeşil"));
renkler.remove("yeşil");
System.out.println(renkler);
Collection<String> aranan = Arrays.asList("mavi", "kırmızı");
System.out.println(renkler.containsAll(aranan));
Object[] dizi = renkler.toArray();
System.out.println(dizi.length);
renkler.clear();
System.out.println(renkler.isEmpty());

3
true
[kırmızı, mavi]
true
2
true

Program satır satır şöyle ilerler. Üç renk eklenince size() 3 olur. contains("yeşil") true döndürür. remove("yeşil") öğeyi değerine göre bulur ve siler; liste [kırmızı, mavi] olur. Arrays.asList("mavi", "kırmızı") iki öğeli bir liste oluşturur. containsAll bu listenin her öğesinin renkler'de bulunup bulunmadığını sorar; sıranın önemi yoktur ve sonuç true'dur. toArray() öğeleri yeni bir diziye kopyalar; dizinin uzunluğu 2'dir. Bu dizi koleksiyondan bağımsızdır: dizide yapılan değişiklik koleksiyonu etkilemez. Son olarak clear() her şeyi siler ve isEmpty() true döner.

Değişken Collection tipinde olduğu için yalnızca ortak metotlar kullanılabilir. Nesne gerçekte bir ArrayList olsa da renkler.get(0) derlenmez:

CollGet.java:6: error: cannot find symbol
        String s = renkler.get(0);
                          ^
  symbol:   method get(int)
  location: variable renkler of type Collection<String>
1 error

İleti, Collection<String> tipindeki değişkende get(int) adlı bir metot bulunmadığını söyler. Bu durum arayüze göre programlama kuralının öteki yüzüdür: değişkenin tipi, hangi metotların çağrılabileceğini belirler. Bu metotların hepsi bütün List, Set ve Queue nesnelerinde vardır.

5.2Listeler

Liste, koleksiyonların en çok kullanılanıdır. Programcıların büyük kısmı diziden sonra ilk olarak ArrayList'i öğrenir ve çoğu iş için ondan başka bir şeye ihtiyaç duymaz. Bu kesim önce List arayüzünün sözleşmesini verir. Ardından iki temel gerçeklemeyi, ArrayList ve LinkedList'i iç yapılarıyla birlikte inceler. Kesimin sonunda Java'nın ilk sürümlerinden kalan Vector ve Stack ile listede gezinmenin üç yolu yer alır.

5.2.1List arayüzü

Tanımdaki “sıra” sözcüğü iki farklı anlama gelebilir ve bu ikisi sık karıştırılır. Listedeki öğeler sıralıdır (ordered): her öğenin belirli bir konumu vardır ve öğeler o konumda kalır. Ama liste kendiliğinden sıralanmış (sorted) değildir. 30, 10, 20 sırasıyla eklenen sayılar listede yine 30, 10, 20 olarak durur. Küçükten büyüğe dizmek için ayrıca sıralama algoritması çağrılır.

List arayüzü Collection'dan gelen metotlara indisle çalışan metotlar ekler. Tablo 5.3 en sık kullanılanları verir.

Arayüzün üç bilinen gerçeklemesi vardır. ArrayList dinamik bir dizi kullanır ve indisle erişimde çok hızlıdır. LinkedList çift yönlü bağlı liste kullanır; listenin uçlarında ekleme ve çıkarma hızlıdır. Vector ise eski ve senkronize bir sürümdür; yeni kodda yerine ArrayList tercih edilir.

5.2.2ArrayList ve iç dizisi

ArrayList<String> meyveler = new ArrayList<>();
meyveler.add("Elma");
meyveler.add("Armut");
System.out.println(meyveler.get(1));  // indeksle

Armut

Bu örnekte değişken bilerek ArrayList tipinde tanımlanmıştır; sunum iki yazımı da gösterir. meyveler.get(1), indis 1'deki öğeyi, yani eklenen ikinci meyveyi verir. İndisler 0'dan başladığı için “Elma” 0'da, “Armut” 1'dedir.

ArrayList'in hızı iç dizisinden gelir. get(i) çağrısı, dizinin i numaralı hücresine doğrudan gider. Dizideki her hücre aynı boyuttadır ve bellekte art arda durur. Bu yüzden i numaralı hücrenin adresi tek bir çarpma ve toplamayla bulunur. Liste on öğeli de olsa on milyon öğeli de olsa bu iş aynı sürer. set(i, e) de aynı nedenle hızlıdır.

Maliyetleri anlatırken büyük O gösterimi kullanılır. O(1), sürenin öğe sayısından bağımsız, yani sabit olduğunu söyler. O(n), sürenin öğe sayısı n ile orantılı büyüdüğünü söyler: öğe sayısı iki katına çıkınca süre de yaklaşık iki katına çıkar. get ve set O(1)'dir. Sona ekleme ortalamada O(1)'dir. Ortaya ekleme ve ortadan çıkarma ise öğeleri kaydırdığı için O(n)'dir.

ArrayList nasıl büyür?

İç dizinin uzunluğuna kapasite (capacity) denir. Kapasite, listenin size() değeriyle aynı şey değildir. size() dolu hücre sayısıdır; kapasite ise toplam hücre sayısıdır. Liste sona eklemeyi boş hücre kaldığı sürece doğrudan yapar. Dizi dolunca daha büyük bir dizi ayrılır ve eski öğeler oraya kopyalanır. Şekil 5.4 bu süreci kapasitesi 4 olan bir liste üzerinde gösterir.

Yeni dizinin boyu eski kapasitenin yaklaşık 1,5 katıdır: 4 + 4/2 = 6. Bu kuralı kendimiz gözlemleyebiliriz. ArrayList'in iç dizisi elementData adlı özel bir alandadır. Normal programlar bu alana erişmez, ama ölçüm için yansıma (reflection) ile okunabilir. Aşağıdaki çıktı, notun ölçüm programının JDK 21'deki sonucudur:

size 3 kap 4
size 4 kap 4
size 5 kap 6
bos kap 0: 1->10 11->15 16->22 23->33 34->49 50->73 74->109
clear sonrası kap 109

İlk üç satır şekildeki adımlarla birebir aynıdır: kapasite 4 iken üç ve dört öğe sığar, beşinci öğede kapasite 6 olur. Dördüncü satır parametresiz new ArrayList<>()'in davranışını gösterir. Boş liste başlangıçta hiç hücre ayırmaz (kapasite 0). İlk add ile 10 hücrelik dizi ayrılır; sunumdaki “varsayılan kapasite 10” bu anlamdadır. Sonraki büyümeler 15, 22, 33, 49, 73 ve 109 hücreye çıkar. Her biri öncekinin 1,5 katıdır, küsurat atılır. Son satır önemli bir ayrıntıyı gösterir: clear() öğeleri siler ama iç diziyi küçültmez. Silme, kapasiteyi azaltmaz.

Amortize O(1)

Büyüme anında add çağrısı bütün öğeleri kopyalar; bu tek çağrı O(n) sürer. Buna rağmen sona eklemenin “ortalamada O(1)” olduğu söylenir. Bunun nedeni kopyalamanın seyrek olmasıdır. Kapasite her seferinde 1,5 katına çıktığı için iki büyüme arasındaki ekleme sayısı da giderek artar. Toplam kopyalama sayısını n eklemeye bölünce sabit bir sayı çıkar. Notun sayım programı bunu doğrudan hesaplar:

10 ekleme: 0 kopya, oran 0,00
100 ekleme: 202 kopya, oran 2,02
1000 ekleme: 2456 kopya, oran 2,46
1000000 ekleme: 2430972 kopya, oran 2,43

Bir milyon ekleme boyunca yaklaşık 2,4 milyon öğe kopyalanır. Ekleme başına ortalama 2,43 kopya düşer ve bu oran n büyüdükçe artmaz. Ekleme sayısı ne olursa olsun her ekleme ortalamada sabit miktarda iş yapar. Bu tür ortalamaya amortize (amortized) maliyet denir. Tek bir çağrı bazen pahalıdır, ama uzun bir dizi çağrıda pahalı adımların payı sabit kalır.

5.2.3ArrayList metotlarını izlemek

Liste metotlarının birlikte nasıl çalıştığını görmek için beş isimle bir liste kurup üzerinde değişiklikler yapalım:

ArrayList<String> isimler = new ArrayList<>();
isimler.add("Ali");
isimler.add("Banu");
isimler.add("Cem");
isimler.add("Deniz");
isimler.add("Ece");
System.out.println(isimler);
isimler.set(3, "Can");       // 3. indeksi değiştir
System.out.println(isimler);
isimler.remove(4);           // 4. indeksi sil
System.out.println(isimler);
isimler.add(2, "Fatma");     // 2. indekse ekle
System.out.println(isimler);
int indeks = isimler.indexOf("Banu");
System.out.println("indeks: " + indeks);
boolean varMi = isimler.contains("Ece");
System.out.println("Ece var mı: " + varMi);
System.out.println("boyut: " + isimler.size());

[Ali, Banu, Cem, Deniz, Ece]
[Ali, Banu, Cem, Can, Ece]
[Ali, Banu, Cem, Can]
[Ali, Banu, Fatma, Cem, Can]
indeks: 1
Ece var mı: false
boyut: 5

Tablo 5.4 her adımda listenin içeriğini ve yeni çıktıyı verir. Satır numaraları yukarıdaki kodun satırlarıdır.

İlk adımda boş bir liste oluşur; size() 0'dır. add("Ali") ilk öğeyi 0 numaralı indise koyar. Dört add daha, öğeleri 1, 2, 3 ve 4 numaralı indislere yerleştirir. Liste yazdırılınca öğeler eklenme sırasıyla görünür. Şekil 5.5 izlemenin üç önemli anını gösterir.

set(3, "Can") boyutu değiştirmez; yalnızca 3 numaralı hücrenin içeriği değişir. Metot eski değeri (“Deniz”) döndürür, ama bu örnekte dönüş değeri kullanılmamıştır. remove(4) son öğeyi siler. Son öğenin arkasında başka öğe olmadığı için hiçbir şey kaymaz ve işlem O(1) sürer. add(2, "Fatma") ise listenin ortasına ekler. Önce 2 ve 3 numaralı indislerdeki Cem ve Can birer hücre sağa taşınır, sonra boşalan 2 numaralı hücreye Fatma yazılır.

Son üç satır arama yapar. indexOf("Banu") listeyi baştan tarar ve ilk eşleşmenin indisini döndürür: 1. contains("Ece") de aynı taramayı yapar, ama Ece daha önce silindiği için sonuç false'tur. Son boyut 5'tir: 5 ekleme ve 1 araya ekleme yapılmış, 1 öğe silinmiştir. İki arama metodu da en kötü durumda bütün listeyi dolaştığı için O(n)'dir. Bir listede sık sık “var mı?” sorusu soruluyorsa kümeye geçmek doğru seçimdir.

5.2.4Ortaya ekleme ve silme

Kaydırmanın maliyetini daha yakından görmek için dört sayılık bir listeye araya bir öğe ekleyip baştan bir öğe silelim:

List<Integer> liste2 = new ArrayList<>(Arrays.asList(10, 20, 30, 40));
liste2.add(1, 15);      // araya ekle: 20, 30, 40 sağa kayar
System.out.println(liste2);
liste2.remove(0);       // baştan sil: hepsi sola kayar
System.out.println(liste2);

[10, 15, 20, 30, 40]
[15, 20, 30, 40]

new ArrayList<>(Arrays.asList(10, 20, 30, 40)) yazımı, verilen değerlerle doldurulmuş değiştirilebilir bir liste oluşturur. Bu kalıp kısa örneklerde sık kullanılır. Şekil 5.6 iki işlemi adım adım gösterir.

Sağa kaydırma sondan başlar. Önce 40, sonra 30, sonra 20 bir hücre sağa taşınır. Baştan başlansaydı 20, 30'un üzerine yazılır ve 30 kaybolurdu. Dört öğeli listede add(1, 15) üç öğe taşır. Genel olarak i konumuna ekleme n − i öğe taşır. En kötü durum başa eklemedir; bütün n öğe yer değiştirir. Silmede de durum aynıdır: remove(0) arkadaki bütün öğeleri birer sola çeker.

5.2.5LinkedList

LinkedList'te kapasite diye bir kavram yoktur. Her ekleme yeni bir düğüm oluşturur ve onu komşularına bağlar. Hiçbir öğe kaydırılmaz. Listenin uçlarında ekleme ve çıkarma bu yüzden O(1)'dir: first ve last referansları uçları hazır tutar ve yalnızca birkaç referans değişir.

Bedel indisle erişimde ödenir. Düğümler bellekte art arda durmaz; her biri heap'in herhangi bir yerinde olabilir. 3 numaralı öğeyi bulmak için baştan başlayıp next bağlarını tek tek izlemek gerekir. get(i) bu yüzden O(n)'dir. Java'nın gerçeklemesi küçük bir iyileştirme yapar: indis listenin ilk yarısındaysa baştan, ikinci yarısındaysa sondan yürür. Bu, yürüyüşü en fazla n/2 adıma indirir, ama büyüme hızı yine O(n)'dir.

Sunumdaki benzetme bu dengeyi iyi anlatır. Bağlı liste, el ele tutuşmuş bir sıra insana benzer. Araya biri girecekse yalnızca iki kişi el değiştirir. Ama 3. kişiyi bulmak için baştan saymak gerekir.

LinkedList<String> meyveler = new LinkedList<>();
meyveler.add("Elma");
meyveler.add("Armut");
meyveler.addFirst("Kiraz");   // başa ekle
meyveler.addLast("Muz");      // sona ekle
System.out.println(meyveler);
System.out.println(meyveler.getFirst());
System.out.println(meyveler.getLast());
meyveler.removeFirst();
System.out.println(meyveler);

[Kiraz, Elma, Armut, Muz]
Kiraz
Muz
[Elma, Armut, Muz]

Bu örnekteki addFirst, addLast, getFirst, getLast, removeFirst ve removeLast metotları Deque arayüzünden gelir. add, get ve remove(i) ise List'ten gelir. Değişken LinkedList tipinde tanımlandığı için her iki arayüzün metotları da kullanılabilir.

Düğümleri adım adım izlemek

Tablo 5.5 aynı programı satır satır izler. Düğümler sütunu, listenin first'ten başlayıp next bağlarıyla gezildiğinde verdiği sırayı gösterir.

Başlangıçta liste boştur: first ve last ikisi de null'dır. “Elma” için ilk düğüm oluşur; tek düğüm hem ilk hem son olduğu için iki referans da onu gösterir. “Armut” sona bağlanırken üç referans değişir. Elma'nın next'i Armut'u, Armut'un prev'i Elma'yı gösterir; last Armut'a geçer. Şekil 5.8 bu bağlama işini ve removeFirst'ün etkisini gösterir.

addFirst("Kiraz") çağrısında yeni düğümün next'i Elma'yı gösterir, Elma'nın prev'i Kiraz'ı gösterir ve first Kiraz'a geçer. Bir dizide başa ekleme bütün öğeleri kaydırırdı. Burada yalnızca üç referans değişti. addLast("Muz") aynı işi sonda yapar. println listeyi first'ten başlayıp next bağlarını izleyerek yazar.

getFirst() ve getLast() doğrudan first ve last'in gösterdiği düğümün değerini döndürür; ikisi de O(1)'dir. removeFirst() first'ü bir sonraki düğüme taşır ve o düğümün prev'ini null yapar. Kiraz düğümüne artık hiçbir referans kalmadığı için çöp toplayıcı onu sonra temizler.

Boş bir LinkedList'te peekFirst() null döndürür, getFirst() ise NoSuchElementException fırlatır.

5.2.6ArrayList mi, LinkedList mi?

İki sınıf aynı List arayüzünü uygular, ama işlemlerin maliyeti çok farklıdır. Tablo 5.6 temel işlemleri karşılaştırır.

Tablonun dördüncü satırı sık yanlış anlaşılır. “Bağlı listede ortaya ekleme O(1)'dir” denir, ama bu yalnızca doğru düğüm elde hazırsa geçerlidir. add(i, e) çağrısı önce i numaralı düğümü bulmak için yürür; bu yürüyüş O(n)'dir. Bağlama adımı ise O(1)'dir. Sonuçta ortaya ekleme iki yapıda da O(n)'dir. Aradaki fark, ArrayList'in öğeleri kaydırması, LinkedList'in ise düğümleri saymasıdır. Bellekte art arda duran bir diziyi kaydırmak, dağınık düğümlerde yürümekten çoğu zaman daha hızlıdır.

Farkın büyüklüğünü görmek için iki uç durumu ölçelim. Ölçüm programı her iki listenin başına 100 000 öğe ekler, sonra 100 000 kez get(i) çağırır:

başa ekleme ms: ArrayList 539, LinkedList 1 | get(i) ms: ArrayList 0, LinkedList 5161

Süreler makineye ve çalıştırmaya göre değişir; bu sayılar notun yazıldığı bilgisayardaki bir çalıştırmadan alınmıştır. Oranlar ise kararlıdır. Başa eklemede LinkedList yüzlerce kat hızlıdır, çünkü ArrayList her eklemede bütün öğeleri kaydırır ve toplam iş O(n²)'ye çıkar. İndisle okumada durum tersine döner: ArrayList bir milisaniyenin altında biter, LinkedList ise her get için düğüm düğüm yürüdüğü için saniyeler harcar.

Çoğu durumda doğru seçim ArrayList'tir. Programlar listeyi çoğunlukla sona ekleyerek doldurur ve indisle ya da for-each ile okur. Bu iki işte ArrayList en az LinkedList kadar hızlıdır ve daha az bellek kullanır. Ekleme ve çıkarma sık ve özellikle listenin uçlarında yapılıyorsa LinkedList düşünülebilir. Kuyruk ve yığın ihtiyacı için ise genellikle ArrayDeque daha iyi bir seçimdir.

5.2.7Vector ve Stack

Vector ve Stack Java 1.0'dan kalmadır; Koleksiyon Çerçevesi Java 1.2 ile geldiğinde bu iki sınıf List arayüzüne uyarlanmıştır. Eski kodlarda ve bazı ders kitaplarında hâlâ görülürler. Bu yüzden nasıl çalıştıklarını bilmek gerekir, ama yeni kodda yerlerine daha uygun sınıflar kullanılır.

Vector

Vector, List arayüzünü uygulayan genişletilebilir bir dinamik dizidir. Belirtilen kapasiteyle, belirtilmezse 10 hücreyle başlar. Dolunca kapasitesi iki katına çıkar; ArrayList'in 1,5 katı büyümesinden farkı budur. Asıl ayrım ise metotlarının senkronize (synchronized) olmasıdır. Her metot çağrılırken nesne kilitlenir. Böylece birden çok iş parçacığı aynı listeye aynı anda güvenle erişebilir. Ama kilit tek iş parçacıklı programlarda da her çağrıda alınıp bırakılır ve bu boş yere zaman harcatır.

Vector<Integer> v = new Vector<>();   // kapasite: 10
for (int i = 1; i <= 11; i++) {
    v.addElement(i * 10);
}
System.out.println(v.size() + " / " + v.capacity());
System.out.println(v.elementAt(0));
v.removeElement(110);    // değeri 110 olan öğe
System.out.println(v.size() + " / " + v.capacity());

11 / 20
10
10 / 20

10, 20, …, 110 değerleri eklenir. On birinci öğe geldiğinde 10 hücrelik dizi dolmuştur ve kapasite iki katına, 20'ye çıkar. elementAt(0) ilk öğeyi verir. removeElement(110) değeri 110 olan öğeyi siler; boyut 10'a iner, ama kapasite 20'de kalır. Silme kapasiteyi küçültmez. Tablo 5.7 Vector'a özgü eski adlı metotları verir. Bu metotların hepsinin List'te bir karşılığı vardır: addElement yerine add, elementAt yerine get.

Stack

Yığın günlük hayatta üst üste konmuş tabaklara benzer: tabak hep en üste konur ve en üstten alınır. Programlamada yığının pek çok kullanımı vardır. Metin düzenleyicideki geri alma (undo) son yapılan işi ilk geri alır. Bir ifadedeki parantezlerin dengeli olup olmadığı yığınla denetlenir. Derinlik öncelikli arama ziyaret edilecek düğümleri yığında tutar. Metot çağrıları da çağrı yığınında saklanır.

Java'nın Stack sınıfı Vector'dan türetilmiştir. Tablo 5.8 metotlarını, Şekil 5.9 temel işleyişini verir.

Stack<String> yigin = new Stack<>();
yigin.push("A");
yigin.push("B");
yigin.push("C");
System.out.println(yigin);
System.out.println(yigin.peek());
System.out.println(yigin.pop());
System.out.println(yigin.search("A"));
System.out.println(yigin.empty());

[A, B, C]
C
C
2
false

Tablo 5.9 programı adım adım izler. Yığın sütunu öğeleri alttan üste doğru verir.

Üç push'tan sonra A en altta, C en üsttedir. println yığını alttan üste yazar: [A, B, C]. Bu sıra ilk bakışta şaşırtabilir, çünkü “üst” sağ uçtadır. Stack bir Vector olduğu için öğeleri iç dizide eklenme sırasıyla tutar ve en üst, dizinin son hücresidir. peek() C'yi döndürür ama çıkarmaz. pop() C'yi çıkarır ve döndürür; son giren ilk çıkmıştır. search("A") konumu üstten 1'den başlayarak sayar: B 1, A 2'dir. Bu sayım indislerden farklıdır, 0'dan değil 1'den başlar. Son satırda yığında iki öğe vardır ve empty() false döndürür.

push, pop ve peek iç dizinin sonunda çalıştığı için üçü de O(1)'dir (push amortize). Boş bir yığında pop() ya da peek() çağrılırsa EmptyStackException fırlatılır:

Exception in thread "main" java.util.EmptyStackException

Modern kodda Stack yerine Deque arayüzünü uygulayan ArrayDeque (ya da LinkedList) önerilir. Stack'in iki sorunu vardır. Birincisi Vector'dan gelen gereksiz senkronizasyondur. İkincisi kalıtımın getirdiği fazla metotlardır. Stack bir Vector olduğu için add(0, x) ya da remove(1) gibi çağrılar da yapılabilir. Bunlar yığının “yalnızca üstten erişim” kuralını bozar.

5.2.8Listede gezinme

Bir listenin bütün öğelerini sırayla işlemek için üç yaygın yol vardır:

List<String> dersler = new ArrayList<>(
        Arrays.asList("Fizik", "Java", "Devre"));
// 1) İndeksli for
for (int i = 0; i < dersler.size(); i++) {
    System.out.print(dersler.get(i) + " ");
}
System.out.println();
// 2) Gelişmiş for (for-each)
for (String d : dersler) {
    System.out.print(d + " ");
}
System.out.println();
// 3) forEach + lambda (Java 8+)
dersler.forEach(d -> System.out.print(d + " "));
System.out.println();

Fizik Java Devre 
Fizik Java Devre 
Fizik Java Devre 

Birinci yol indisli for döngüsüdür. Döngü değişkeni i 0'dan size() − 1'e kadar gider ve her öğe get(i) ile alınır. Bu yol, indisin kendisine ihtiyaç olduğunda kullanılır; örneğin “3. sırada Java var” diye yazmak için. Yalnızca listelerde çalışır, çünkü kümelerde ve kuyruklarda get(i) yoktur.

İkinci yol gelişmiş for, yani for-each döngüsüdür. En okunur yazımdır ve Iterable olan her koleksiyonda çalışır. Derleyici bu döngüyü arka planda bir yineleyiciye çevirir. Yineleyici kesiminde bu dönüşüm ayrıntılı izlenir.

Üçüncü yol forEach metodu ve bir lambda ifadesidir (Java 8+). d -> System.out.print(d + " ") ifadesi “her d öğesi için şunu yap” anlamına gelir. Kısa bir yazımdır, ama döngü gövdesinden dışarıdaki yerel değişkenleri değiştiremez. Lambda içinden bir sayaç artırmak istenirse derleyici durur:

LambdaDis.java:6: error: local variables referenced from a lambda expression must be final or effectively final
        l.forEach(x -> toplam += x);
                       ^
1 error

Lambda, dışarıdaki yerel değişkenleri yalnızca okuyabilir; o değişkenler final ya da fiilen final (bir kez atanıp hiç değişmeyen) olmalıdır. Toplam gibi birikimli değerler için ya for-each kullanılır ya da akışların sum, reduce gibi işlemleri.

Üç yolun çıktısı aynıdır. Gezinirken listeden öğe silmek gerekiyorsa üçü de uygun değildir. Bu iş için yineleyicinin kendi remove metodu kullanılır.

5.3Kuyruklar

Bir kuyruk, işlenmeyi bekleyen öğeleri tutar. Yazıcıya gönderilen belgeler, bir sunucuya gelen istekler, bir oyunda sırası gelecek hamleler hep bir kuyrukta bekler. Kuyruğun asıl sorusu “sıradaki kim?” sorusudur. Bu sorunun yanıtı yapıya göre değişir: sıradan bir kuyrukta ilk gelen, öncelikli kuyrukta en acil olan, yığında ise en son gelen sıradadır. Bu kesim bu üç davranışı sırasıyla Queue, PriorityQueue ve Deque üzerinden anlatır.

5.3.1Queue arayüzü

Benzetme olarak market kasası düşünülebilir. Sıraya en sondan girilir, ödemeyi en öndeki yapar. Kimse sıranın ortasına giremez ve ortadan çıkamaz. Şekil 5.10 bu düzeni gösterir.

Queue arayüzünün üç bilinen gerçeklemesi vardır. LinkedList çift yönlü bağlı listeyle, ArrayDeque dinamik diziyle çalışır; ikisi de gerçek FIFO kuyruğudur. PriorityQueue ise öğeleri önceliğe göre çıkarır; bu yüzden FIFO değildir. Kuyruğun tipik kullanımları yazıcı kuyruğu, görev sırası ve genişlik öncelikli aramadır.

Her işlemin iki biçimi

Queue arayüzü her temel işlemi iki biçimde sunar. Bir biçim başarısızlıkta istisna fırlatır, öteki özel bir değer döndürür. Tablo 5.10 bu ikiliği verir.

Kuyruk boşken remove() ve element() NoSuchElementException fırlatır; poll() ve peek() ise null döndürür. Ekleme tarafında fark ancak kapasitesi sınırlı kuyruklarda ortaya çıkar. Dolu kuyrukta add istisna fırlatır, offer ise false döndürür. LinkedList ve ArrayDeque sınırsız büyüdüğü için bu ikisinde ekleme hep başarılı olur. Boş kuyruktaki davranış farkı aşağıda görülür:

import java.util.*;
public class BosKuyruk {
    public static void main(String[] args) {
        Queue<String> k = new LinkedList<>();
        System.out.println(k.poll() + " " + k.peek());
        try { k.element(); } catch (RuntimeException e) { System.out.println("element: " + e); }
        k.remove();
    }
}

null null
element: java.util.NoSuchElementException
Exception in thread "main" java.util.NoSuchElementException

Kuyruğu izlemek

Queue<String> kuyruk = new LinkedList<>();
kuyruk.offer("Ali");
kuyruk.offer("Banu");
kuyruk.offer("Cem");
System.out.println(kuyruk);
System.out.println(kuyruk.peek());
System.out.println(kuyruk.poll());
System.out.println(kuyruk.poll());
System.out.println(kuyruk.size());
System.out.println(kuyruk.poll());
System.out.println(kuyruk.poll());

[Ali, Banu, Cem]
Ali
Ali
Banu
1
Cem
null

Değişken Queue tipinde, nesne ise LinkedList'tir. Bu sayede yalnızca kuyruk metotları kullanılabilir; kuyruk.get(1) gibi kuyruk düzenini bozacak bir çağrı derlenmez. Tablo 5.11 her adımda kuyruğun içeriğini verir.

Üç offer Ali, Banu ve Cem'i sırayla sona ekler. peek() baştakini (Ali) döndürür, ama kuyruğu değiştirmez. İlk poll() Ali'yi çıkarır ve döndürür; ilk giren ilk çıkmıştır. İkinci poll() Banu'yu çıkarır. Bu noktada size() 1'dir. Üçüncü poll() Cem'i çıkarır ve kuyruk boşalır. Dördüncü poll() hata vermez, null döndürür. Kuyruğun başı ve sonu sabit zamanda bulunduğu için offer, poll ve peek O(1)'dir.

5.3.2PriorityQueue ve ikili yığın

Öncelikli kuyruğun tipik kullanımları görev çizelgeleme, acil servis sırası ve en kısa yol algoritmalarıdır. Acil serviste hastalar geliş sırasına göre değil, durumlarının ağırlığına göre çağrılır. İşletim sistemi de öncelikli işleri öne alır. Öğelerin karşılaştırılabilir olması gerekir. Ya öğe sınıfı Comparable arayüzünü uygular ya da kuyruğa bir Comparator verilir. Ters sıra, yani en büyüğün önce çıkması için de bir karşılaştırıcı verilir. Tablo 5.12 temel metotları listeler.

PriorityQueue içte bir ikili yığın (binary heap) kullanır. Bu “yığın” sözcüğü LIFO yığınıyla aynı adı taşır, ama başka bir yapıdır. İkili yığın, bir dizide saklanan tam bir ikili ağaçtır. Ağacın kuralı şudur: her ebeveyn çocuklarından küçük ya da onlara eşittir. Bu kural yalnızca ebeveyn ile çocuk arasındadır; kardeşler arasında bir sıra yoktur. Kuralın sonucu olarak en küçük öğe her zaman köktedir.

Ağaç bir dizide şöyle tutulur. Kök indis 0'dadır. İndis i'deki düğümün çocukları 2i + 1 ve 2i + 2'de, ebeveyni (i − 1) / 2'dedir. Böylece hiçbir referans tutmadan ağaçta aşağı ve yukarı gidilebilir. Şekil 5.11 dört öğeli bir yığını hem ağaç hem dizi olarak gösterir.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(30);
pq.add(10);
pq.add(40);
pq.add(20);
System.out.println(pq.peek());   // en küçük
System.out.println(pq);          // iç düzen (yığın)
while (!pq.isEmpty()) {
    System.out.print(pq.poll() + " ");
}
System.out.println();

10
[10, 20, 40, 30]
10 20 30 40 

Çıktının ikinci satırı sık sık şaşırtır. println(pq) öğeleri sıralı yazmaz; iç diziyi olduğu gibi yazar. İç dizi yalnızca “her ebeveyn çocuklarından küçük” kuralına uyar: 10 kendi çocukları 20 ve 40'tan, 20 de kendi çocuğu 30'dan küçüktür. Ama 40 ile 30 arasında bir sıra yoktur. Sıralı sonuç için öğeler poll ile tek tek çıkarılır; çıkış sırası her zaman küçükten büyüğedir.

Yığın kuralını adım adım izlemek

Her ekleme ve çıkarmanın içeride ne yaptığını Tablo 5.13 gösterir. İç dizi sütunu her adımdan sonraki diziyi verir; değerler aynı programın her adımda iç diziyi yazdıran bir sürümüyle doğrulanmıştır.

Ekleme her zaman dizinin sonuna yapılır, sonra yeni öğe gerektiği kadar yukarı çıkar. 30 boş diziye girer ve kök olur. 10 indis 1'e eklenir. Ebeveyni indis 0'daki 30'dur ve 10 ondan küçüktür; kural bozulduğu için ikisi yer değiştirir. Kök artık 10'dur. 40 indis 2'ye girer; ebeveyni 10'dan büyük olduğu için yerinde kalır. 20 indis 3'e girer. Ebeveyni indis 1'deki 30'dur. 20 daha küçük olduğu için yer değiştirirler. 20 şimdi indis 1'dedir; ebeveyni 10'dan büyük olduğu için durur. Şekil 5.12 bu adımları ağaç üzerinde gösterir.

peek() yalnızca köke bakar ve O(1)'dir. Çıkarma ise şöyle yapılır. Kök çıkarılır, dizinin son öğesi köke taşınır ve gerektiği kadar aşağı iner. İlk poll()'da 10 çıkar, son öğe 30 köke gelir. 30'un çocukları 20 ve 40'tır; küçük olan 20 ile yer değiştirir. Dizi [20, 30, 40] olur. İkinci poll()'da 20 çıkar, 40 köke gelir ve küçük çocuğu 30 ile yer değiştirir: [30, 40]. Sonra 30 ve 40 sırayla çıkar ve kuyruk boşalır. Çıkış sırası 10 20 30 40'tır.

Yukarı çıkma ve aşağı inme yalnızca bir dalı izler. n öğeli tam ikili ağacın yüksekliği yaklaşık log₂ n'dir. Bu yüzden add ve poll O(log n)'dir. Bir milyon öğeli bir yığında bile her işlem en çok 20 kadar karşılaştırma yapar. remove(Object o) ise önce öğeyi bulmak için diziyi tarar ve O(n)'dir.

5.3.3Önceliği belirlemek

Sayılar ve dizgiler zaten karşılaştırılabilir; doğal sıraları bellidir. Kendi sınıflarımızın nesneleri ise ancak bir sıra tanımlanırsa öncelikli kuyruğa girebilir. Bunun birinci yolu sınıfın Comparable arayüzünü uygulamasıdır:

class Gorev implements Comparable<Gorev> {
    String ad;
    int oncelik;          // küçük = acil

    Gorev(String ad, int oncelik) {
        this.ad = ad;
        this.oncelik = oncelik;
    }

    @Override
    public int compareTo(Gorev diger) {
        return Integer.compare(oncelik, diger.oncelik);
    }

    @Override
    public String toString() {
        return ad + "(" + oncelik + ")";
    }
}

PriorityQueue<Gorev> gorevler =
        new PriorityQueue<>();
gorevler.add(new Gorev("Rapor", 3));
gorevler.add(new Gorev("Arıza", 1));
gorevler.add(new Gorev("Toplantı", 2));
while (!gorevler.isEmpty()) {
    System.out.println(gorevler.poll());
}

Arıza(1)
Toplantı(2)
Rapor(3)

Gorev sınıfı Comparable<Gorev>'u uygular ve tek bir metot yazar: compareTo. Bu metot iki görevi karşılaştırır. this önce gelecekse negatif, eşitse 0, sonra gelecekse pozitif bir sayı döndürür. Integer.compare(oncelik, diger.oncelik) tam olarak bunu yapar. Burada küçük öncelik numarası acil anlamına gelir. Arıza (1) en önce, Toplantı (2) sonra, Rapor (3) en son çıkar. Eklenme sırasının hiçbir önemi yoktur.

Doğal sıranın tersi gerekiyorsa sınıfı değiştirmeye gerek yoktur. Kuyruğun yapıcısına bir karşılaştırıcı verilir. Collections.reverseOrder() doğal sırayı tersine çeviren hazır bir karşılaştırıcıdır:

PriorityQueue<Integer> buyukOnce =
        new PriorityQueue<>(
        Collections.reverseOrder());
buyukOnce.add(30);
buyukOnce.add(10);
buyukOnce.add(40);
System.out.println(buyukOnce.poll());

40

Bu kuyrukta en büyük öğe köktedir ve önce çıkar. Karşılaştırıcılar algoritmalar kesiminde ayrıntılı işlenir.

Öğe sınıfı ne Comparable'ı uyguluyor ne de kuyruğa karşılaştırıcı verilmişse program derlenir, ama ikinci eklemede, ilk karşılaştırma anında ClassCastException fırlatılır.

5.3.4Deque ve ArrayDeque

Deque arayüzünün iki gerçeklemesi vardır: LinkedList (çift yönlü bağlı liste) ve ArrayDeque (dinamik dizi). Her iki uç için aynı üç işlem bulunur: ekle, çıkar ve bak. Tablo 5.14 bu metotları toplar. Queue'da olduğu gibi her işlemin istisna fırlatan ve özel değer döndüren iki biçimi vardır. remove… ve get… boş deque'de istisna fırlatır; poll… ve peek… null döndürür.

Deque ayrıca yığın ve kuyruk arayüzlerinin tanıdık adlarını da taşır. Yığın işlemleri baş uçta çalışır: push = addFirst, pop = removeFirst, peek = peekFirst. Kuyruk işlemlerinde offer sona ekler (offerLast), poll baştan alır (pollFirst). Bu eşleşmeler akılda tutulursa bir deque'in içeriği kolayca izlenir.

ArrayDeque

ArrayDeque, çift uçlu kuyruğu dairesel bir diziyle uygular. Dizi iki indis tutar: baş (head) ve son (tail). Başa ekleme baş indisini bir geri alır, sona ekleme son indisini bir ileri alır. İndis dizinin bir ucundan taşarsa öbür uca sarar. Böylece her iki uçta da öğe kaydırmadan O(1) ekleme ve çıkarma yapılır. Dizi dolunca daha büyük bir diziye kopyalanır, tıpkı ArrayList'teki gibi. Şekil 5.14 bu düzeni gösterir.

ArrayDeque çoğu durumda hem Stack'ten hem LinkedList'ten hızlı ve hafiftir. Stack gibi her çağrıda kilit almaz. LinkedList gibi her öğe için ayrı bir düğüm nesnesi oluşturmaz. Bu nedenle Java belgeleri yığın ve kuyruk ihtiyacı için ArrayDeque'i önerir. Tek kısıtı null öğe kabul etmemesidir. poll boş deque'de null döndürdüğü için null öğe bu dönüş değeriyle karışırdı; sınıf bu yüzden null'ı baştan reddeder:

import java.util.*;
public class NullDeque {
    public static void main(String[] args) {
        Deque<String> d = new ArrayDeque<>();
        d.offer(null);
    }
}

Exception in thread "main" java.lang.NullPointerException

Yığın olarak kullanmak için değişken Deque tipinde tanımlanır:

Deque<String> yigin = new ArrayDeque<>();
yigin.push("A");     // başa ekler
yigin.push("B");
System.out.println(yigin.pop());

B

A ve B başa itilir; B en üsttedir ve pop() onu döndürür. Stack alttan üste yazar; ArrayDeque ise baştan sona, yani üstten alta yazar: aynı A, B, C itmelerinden sonra biri [A, B, C], öteki [C, B, A] verir.

ArrayDeque'i izlemek

ArrayDeque<Integer> sayilar = new ArrayDeque<>();
sayilar.addFirst(5);
sayilar.addLast(10);
sayilar.addFirst(1);
System.out.println(sayilar);
int ilkSayi = sayilar.pollFirst();
int sonSayi = sayilar.pollLast();
System.out.println(ilkSayi + " " + sonSayi);
System.out.println(sayilar.peekFirst());

[1, 5, 10]
1 10
5

Tablo 5.15 programı adım adım izler.

addFirst(5) tek öğeyi ekler; 5 hem baştır hem son. addLast(10) 10'u sona ekler. addFirst(1) 1'i başa ekler; 5 ve 10 yerlerinde kalır, hiçbir öğe kaymaz. Deque baştan sona [1, 5, 10] olarak yazılır. pollFirst() baştaki 1'i çıkarır. Metot bir Integer döndürür; int ilkSayi'ye atanırken otomatik kutudan çıkarma yapılır. pollLast() sondaki 10'u çıkarır. İki değer yazılır: 1 10. Son olarak peekFirst() baştaki 5'i döndürür ama çıkarmaz.

Bu programın ince bir tuzağı vardır. pollFirst() boş deque'de null döndürür. Sonuç doğrudan bir int'e atanırsa kutudan çıkarma null üzerinde yapılır ve program çöker:

import java.util.*;
public class BosDeque {
    public static void main(String[] args) {
        ArrayDeque<Integer> d = new ArrayDeque<>();
        int x = d.pollFirst();
    }
}

Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.ArrayDeque.pollFirst()" is null

“Özel değer döndüren” biçimin güvenliği burada kaybolur. poll ailesi kullanılırken dönüş değeri önce Integer olarak alınıp null denetimi yapılır ya da çağrıdan önce isEmpty() sorulur.

5.4Kümeler

Bir öğrencinin aldığı derslerin kodları, bir metindeki farklı kelimeler, bir ağdaki ziyaret edilmiş düğümler: bunların ortak noktası tekrarın anlamsız olmasıdır. Aynı ders iki kez alınmaz, aynı kelime farklı kelime sayısını artırmaz. Küme bu tür veriler için tasarlanmıştır. Kümenin asıl gücü “bu öğe var mı?” sorusunu çok hızlı yanıtlamasıdır. Bu kesim kümenin sözleşmesini, hash tablosunun işleyişini, kendi sınıflarımızın kümede doğru davranması için gereken equals ve hashCode kurallarını ve sıralı kümeyi anlatır.

5.4.1Set arayüzü

Set arayüzü genel olarak bir sıra garantisi vermez; gezinme sırası gerçeklemeye bağlıdır. Üç gerçekleme üç farklı sıra sunar. HashSet sırasızdır. LinkedHashSet eklenme sırasını korur. TreeSet öğeleri sıralı tutar; sıra doğal sıra ya da verilen bir Comparator'dır. Set, Collection'a yeni metot eklemez; aynı metotları “tekrar yok” kuralıyla uygular.

Set<String> meyveler = new HashSet<>();
System.out.println(meyveler.add("Elma"));
System.out.println(meyveler.add("Armut"));
System.out.println(meyveler.add("Elma"));
System.out.println(meyveler.size());
System.out.println(meyveler.contains("Armut"));
meyveler.remove("Armut");
System.out.println(meyveler);

true
true
false
2
true
[Elma]

İlk iki add yeni öğe eklediği için true döndürür. Üçüncü add("Elma") var olan bir öğeyi eklemeye çalışır; küme değişmez ve sonuç false'tur. Bu yüzden size() 3 değil, 2'dir. contains("Armut") true döndürür. Armut silindikten sonra kümede yalnızca Elma kalır. add'in dönüş değeri pratikte de işe yarar: “bu kelimeyi daha önce gördük mü?” sorusu ayrı bir contains çağrısı yapmadan, tek bir add ile yanıtlanır.

5.4.2HashSet ve hash tablosu

HashSet tekil öğeleri sırasız saklar. AbstractSet'ten türetilmiştir ve Set arayüzünü uygular. İçeride aslında bir HashMap kullanır: kümenin öğeleri eşlemenin anahtarlarıdır. Bir öğeyi aramak için listedeki gibi baştan sona taramak gerekmez. Öğenin kovası hesaplanır ve yalnız o kovaya bakılır.

Kova numarası iki adımda bulunur. Önce öğenin hashCode() değeri alınır. Java, bu değerin üst 16 bitini alt 16 bitiyle karıştırır: h ^ (h >>> 16). Sonra sonucun son bitleri kova numarası olur. 16 kovalı bir tabloda son 4 bit kullanılır: (h ^ (h >>> 16)) & 15. Notun ölçüm programı dört meyvenin kovasını bu formülle hesaplar:

muz hashCode=108498 kova=3
elma hashCode=3116155 kova=4
kiraz hashCode=102057485 kova=8
armut hashCode=93086203 kova=7
Zeynep hashCode=-1621354421 kova=7
Ahmet hashCode=63235125 kova=1
Mert hashCode=2394618 kova=14
Elma hashCode=2162843 kova=10
Armut hashCode=63533531 kova=2

İlk dört satır sunumdaki kova numaralarını doğrular: muz 3, elma 4, kiraz 8, armut 7. Aynı formül eşlemeler kesimindeki rehber örneğinde de kullanılacaktır. Şekil 5.15 bu öğelerin tabloya yerleşmesini gösterir.

İkinci add("elma") çağrısı kümenin “tekrar yok” kuralının nasıl uygulandığını gösterir. Öğenin kovası hesaplanır: 4. O kovadaki öğelerle equals ile karşılaştırılır. Eşit bir öğe bulunduğu için ekleme yapılmaz. Bütün küme taranmaz; yalnızca tek bir kovaya bakılır.

Gezinme sırası kovaların sırasıdır. Tablo 0'dan 15'e taranır ve dolu kovalardaki öğeler sırayla verilir. Bu yüzden HashSet'in sırası eklenme sırasıyla ilgisizdir. Kova sayısı değişirse sıra da değişebilir. Bu sıraya hiçbir programda güvenilmemelidir.

İki farklı öğenin kova numarası aynı çıkabilir; buna çakışma (collision) denir. Örneğin yukarıdaki çıktıda armut ile Zeynep'in kovası 7'dir. Çakışan öğeler aynı kovada küçük bir zincir oluşturur ve arama o zincirde equals ile yapılır. Java 8'den beri, bir kovadaki zincir çok uzarsa (8 öğeden fazla ve tablo yeterince büyükse) zincir dengeli bir ağaca çevrilir. Tablodaki öğe sayısı kova sayısının %75'ini (yük faktörü 0,75) aşınca tablo iki katına büyür ve öğeler yeni kovalara dağıtılır. Böylece zincirler kısa kalır ve ortalama maliyet O(1) olur.

5.4.3LinkedHashSet ve üç kümenin sırası

LinkedHashSet, HashSet'ten türer ve öğeleri ek olarak bir bağlı listeyle birbirine bağlar. Hash tablosu hızlı erişimi ve tekilliği sağlar, bağlı liste ise eklenme sırasını korur. Hem hız hem sıra önemliyse LinkedHashSet seçilir. Sıra önemli değilse ve hız kritikse HashSet yeterlidir. Temel metotları aynıdır: add, remove, contains, size, clear.

LinkedHashSet<Integer> sayilar =
        new LinkedHashSet<>();
sayilar.add(5);
sayilar.add(10);
sayilar.add(5);         // tekrar: eklenmez
sayilar.add(1);
System.out.println(sayilar);

[5, 10, 1]

İkinci add(5) tekrar olduğu için eklenmez. Sonraki 1 listenin sonuna bağlanır. Çıktı eklenme sırasıdır: önce 5, sonra 10, sonra 1. Aynı kelimeleri üç kümeye birden ekleyince fark açıkça görülür:

String[] kelimeler = {"muz", "elma", "kiraz", "elma", "armut"};
Set<String> h = new HashSet<>();
Set<String> l = new LinkedHashSet<>();
Set<String> t = new TreeSet<>();
for (String k : kelimeler) {
    h.add(k);
    l.add(k);
    t.add(k);
}
System.out.println("HashSet:       " + h);
System.out.println("LinkedHashSet: " + l);
System.out.println("TreeSet:       " + t);

HashSet:       [muz, elma, armut, kiraz]
LinkedHashSet: [muz, elma, kiraz, armut]
TreeSet:       [armut, elma, kiraz, muz]

Beş kelimeden biri tekrardır (ikinci “elma”); üç kümede de dört öğe vardır. HashSet kovaların sırasını verir: muz 3, elma 4, armut 7, kiraz 8. LinkedHashSet eklenme sırasını korur. TreeSet alfabetik sıra verir. Tablo 5.16 üç sınıfı karşılaştırır.

5.4.4Kendi sınıflarımız: equals ve hashCode

Dizgi ve sayı kümeleri beklendiği gibi çalışır, çünkü String ve Integer sınıfları equals ve hashCode metotlarını değere göre yazmıştır. Kendi sınıflarımızda bu metotlar yazılmazsa Object'ten devralınan sürümler kullanılır. Object'in equals'ı iki referansın aynı nesneyi gösterip göstermediğine bakar. Alan değerleri aynı olan iki ayrı nesne bu yüzden “farklı” sayılır.

class Nokta {
    int x, y;
    Nokta(int x, int y) {
        this.x = x;
        this.y = y;
    }
    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Nokta)) return false;
        Nokta n = (Nokta) o;
        return x == n.x && y == n.y;
    }
    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

Set<NoktaA> s1 = new HashSet<>();
s1.add(new NoktaA(1, 2));
s1.add(new NoktaA(1, 2));
System.out.println(s1.size());

Set<Nokta> s2 = new HashSet<>();
s2.add(new Nokta(1, 2));
s2.add(new Nokta(1, 2));
System.out.println(s2.size());

2
1

NoktaA aynı iki alanlı sınıftır, ama equals ve hashCode yazılmamıştır. new NoktaA(1, 2) iki kez çalışınca bellekte iki ayrı nesne oluşur. Object'in equals'ı bunları farklı sayar ve küme boyutu 2 olur. Nokta sınıfında ise iki metot da geçersiz kılınmıştır. equals alanları karşılaştırır. hashCode, Objects.hash(x, y) ile aynı alanlardan bir sayı üretir. Aynı nokta kümeye bir kez girer ve boyut 1 olur.

Kuralın gerekçesi hash tablosunun çalışma biçimindedir. Önce kova hashCode ile bulunur, sonra o kovadaki öğeler equals ile karşılaştırılır. Eşit iki nesnenin hash kodları farklıysa farklı kovalara giderler. equals hiç çağrılmaz ve ikisi de kümeye girer. Yalnızca equals'ı yazıp hashCode'u unutan bir sınıf tam olarak bu hatayı yapar:

// yalnız equals yazılmış, hashCode unutulmuş
class NoktaE {
    int x, y;
    NoktaE(int x, int y) { this.x = x; this.y = y; }
    @Override
    public boolean equals(Object o) {
        if (!(o instanceof NoktaE)) return false;
        NoktaE n = (NoktaE) o;
        return x == n.x && y == n.y;
    }
}

import java.util.*;
public class YalnizEquals {
    public static void main(String[] args) {
        NoktaE a = new NoktaE(1, 2), b = new NoktaE(1, 2);
        Set<NoktaE> s = new HashSet<>();
        s.add(a);
        s.add(b);
        System.out.println(a.equals(b) + " " + s.size() + " " + s.contains(new NoktaE(1, 2)));
        List<NoktaE> l = new ArrayList<>();
        l.add(a);
        System.out.println(l.contains(new NoktaE(1, 2)));
    }
}

true 2 false
true

İlk satır çelişkiyi gösterir: a.equals(b) true'dur, ama küme iki öğe tutar. Yeni bir NoktaE(1, 2) ile yapılan contains da false döner, çünkü yeni nesnenin hash kodu (dolayısıyla kovası) başkadır. İkinci satırda aynı nesne bir listede aranır ve bulunur. ArrayList.contains yalnızca equals kullanır; hash koduna bakmaz. Aynı sınıf listede doğru, kümede yanlış çalışır. Derleyici bu durumu fark eder ve -Xlint seçeneğiyle derlenince uyarı verir: Class NoktaE overrides equals, but neither it nor any superclass overrides hashCode method.

Objects.hash(x, y)'nin ürettiği sayı basit bir formüldür: 31 · (31 · 1 + x) + y. (1, 2) noktası için 31 · 32 + 2 = 994 çıkar. Bu sayı bir sonraki örnekte kullanılacaktır.

5.4.5Kümedeki nesneyi değiştirmek

equals ve hashCode doğru yazılmış olsa da bir tuzak daha vardır. Kümeye girmiş bir nesnenin, hash kodunu belirleyen alanı sonradan değiştirilirse ne olur? Aşağıdaki program bunu dener:

Set<Nokta> kume = new HashSet<>();
Nokta p = new Nokta(1, 2);
kume.add(p);
System.out.println(kume.contains(p));
p.x = 5;              // alan değişti
System.out.println(kume.contains(p));
System.out.println(kume.contains(new Nokta(1, 2)));
kume.add(p);
System.out.println(kume.size());

true
false
false
2

Tablo 5.17 programı adım adım izler. Değişkenler sütununda hash, p'nin o anki hash kodu, kova ise bu koddan hesaplanan kova numarasıdır.

Başlangıçta Objects.hash(1, 2) 994'tür. 994'ün ikili gösterimi 1111100010'dur ve son 4 biti 0010, yani 2'dir. add(p) nesneyi 2 numaralı kovaya koyar. contains(p) yine 2 numaralı kovaya bakar, equals doğru döner ve sonuç true olur.

Sonra p.x = 5 ataması yapılır. Nesnenin hash kodu artık 31 · 36 + 2 = 1118'dir ve kovası 14'tür. Ama nesne hâlâ 2 numaralı kovada durur; küme, alanın değiştiğinden haberdar değildir. Şekil 5.16 bu durumu ve sonucunu gösterir.

İkinci contains(p) kova 14'e bakar. Orası boştur ve sonuç false'tur. Nesne kümededir, ama bulunamaz. Üçüncü sorguda yeni bir Nokta(1, 2) aranır. Bu nesnenin kovası 2'dir ve orada gerçekten bir nesne vardır. Ama o nesne artık (5, 2)'dir; equals yanlış döner ve sonuç yine false'tur. Son olarak add(p) kova 14'ü boş bulur ve aynı nesneyi ikinci kez ekler. size() 2 olur. Küme aynı nesneyi iki kez içerir; “tekrar yok” kuralı bozulmuştur.

Bu hatanın ders çıkarılacak yanı, hiçbir istisna fırlatılmamasıdır. Program çalışmaya devam eder ve yanlış sonuç üretir. Kural basittir: hash'li bir koleksiyondaki (HashSet, HashMap anahtarı) nesnenin equals ve hashCode'a giren alanları değiştirilmez. Anahtar olarak String, Integer gibi değiştirilemez nesneler ya da alanları final olan sınıflar seçilir. Bir alanın değişmesi gerekiyorsa nesne önce kümeden çıkarılır, değiştirilir ve sonra yeniden eklenir.

5.4.6SortedSet ve TreeSet

SortedSet, öğeleri sıralı saklayan küme arayüzüdür. Sıra doğal sıraya (Comparable) ya da verilen bir Comparator'a göredir. Arayüz, sıralı olmanın getirdiği yeni sorgular sunar: en küçük ve en büyük öğe, belirli bir değerden küçükler, belirli bir aralıktakiler. TreeSet AbstractSet'ten türetilir ve NavigableSet (dolayısıyla SortedSet) arayüzünü uygular. İçte bir kırmızı-siyah ağaç (red-black tree) kullanır.

Kırmızı-siyah ağaç kendini dengeleyen bir ikili arama ağacıdır. Her düğümün solundaki öğeler ondan küçük, sağındakiler ondan büyüktür. Ekleme ve silme sırasında ağaç, yüksekliği log n düzeyinde kalacak biçimde düğümleri döndürür. Bu yüzden ekleme, silme ve arama O(log n)'dir. HashSet'in O(1)'inden yavaştır, ama karşılığında sıra verir. Tablo 5.18 TreeSet'in sıralı sorgularını, Şekil 5.17 ağacı verir.

TreeSet<Integer> notlar = new TreeSet<>();
notlar.add(70);
notlar.add(50);
notlar.add(90);
notlar.add(60);
notlar.add(80);
System.out.println(notlar);
System.out.println(notlar.first() + " " + notlar.last());
System.out.println(notlar.headSet(70));     // 70 hariç
System.out.println(notlar.tailSet(70));     // 70 dahil
System.out.println(notlar.subSet(60, 90));  // [60, 90)
System.out.println(notlar.comparator());    // doğal sıra

TreeSet<String> meyveler = new TreeSet<>();
meyveler.add("Elma");
meyveler.add("Armut");
System.out.println(meyveler);

[50, 60, 70, 80, 90]
50 90
[50, 60]
[70, 80, 90]
[60, 70, 80]
null
[Armut, Elma]

Notlar 70, 50, 90, 60, 80 sırasıyla eklenir, ama küme her zaman sıralı yazılır: [50, 60, 70, 80, 90]. first() 50, last() 90'dır. Aralık metotlarında sınırların dahil olup olmadığı önemlidir. Kural “başlangıç dahil, bitiş hariç”tir; bu, Java'nın substring gibi öteki aralık metotlarıyla da uyumludur. headSet(70) 70'i içermez: [50, 60]. tailSet(70) 70'i içerir: [70, 80, 90]. subSet(60, 90) matematikteki [60, 90) aralığıdır: [60, 70, 80]. Doğal sıra kullanıldığı için comparator() null döndürür. Dizgiler de karakter kodlarına göre sıralanır: “Armut”, “Elma”dan önce gelir.

5.4.7Küme işlemleri

Matematikteki birleşim, kesişim ve fark işlemlerinin her birinin Collection'da bir karşılığı vardır. Tablo 5.19 eşleşmeyi verir.

Set<Integer> a = new TreeSet<>(Arrays.asList(1, 2, 3, 4));
Set<Integer> b = new TreeSet<>(Arrays.asList(3, 4, 5));

Set<Integer> birlesim = new TreeSet<>(a);
birlesim.addAll(b);
Set<Integer> kesisim = new TreeSet<>(a);
kesisim.retainAll(b);
Set<Integer> fark = new TreeSet<>(a);
fark.removeAll(b);

System.out.println("A ∪ B = " + birlesim);
System.out.println("A ∩ B = " + kesisim);
System.out.println("A − B = " + fark);
System.out.println(a.containsAll(kesisim));

A ∪ B = [1, 2, 3, 4, 5]
A ∩ B = [3, 4]
A − B = [1, 2]
true

Bu metotlar çağrıldıkları kümeyi değiştirir. a.addAll(b) yazılsaydı a'nın kendisi birleşime dönüşür ve sonraki işlemlerde asıl a kaybolurdu. Bu yüzden her işlemden önce new TreeSet<>(a) ile bir kopya alınır. Birleşim kopyaya b'nin öğelerini ekler; tekrar eden 3 ve 4 ikinci kez eklenmez. Kesişim, kopyada yalnızca b'de de bulunan öğeleri bırakır. Fark, kopyadan b'nin öğelerini çıkarır. Son satır kesisim'in a'nın alt kümesi olduğunu doğrular. TreeSet kullanıldığı için sonuçlar sıralı yazılır. Bu işlemler, parametre olarak verilen koleksiyonun her öğesi için bir contains ya da add yapar; maliyetleri öğe sayısı ile bu işlemin maliyetinin çarpımıdır.

5.5Eşlemeler

Bir öğrenci numarasından öğrenciye, bir ürün adından fiyata, bir kelimeden geçiş sayısına ulaşmak programlamanın en sık işlerindendir. Bu işlerde veri çiftler hâlinde gelir: bir anahtar ve ona bağlı bir değer. Eşleme bu çiftleri saklar ve anahtardan değere hızla gider. Bu kesimde eşleme arayüzü, üç temel gerçeklemesi ve eski Hashtable sınıfı ele alınır.

5.5.1Map arayüzü ve metotları

Eşlemenin en bilinen benzetmesi sözlüktür. Kelime (anahtar) ile anlamı (değer) bulunur ve aynı kelime sözlükte iki kez yer almaz. İki farklı kelimenin anlamı ise aynı olabilir. Eşleme anahtar üzerinden hızlı erişim sağlar ve çiftler üzerinde işlem yapmaya olanak tanır. Şekil 5.19 eşleme sınıflarının hiyerarşisini gösterir.

Üç temel gerçekleme, kümelerdeki üçlünün eşlemedeki karşılığıdır. HashMap sıra garantisi vermez. LinkedHashMap eklenme sırasını korur. TreeMap anahtarları sıralı tutar; sıra doğal sıra ya da verilen Comparator'dır. Tablo 5.20 arayüzün metotlarını verir. K anahtar tipini, V değer tipini gösterir. Örneğin Map<String, Integer> isimden nota bir eşlemedir.

5.5.2HashMap

HashMap, anahtar-değer çiftlerini bir hash tablosunda saklar. AbstractMap'ten türetilmiştir ve Map'i uygular. Çiftin kovası anahtarın hash kodundan hesaplanır; değerin hash kodu hiç kullanılmaz. Bu yüzden get ve put ortalamada O(1)'dir. Öğeler sırasız depolanır.

HashMap<String, Double> urunFiyatlari = new HashMap<>();
urunFiyatlari.put("Telefon", 2000.0);
urunFiyatlari.put("Kulaklık", 350.0);
urunFiyatlari.put("Kılıf", 120.0);
Double eski = urunFiyatlari.put("Telefon", 1800.0);
System.out.println(eski);
System.out.println(urunFiyatlari.get("Telefon"));
System.out.println(urunFiyatlari.get("Tablet"));
System.out.println(urunFiyatlari.containsKey("Kılıf"));
urunFiyatlari.remove("Kılıf");
System.out.println(urunFiyatlari.size());

urunFiyatlari.put(null, 0.0);         // tek null anahtar
urunFiyatlari.put("Kalem", null);     // null değer
System.out.println(urunFiyatlari.size());

2000.0
1800.0
null
true
2
4
null true 0.0

Program şöyle ilerler. Üç ürün eklenir. Dördüncü put("Telefon", 1800.0) yeni bir çift eklemez; var olan anahtarın değerini değiştirir. Anahtarlar tekil olduğu için böyle olur. put eski değeri döndürür: 2000.0. Bu dönüş değeri bir anahtarın daha önce var olup olmadığını öğrenmenin de yoludur; yeni anahtarda put null döndürür. get("Telefon") yeni değeri verir. get("Tablet") bulunmayan bir anahtar için null döndürür, istisna fırlatmaz. containsKey("Kılıf") true döner. Kılıf silindikten sonra eşlemede iki çift kalır.

HashMap bir null anahtara ve birden çok null değere izin verir. Ek satırlar bir null anahtar ve bir null değer ekler; boyut 4 olur. Notun programına eklenmiş son satır bu iznin doğurduğu belirsizliği gösterir. get("Kalem") null döndürür, ama bu “anahtar yok” anlamına gelmez; containsKey("Kalem") true'dur. null değer saklayan bir eşlemede “yok” ile “değeri null” ancak containsKey ile ayırt edilir. getOrDefault("Tablet", 0.0) ise anahtar yoksa verilen varsayılanı döndürür: 0.0.

5.5.3Eşleme üzerinde gezinme

Map Iterable değildir; doğrudan for-each döngüsüne verilemez. Gezinme, eşlemenin sunduğu üç görünümden biri üzerinden yapılır:

Map<String, Integer> notlar = new TreeMap<>();
notlar.put("Cem", 72);
notlar.put("Ayşe", 95);
notlar.put("Banu", 60);

for (String isim : notlar.keySet()) {
    System.out.print(isim + " ");
}
System.out.println();
for (Integer not : notlar.values()) {
    System.out.print(not + " ");
}
System.out.println();
for (Map.Entry<String, Integer> g : notlar.entrySet()) {
    System.out.println(g.getKey() + " → " + g.getValue());
}

Ayşe Banu Cem 
95 60 72 
Ayşe → 95
Banu → 60
Cem → 72

Burada nesne bir TreeMap'tir; anahtarlar alfabetik sırayla gelir. keySet() yalnızca anahtarları verir: Ayşe Banu Cem. values() yalnızca değerleri, anahtarların sırasıyla verir: 95 60 72. entrySet() her çifti bir Map.Entry nesnesi olarak verir. getKey() anahtarı, getValue() değeri okur.

Hem anahtar hem değer gerekiyorsa en verimli yol entrySet()'tir. keySet() üzerinde gezip her anahtar için get çağırmak da aynı sonucu verir, ama her adımda anahtarı yeniden arar. HashMap'te bu ek arama ortalama O(1)'dir; TreeMap'te ise her get O(log n)'dir ve toplam iş O(n log n)'e çıkar. entrySet ise çiftleri zaten elinde tutar ve gezinme O(n)'dir.

Eşlemenin kendisini for-each'e vermek derleme hatasıdır:

MapForEach.java:5: error: for-each not applicable to expression type
        for (String s : m) {
                        ^
  required: array or java.lang.Iterable
  found:    Map<String,Integer>
1 error

İleti, for-each'in yalnızca dizilerde ve java.lang.Iterable tiplerinde kullanılabildiğini, ama bir Map<String,Integer> bulunduğunu söyler.

5.5.4Kelime sayma

Eşlemenin klasik kullanımı bir metindeki kelimeleri saymaktır. Her kelime bir anahtardır, değer ise o kelimenin kaç kez geçtiğidir:

String metin = "elma armut elma kiraz armut elma";
Map<String, Integer> sayac = new TreeMap<>();
for (String k : metin.split(" ")) {
    if (sayac.containsKey(k)) {
        sayac.put(k, sayac.get(k) + 1);
    } else {
        sayac.put(k, 1);
    }
}
System.out.println(sayac);

{armut=2, elma=3, kiraz=1}

metin.split(" ") metni boşluklardan böler ve altı kelimelik bir dizi verir. Döngü her kelime için iki durumdan birini işler. Kelime daha önce görülmüşse eski sayı alınır, bir artırılır ve geri yazılır. İlk kez görülüyorsa 1 değeriyle eklenir. Tablo 5.21 her kelimeden sonraki durumu verir.

“elma” ve “armut” ilk kez görüldüğünde 1 ile eklenir. Üçüncü kelime yine “elma”dır. containsKey doğru döner; eski değer 1 alınır ve 2 yazılır. “kiraz” 1 ile eklenir. “armut” 2'ye, son “elma” 3'e çıkar. Döngü bittiğinde TreeMap anahtarları alfabetik sırayla yazar. Şekil 5.20 eşlemenin üç anını gösterir.

Döngü gövdesi her kelime için en çok üç eşleme işlemi yapar: containsKey, get ve put. getOrDefault ile aynı iş tek satıra iner: sayac.put(k, sayac.getOrDefault(k, 0) + 1). Java 8 ile gelen merge metodu daha da kısadır: sayac.merge(k, 1, Integer::sum). Bu çağrı anahtar yoksa 1 yazar, varsa eski değerle 1'i toplar. Üç yazım aynı sonucu verir:

{armut=2, elma=3, kiraz=1} {armut=2, elma=3, kiraz=1}
{elma=3, kiraz=1, armut=2}

Çıktının ikinci satırı aynı sayaçların bir HashMap'e kopyalanmış hâlidir. Sıra artık alfabetik değildir: elma, kiraz, armut. Sayılar aynıdır, yalnızca gezinme sırası değişmiştir. Kelime sayımında alfabetik çıktı isteniyorsa TreeMap, en hızlı sayım isteniyorsa HashMap seçilir. n kelimelik bir metinde HashMap ile sayım ortalama O(n), TreeMap ile O(n log n) sürer.

5.5.5LinkedHashMap ve Hashtable

LinkedHashMap

LinkedHashMap, HashMap'ten türeyen ve çiftleri ek olarak bağlı listeyle birbirine bağlayan eşlemedir. Bu bağlı liste sayesinde eklenme sırası korunur. Hız ve sıra birlikte önemliyse tercih edilir; sıra önemli değilse HashMap yeterlidir. Temel metotları Map ile aynıdır: put, remove, get, containsKey, size. Aynı rehberi üç eşlemeye koyunca sıra farkı görülür:

Map<String, String> rehber = new LinkedHashMap<>();
rehber.put("Zeynep", "555-1111");
rehber.put("Ahmet", "555-1234");
rehber.put("Mert", "555-2222");
Map<String, String> h = new HashMap<>(rehber);
Map<String, String> t = new TreeMap<>(rehber);
System.out.println("LinkedHashMap: " + rehber);
System.out.println("HashMap:       " + h);
System.out.println("TreeMap:       " + t);

LinkedHashMap: {Zeynep=555-1111, Ahmet=555-1234, Mert=555-2222}
HashMap:       {Ahmet=555-1234, Mert=555-2222, Zeynep=555-1111}
TreeMap:       {Ahmet=555-1234, Mert=555-2222, Zeynep=555-1111}

new HashMap<>(rehber) ve new TreeMap<>(rehber) yazımları, verilen eşlemenin bütün çiftlerini kopyalayan yapıcılardır. LinkedHashMap eklenme sırasını korur: Zeynep, Ahmet, Mert. TreeMap anahtarları alfabetik sıraya dizer. HashMap'in sırası ise kova sırasıdır ve buradaki alfabetik görünüm tesadüftür. Kopyalayan yapıcı, kova sayısını kaynak eşlemenin boyuna göre seçer: üç çift için 4 kova. Dört kovada kova numarası hash değerinin son 2 bitidir. Kümeler kesimindeki ölçüm programının hash değerlerinden Ahmet 1, Mert 2, Zeynep 3 numaralı kovaya düşer. Aynı üç isim 16 kovalı bir tabloya konsaydı kovaları 1, 14 ve 7 olurdu ve sıra Ahmet, Zeynep, Mert'e dönerdi. Tablonun 4 kovalı olduğu, iç diziyi yansımayla okuyan bir ölçüm programıyla doğrulanmıştır. Sonuç açıktır: HashMap'in sırası kova sayısına bağlıdır ve programlar bu sıraya hiçbir zaman güvenmez.

Hashtable

Hashtable, anahtar-değer çiftlerini saklayan, senkronize ve eski bir eşleme sınıfıdır (Java 1.0). HashMap'ten farkı, her metodunun kilitli olmasıdır. Kilitleme yüzünden tek iş parçacıklı programlarda HashMap'ten yavaştır. Çok iş parçacıklı programlarda ise java.util.concurrent paketindeki ConcurrentHashMap daha iyi bir seçimdir; tablonun tamamını kilitlemek yerine daha ince bir kilitleme yapar. Bugün Hashtable çoğunlukla eski kodlarda görülür.

Hashtable'ın ikinci farkı null kabul etmemesidir: anahtarlar da değerler de null olamaz.

Hashtable<String, String> telefonRehberi = new Hashtable<>();
telefonRehberi.put("Ahmet", "555-1234");
System.out.println(telefonRehberi.get("Ahmet"));
System.out.println(telefonRehberi.containsKey("Ayşe"));
// telefonRehberi.put(null, "x");  → NullPointerException

555-1234
false
Exception in thread "main" java.lang.NullPointerException: Cannot invoke "Object.hashCode()" because "key" is null

Notun programında sunumdaki yorum satırı açılmıştır. İlk iki çıktı normaldir; “Ayşe” anahtarı yoktur. put(null, "x") ise NullPointerException fırlatır. İleti hatanın nedenini söyler: tablo kovayı bulmak için anahtarın hashCode() metodunu çağırmak ister, ama anahtar null'dır. null değer de reddedilir; t.put("Ayşe", null) da aynı istisnayı, bu kez iletisiz fırlatır.

5.5.6SortedMap ve TreeMap

SortedMap, anahtarları sıralı saklayan eşleme arayüzüdür; her anahtar bir kez bulunur. Alt eşleme ve üst eşleme gibi aralık işlemleri sunar. TreeMap AbstractMap'ten türetilir ve NavigableMap arayüzünü uygular. Anahtarlar doğal sıraya ya da verilen Comparator'a göre dizilir. İçte TreeSet'teki gibi bir kırmızı-siyah ağaç vardır; get, put, remove O(log n)'dir. Tablo 5.22 sıralı eşleme metotlarını verir. Adları ve sınır kuralları TreeSet'in metotlarıyla aynıdır.

TreeMap<String, Double> urunFiyatlari = new TreeMap<>();
urunFiyatlari.put("Telefon", 2000.0);
urunFiyatlari.put("Kalem", 15.0);
urunFiyatlari.put("Defter", 40.0);
urunFiyatlari.put("Silgi", 5.0);
System.out.println(urunFiyatlari);
System.out.println(urunFiyatlari.firstKey());
System.out.println(urunFiyatlari.lastKey());
System.out.println(urunFiyatlari.headMap("Kalem"));
System.out.println(urunFiyatlari.tailMap("Kalem"));
System.out.println(urunFiyatlari.subMap("Defter", "Silgi"));

{Defter=40.0, Kalem=15.0, Silgi=5.0, Telefon=2000.0}
Defter
Telefon
{Defter=40.0}
{Kalem=15.0, Silgi=5.0, Telefon=2000.0}
{Defter=40.0, Kalem=15.0}

Ürünler hangi sırayla eklenirse eklensin, eşleme anahtarların alfabetik sırasıyla yazılır: Defter, Kalem, Silgi, Telefon. En küçük anahtar Defter, en büyüğü Telefon'dur. headMap("Kalem") Kalem'den küçük anahtarları verir ve Kalem'i içermez: yalnız Defter. tailMap("Kalem") Kalem'i ve ondan büyükleri içerir. subMap("Defter", "Silgi") Defter'i içerir, Silgi'yi içermez. Aralık sorguları sıralanmış anahtarlar sayesinde O(log n) zamanda başlar; HashMap'te aynı sorgu için bütün anahtarları taramak gerekirdi.

5.5.7Eşleme sınıflarını karşılaştırmak

Tablodaki mantık kümelerde de geçerlidir. HashSet, LinkedHashSet ve TreeSet içte sırasıyla HashMap, LinkedHashMap ve TreeMap kullanır; kümenin öğeleri eşlemenin anahtarlarıdır. Bu yüzden bir kümenin sırası, hızı ve null kuralı karşılık geldiği eşlemeninkiyle aynıdır.

5.6Yineleyici

Liste indisle, küme hash tablosuyla, TreeSet ağaçla, ArrayDeque dairesel diziyle çalışır. Bu kadar farklı yapının öğelerini tek bir döngü biçimiyle gezmek ancak ortak bir arayla mümkündür. Bu ara yineleyicidir. Her koleksiyon kendi iç yapısını bilen bir yineleyici üretir; kullanıcı ise yalnızca “sıradaki öğe var mı?” ve “sıradakini ver” diye sorar.

5.6.1Iterator arayüzü

Yineleyiciyi anlamanın en kolay yolu bir imleç düşünmektir. İmleç öğelerin üzerinde değil, aralarında durur. Başlangıçta ilk öğenin önündedir. next() imleci bir öğenin üzerinden atlatır ve atladığı öğeyi döndürür. hasNext() imlecin önünde öğe kalıp kalmadığını söyler. Şekil 5.21 bu düzeni gösterir.

ArrayList<Integer> liste = new ArrayList<>();
liste.add(3);
liste.add(8);
liste.add(5);
Iterator<Integer> iterator = liste.iterator();
while (iterator.hasNext()) {
    Integer sayi = iterator.next();
    // öğe burada işlenir
    System.out.println(sayi);
}

3
8
5

Yineleyici genellikle while (it.hasNext()) döngüsüyle kullanılır. Tablo 5.25 döngüyü adım adım izler.

liste.iterator() imleci ilk öğenin önüne koyar. Döngünün her turunda hasNext() true döndürür, next() sıradaki öğeyi verir ve imleci ilerletir. Üç turdan sonra imleç sondadır. hasNext() false döner ve döngü biter. Öğe kalmamışken next() çağrılırsa NoSuchElementException fırlatılır.

For-each döngüsü arka planda tam olarak bu yineleyici döngüsüne çevrilir. for (Integer sayi : liste) { … } yazıldığında derleyici bir yineleyici oluşturur ve hasNext/next çağrılarını kendisi ekler. Java Dil Belirtimi bu dönüşümü kesin olarak tanımlar. For-each'in yalnızca Iterable tiplerde çalışmasının nedeni de budur.

5.6.2Gezinirken silme

Bir listeden belirli bir koşulu sağlayan öğeleri silmek sık bir iştir. En doğal görünen yol, for-each içinde listenin kendi remove metodunu çağırmaktır. Bu yol yanlıştır:

List<Integer> sayilar = new ArrayList<>(Arrays.asList(4, 7, 10, 13, 16));
for (Integer s : sayilar) {
    if (s % 2 == 0) {
        sayilar.remove(s);
    }
}

Exception in thread "main" java.util.ConcurrentModificationException

İlk çift sayı 4 silinir, ama hemen ardından program ConcurrentModificationException ile durur. Doğru yol, yineleyiciyi açıkça yazmak ve onun kendi remove() metodunu çağırmaktır:

List<Integer> sayilar = new ArrayList<>();
Collections.addAll(sayilar, 4, 7, 10, 13, 16);
Iterator<Integer> it = sayilar.iterator();
while (it.hasNext()) {
    if (it.next() % 2 == 0) {
        it.remove();         // güvenli silme
    }
}
System.out.println(sayilar);

it.next() öğeyi alır ve çift olup olmadığı denetlenir. Çiftse it.remove() son alınan öğeyi listeden çıkarır. Yineleyici silmeyi kendisi yaptığı için iç durumunu da günceller ve gezinme bozulmadan sürer. Java 8 ile aynı işin kısa bir yolu gelmiştir: removeIf. Koşul bir lambda ifadesiyle verilir ve metot döngüyü kendisi kurar:

List<Integer> s2 = new ArrayList<>();
Collections.addAll(s2, 4, 7, 10, 13, 16);
s2.removeIf(s -> s % 2 == 0);
System.out.println(s2);

[7, 13]
[7, 13]

İki yolun çıktısı da aynıdır: yalnız tek sayılar kalır. ArrayList.removeIf önce silinecek öğeleri işaretler, sonra kalanları tek geçişte sola kaydırır. Bu yüzden toplam iş O(n)'dir. Yineleyiciyle tek tek silmek ise her silmede arkadaki öğeleri kaydırır ve en kötü durumda O(n²)'ye çıkar. Büyük listelerde removeIf hem daha kısa hem daha hızlıdır.

it.remove() her next()'ten sonra en çok bir kez çağrılabilir; aksi hâlde IllegalStateException fırlatılır.

5.6.3ConcurrentModificationException nereden gelir?

For-each içindeki silmenin neden istisna fırlattığını anlamak için yineleyicinin içine bakmak gerekir. ArrayList'in bir modCount alanı vardır. Bu alan listenin yapısal değişiklik sayacıdır: her ekleme ve silme onu bir artırır. Yineleyici oluşturulduğu anda bu sayacın değerini expectedModCount adıyla saklar ve bir de cursor (imleç) tutar. Her next() çağrısı önce iki sayacı karşılaştırır. Farklıysa liste yineleyicinin bilgisi dışında değiştirilmiştir ve gezinmeye devam etmek güvenli değildir. Yineleyici bu durumda ConcurrentModificationException fırlatır. Bu davranışa “hızlı başarısız olma” (fail-fast) denir.

List<Integer> s = new ArrayList<>();
Collections.addAll(s, 6, 9, 12);
for (Integer x : s) {      // gizli Iterator
    if (x % 2 == 0) {
        s.remove(x);
    }
}
System.out.println(s);

Tablo 5.26 programı sayaçlarla birlikte izler.

Liste üç öğelidir ve modCount 0'dır. For-each gizlice s.iterator() çağırır: cursor = 0, expectedModCount = 0. İlk hasNext(), cursor (0) ile size (3) farklı olduğu için true döner. next() önce sayaçları karşılaştırır (0 = 0), 6'yı döndürür ve cursor'ı 1 yapar. 6 çifttir ve s.remove(x) çağrılır. Bu, listenin kendi metodudur: 9 ve 12 sola kayar, size 2'ye iner, modCount 1'e çıkar. Yineleyicinin bundan haberi yoktur. Şekil 5.22 bu anı ve sonrasını gösterir.

Sonraki hasNext(), cursor (1) ile size (2) farklı olduğu için true döner; döngü sürer. Ama next() sayaçları karşılaştırınca modCount 1, expectedModCount 0'dır. İstisna fırlatılır ve println'e hiç ulaşılmaz.

Exception in thread "main" java.util.ConcurrentModificationException

İzleme bir şeyi daha gösterir: istisna, silme anında değil bir sonraki next()'te ortaya çıkar. Silmeden sonra hasNext() false dönerse next() hiç çağrılmaz ve istisna da oluşmaz. Liste {6, 9} olsaydı 6 silindikten sonra cursor 1, size 1 olurdu. hasNext() false döner ve döngü sessizce biterdi:

[9]

Program hatasız biter, ama 9 hiç denetlenmemiştir. Yanlış kod bazen çalışıyormuş gibi görünür. Bu yüzden “bende çalıştı” demek yeterli değildir. Gezinirken silme her zaman yineleyicinin remove'u ya da removeIf ile yapılır. İstisnanın adındaki “concurrent” (eş zamanlı) sözcüğü yanıltıcı olabilir. Bu hata çok iş parçacıklı programa özgü değildir; tek iş parçacıklı bir programda da, burada olduğu gibi, ortaya çıkar.

5.7Algoritmalar

Koleksiyon Çerçevesinin üçüncü unsuru hazır algoritmalardır. Bunların çoğu java.util.Collections sınıfında toplanmıştır. Bu kesim sıralama, sıra tanımlama (Comparable ve Comparator), karıştırma, arama ve kompozisyon algoritmalarını sırasıyla anlatır.

5.7.1Collections sınıfı

İki ad sık karıştırılır. Collection bir arayüzdür ve bütün koleksiyonların ortak metotlarını tanımlar. Collections (sonunda “s”) ise koleksiyonlar üzerinde çalışan hazır static metotları toplayan bir yardımcı sınıftır. Bu sınıftan nesne oluşturulmaz; metotları Collections.sort(liste) gibi sınıf adıyla çağrılır.

Bu algoritmalar hızlı ve test edilmiştir; aynı işi elle yazmak hem zaman alır hem hata riski taşır. Dört grupta toplanırlar:

• Sıralama: sort, reverse, reverseOrder.
• Karıştırma: shuffle.
• Arama: binarySearch, max, min, frequency.
• Kompozisyon: copy, fill, swap, reverse.

5.7.2Sıralama

List<String> isimler = new ArrayList<>(
        Arrays.asList("Cem", "Ayşe", "Banu", "Ali"));
Collections.sort(isimler);
System.out.println(isimler);
Collections.sort(isimler, Collections.reverseOrder());
System.out.println(isimler);
Collections.reverse(isimler);
System.out.println(isimler);

[Ali, Ayşe, Banu, Cem]
[Cem, Banu, Ayşe, Ali]
[Ali, Ayşe, Banu, Cem]

Collections.sort(isimler) listeyi doğal sıraya göre, yani alfabetik olarak sıralar. İkinci çağrı bir karşılaştırıcı alır: Collections.reverseOrder() doğal sırayı tersine çevirir ve liste Z'den A'ya dizilir. Collections.reverse ise hiçbir karşılaştırma yapmaz; listenin o anki sırasını ters çevirir. Azalan sıradaki liste ters çevrilince yeniden artan sıra elde edilir. Tablo 5.27 üç metodu özetler.

String, Integer, Double gibi sınıflar zaten Comparable'dır. Java 8'den beri listenin kendi sort metodu da vardır: liste.sort(null) doğal sıraya göre sıralar, liste.sort(c) karşılaştırıcıya göre. Öğeleri karşılaştırılamayan bir liste Collections.sort'a verilirse hata derleme zamanında yakalanır:

OgrenciSort.java:9: error: no suitable method found for sort(List<Ogr>)
        Collections.sort(l);
                   ^
    method Collections.<T#1>sort(List<T#1>) is not applicable
      (inference variable T#1 has incompatible bounds
        equality constraints: Ogr
        upper bounds: Comparable<? super T#1>)
    method Collections.<T#2>sort(List<T#2>,Comparator<? super T#2>) is not applicable
      (cannot infer type-variable(s) T#2
        (actual and formal argument lists differ in length))
  where T#1,T#2 are type-variables:
    T#1 extends Comparable<? super T#1> declared in method <T#1>sort(List<T#1>)
    T#2 extends Object declared in method <T#2>sort(List<T#2>,Comparator<? super T#2>)
1 error

İleti uzundur ama özü tek satırdadır: Ogr tipi Comparable<? super T> üst sınırını sağlamaz, yani karşılaştırılabilir değildir. İkinci olarak önerilen sort(List, Comparator) biçimi de argüman sayısı tutmadığı için uymaz. Öncelikli kuyruktaki çalışma anı hatasından farklı olarak burada derleyici sorunu önceden görür; sort'un imzası tip parametresini sınırlamıştır.

Collections.sort nesne listelerinde TimSort algoritmasını kullanır. TimSort birleştirme sıralamasının uyarlanmış bir türüdür. En kötü durumda O(n log n) sürer ve kısmen sıralı verilerde çok daha hızlıdır. Ayrıca kararlıdır (stable): eşit sayılan öğelerin kendi arasındaki sırası korunur. İlkel dizileri sıralayan Arrays.sort(int[]) ise Dual-Pivot Quicksort kullanır; ilkel değerlerde kararlılığın anlamı olmadığı için bu seçim yapılmıştır. Notun programı “Cem:B, Ali:A, Ece:B, Banu:A, Can:A” listesini yalnızca harf notuna göre sıralamıştır. Sonuç [Ali:A, Banu:A, Can:A, Cem:B, Ece:B]'dir: aynı notu alanlar listedeki eski sıralarını korur. Bu sayede alfabetik bir liste nota göre sıralanınca aynı notu alanlar alfabetik kalır.

5.7.3Comparable: doğal sıra

class Ogrenci implements Comparable<Ogrenci> {
    String isim;
    int puan;

    Ogrenci(String isim, int puan) {
        this.isim = isim;
        this.puan = puan;
    }

    // puana göre artan sıra
    @Override
    public int compareTo(Ogrenci diger) {
        return Integer.compare(puan, diger.puan);
    }

    @Override
    public String toString() {
        return isim + ":" + puan;
    }
}

List<Ogrenci> sinif = new ArrayList<>();
sinif.add(new Ogrenci("Cem", 72));
sinif.add(new Ogrenci("Ayşe", 95));
sinif.add(new Ogrenci("Banu", 60));

Collections.sort(sinif);
System.out.println(sinif);

[Banu:60, Cem:72, Ayşe:95]
[Ayşe:95, Banu:60, Cem:72]
[Banu:60, Cem:72, Ayşe:95]
[Ayşe:95, Cem:72, Banu:60]

Ogrenci sınıfı Comparable<Ogrenci>'yi uygular ve puana göre artan sırayı tanımlar. Collections.sort(sinif) bu sırayı kullanır: Banu (60), Cem (72), Ayşe (95). Programın sonraki satırları karşılaştırıcı örnekleridir ve bir sonraki alt kesimde açıklanır.

compareTo'nun gövdesinde Integer.compare(puan, diger.puan) kullanılmıştır. Aynı iş return puan - diger.puan; ile de yapılabilir gibi görünür: fark negatifse this küçüktür. Puanlar küçük sayılar olduğu sürece bu doğru çalışır. Ama çok büyük ve zıt işaretli iki sayının farkı int aralığını aşar ve işaret ters döner:

public class Tasma {
    public static void main(String[] args) {
        int a = 2_000_000_000, b = -2_000_000_000;
        System.out.println((a - b) + " " + Integer.compare(a, b));
    }
}

-294967296 1

2 milyar −2 milyardan büyüktür ve fark pozitif olmalıdır. Ama 4 milyar int'e sığmaz ve sonuç negatif çıkar; sıralama yanlış olur. Integer.compare çıkarma yapmaz, yalnızca karşılaştırır ve doğru sonucu (1) verir. Bu yüzden çıkarma yerine her zaman Integer.compare (ya da Double.compare) kullanılır.

İyi bir compareTo'nun uyması gereken birkaç kural vardır. a, b'den önceyse b, a'dan sonra olmalıdır. a b'den, b de c'den önceyse a c'den önce olmalıdır. Ayrıca compareTo'nun 0 döndürdüğü nesnelerin equals'ının da doğru dönmesi önerilir. Bu son kural TreeSet ve TreeMap için önemlidir: bu yapılar eşitliği equals ile değil compareTo ile sınar. Puanı aynı iki farklı öğrenci bir TreeSet'e konursa ikincisi “tekrar” sayılır ve eklenmez.

5.7.4Comparator: başka bir sıra

Collections.sort(sinif, new Comparator<Ogrenci>() {
    @Override
    public int compare(Ogrenci a, Ogrenci b) {
        return a.isim.compareTo(b.isim);   // isme göre
    }
});
System.out.println(sinif);

// Java 8+: aynı işin kısa yazımı
sinif.sort(Comparator.comparing(o -> o.puan));
System.out.println(sinif);

Bu kod, önceki programın devamıdır ve çıktının ikinci ve üçüncü satırlarını üretir. Klasik yazımda karşılaştırıcı bir anonim sınıfla (anonymous class) yazılır: new Comparator<Ogrenci>() { … } adı olmayan, yerinde tanımlanan ve tek nesnesi oluşturulan bir sınıftır. Bu karşılaştırıcı isimleri String'in compareTo'suyla karşılaştırır ve liste alfabetik olur: Ayşe, Banu, Cem.

Java 8 ile aynı iş tek satıra iner. Comparator.comparing(o -> o.puan), her öğrenciden puanını çıkaran bir fonksiyon alır ve bu değerlere göre karşılaştıran bir karşılaştırıcı üretir. Liste yeniden puan sırasına döner. Ters sıra için .reversed() eklenir. Notun programındaki son satır bunu yapar: Comparator.comparing((Ogrenci o) -> o.puan).reversed() ile liste en yüksek puandan başlar. Lambda'nın parametre tipinin bu yazımda açıkça verilmesi gerekir; .reversed() zinciri derleyicinin tipi soldan çıkarmasını engeller.

5.7.5Karıştırma

Karıştırma, koleksiyon öğelerini rastgele bir sıraya sokmaktır. Kart dağıtma, kura çekme ve sınavda soru sırasını rastgele yapma tipik kullanımlardır. Collections.shuffle(liste) Fisher–Yates (Knuth) algoritmasını kullanır. Algoritma listenin sonundan başlar. Her adımda, henüz yerleşmemiş öğeler arasından rastgele birini seçer ve o anki konumdaki öğeyle yer değiştirir. n öğeli listede n − 1 yer değiştirme yapılır ve iş O(n)'dir. Algoritmanın değerli yanı, her olası sıralamanın eşit olasılıkla ortaya çıkmasıdır (düzgün dağılım).

List<String> ogrenciler = new ArrayList<>(
        Arrays.asList("Ali", "Banu", "Cem", "Deniz"));
Collections.shuffle(ogrenciler);
System.out.println(ogrenciler);

Bu programın çıktısı her çalıştırmada farklıdır; sunumdaki [Cem, Ali, Deniz, Banu] olası 24 sıralamadan yalnızca biridir. Test yazarken ya da bir sonucu tekrar üretmek gerektiğinde aynı karışım istenir. Bunun için ikinci argüman olarak sabit tohumlu bir rastgele sayı üreteci verilir: Collections.shuffle(liste, new Random(42)). Notun programı aynı listeyi iki kez 42 tohumuyla karıştırır ve iki sonuç birebir aynıdır:

[Deniz, Banu, Ali, Cem]
[Deniz, Banu, Ali, Cem]

Loto örneği

Karıştırmanın güzel bir uygulaması tekrarsız rastgele seçimdir. 1'den 49'a kadar sayılar bir listeye konur, liste karıştırılır ve ilk 6 öğe alınır:

public class Loto {
    // Loto çekilişi yapan metot
    public static Integer[] lotoYap(int toplamSayi, int cekilecekSayi) {
        ArrayList<Integer> sayilar = new ArrayList<Integer>();
        for (int i = 0; i < toplamSayi; i++) {
            sayilar.add(i + 1);          // 1 … toplamSayi
        }
        Collections.shuffle(sayilar);    // karıştır
        Integer[] cekilenSayilar = new Integer[cekilecekSayi];
        for (int i = 0; i < cekilecekSayi; i++) {
            cekilenSayilar[i] = sayilar.get(i);
        }
        return cekilenSayilar;
    }

    public static void main(String[] args) {
        Integer[] sonuc = lotoYap(49, 6);   // 49'dan 6
        for (Integer item : sonuc) {
            System.out.print(item + " ");
        }
    }
}

Bir çalıştırmanın çıktısı şudur (her çalıştırmada farklıdır):

21 25 16 3 33 46 

Karıştırma sayıları yalnızca yer değiştirdiği için listede her sayı tam bir kez bulunur. İlk altı öğe de bu yüzden tekrarsızdır. Notun sınama programı lotoYap(49, 6)'yı 10 000 kez çağırıp her sonucun 6 farklı ve 1–49 aralığında sayı içerdiğini denetlemiştir; hata sayısı 0'dır. Maliyet, seçilen sayı adedinden bağımsız olarak bütün listeyi kurup karıştırmanın maliyetidir: toplamSayi kadar, yani O(n).

5.7.6Arama

Bir koleksiyonda öğe aramanın iki temel yolu vardır.

Doğrusal arama (linear search)

Öğeleri baştan sona tek tek kontrol eder. Koleksiyonun sıralı olması gerekmez. Küçük koleksiyonlarda etkilidir. Maliyeti O(n)'dir. indexOf ve contains doğrusal arama yapar.

İkili arama (binary search)

Sıralı koleksiyonda ortadaki öğeye bakar. Aranan değer küçükse sol yarıda, büyükse sağ yarıda aramaya devam eder. Her adımda aralık yarıya iner. Maliyeti O(log n)'dir. Koleksiyon sıralı olmalıdır.

List<Integer> sayilar = Arrays.asList(1, 3, 5, 7, 9, 11);
System.out.println(Collections.binarySearch(sayilar, 7));
System.out.println(Collections.binarySearch(sayilar, 6));
System.out.println(sayilar.indexOf(7));    // doğrusal arama

3
-4
3
-1 -7
2

İlk üç satır sunumdaki çıktıdır. binarySearch(sayilar, 7) 7'yi indis 3'te bulur. Arama şu adımlarla ilerler. Aralık 0–5'tir; ortadaki indis 2'deki 5, 7'den küçüktür ve arama sağ yarıya geçer. Aralık 3–5'tir; ortadaki indis 4'teki 9, 7'den büyüktür ve sol yarıya geçilir. Aralık 3–3'tür ve indis 3'teki 7 bulunur. Üç karşılaştırma yapılmıştır. Notun sayım programı, karşılaştırıcıya bir sayaç ekleyerek bu sayıyı doğrular:

7: sonuç 3, 3 karşılaştırma
6: sonuç -4, 3 karşılaştırma
1 milyon öğe, denenen en çok: 20

6 listede yoktur. Arama bitince 6'nın girmesi gereken yer, yani ekleme noktası 3'tür: 5'ten sonra, 7'den önce. Bulunamayan değer için dönüş −(ekleme noktası) − 1'dir: −(3) − 1 = −4. Bu biçim iki bilgiyi birden taşır. Sonuç negatifse öğe yoktur; −(sonuç) − 1 ise öğenin sırayı bozmadan ekleneceği yeri verir. “Neden yalnızca −3 değil?” sorusunun yanıtı 0'dır: ekleme noktası 0 olsaydı −0 = 0 çıkar ve “indis 0'da bulundu” ile karışırdı. Notun programının dördüncü satırı uç durumları gösterir. 0 aranınca ekleme noktası 0'dır ve dönüş −1'dir. 12 aranınca ekleme noktası 6'dır (listenin sonu) ve dönüş −7'dir.

Liste sıralı değilse sonuç tanımsızdır. Programın son satırı 7'yi sırasız bir listede arar ve 2 döndürür. Ama 7 aslında indis 2'dedir; bu doğru sonuç tesadüftür. Başka bir değer aransa yanlış bir indis ya da “yok” dönebilirdi. binarySearch listenin sıralı olup olmadığını denetlemez; bu denetim O(n) süreceği için yapılmaz.

İki aramanın farkı büyük verilerde çarpıcıdır. Bir milyon öğede doğrusal arama bir milyona kadar karşılaştırma yapar. İkili arama ise en fazla 20 karşılaştırma yapar, çünkü 2²⁰ ≈ 1 milyondur. Sayım programının son satırı, bir milyon öğeli listede denenen değerler arasında en çok 20 karşılaştırma yapıldığını gösterir. Sık arama yapılan bir liste bir kez sıralanır ve sonra ikili aramayla kullanılır. Sıralama O(n log n) sürer, ama sonraki her arama O(log n)'dir.

5.7.7Kompozisyon algoritmaları

Kompozisyon algoritmaları bir listenin öğelerini kopyalar, değiştirir, yerlerini değiştirir ya da sayar. Tablo 5.28 bunları toplar.

List<Integer> n = Arrays.asList(4, 9, 2, 9, 5);
System.out.println(Collections.max(n));
System.out.println(Collections.min(n));
System.out.println(Collections.frequency(n, 9));

9
2
2

max ve min listenin bütün öğelerine bakar ve doğal sıraya göre en büyüğü ve en küçüğü verir: 9 ve 2. frequency(n, 9) 9'un kaç kez geçtiğini sayar: 2. Üçü de listeyi bir kez dolaşır ve O(n)'dir. Listenin sıralı olması gerekmez.

List<String> isimler =
        Arrays.asList("Ahmet", "Ayşe", "Cem");
List<String> hedef = new ArrayList<>(
        Arrays.asList("X", "Y", "Z", "W"));
Collections.copy(hedef, isimler);
System.out.println(hedef);
Collections.reverse(hedef);
System.out.println(hedef);
Collections.swap(hedef, 0, 2);
System.out.println(hedef);
Collections.fill(hedef, "Java");
System.out.println(hedef);

[Ahmet, Ayşe, Cem, W]
[W, Cem, Ayşe, Ahmet]
[Ayşe, Cem, W, Ahmet]
[Java, Java, Java, Java]

Tablo 5.29 dört işlemi adım adım verir.

isimler, Arrays.asList ile oluşturulmuş sabit boyutlu bir listedir. hedef ise dört öğeli değiştirilebilir bir ArrayList'tir. copy kaynağın üç öğesini hedefin 0, 1 ve 2 numaralı konumlarına yazar. Hedefin dördüncü öğesi W yerinde kalır; copy hedefin boyunu değiştirmez. reverse sırayı tersine çevirir: [W, Cem, Ayşe, Ahmet]. swap(hedef, 0, 2) 0 ve 2 numaralı konumları değiştirir: W ile Ayşe yer değiştirir. fill bütün öğeleri “Java” yapar; boyut yine 4'tür. Şekil 5.23 iki ara durumu gösterir.

copy'nin hedef koşulu sık hata yaptırır. Hedef kaynaktan kısaysa istisna fırlatılır. Asıl tuzak, kapasitesi yeterli ama boş bir listedir. new ArrayList<>(10) 10 hücre ayırır, ama boyu 0'dır; copy kapasiteye değil boya bakar:

import java.util.*;
public class BosHedef {
    public static void main(String[] args) {
        List<String> kaynak = Arrays.asList("a", "b", "c");
        List<String> hedef = new ArrayList<>(10);
        System.out.println(hedef.size());
        Collections.copy(hedef, kaynak);
    }
}

0
Exception in thread "main" java.lang.IndexOutOfBoundsException: Source does not fit in dest

Bir listenin bağımsız kopyası gerekiyorsa copy yerine kopyalayan yapıcı kullanılır: new ArrayList<>(kaynak). Bu yol hedefin boyunu dert etmez ve tek satırdır.

5.8Akış API'si

Önceki kesimlerdeki işlerin çoğu aynı kalıbı izler: bir koleksiyonu gez, bazı öğeleri seç, onları dönüştür, sonucu yeni bir koleksiyonda topla. Bu kalıp her seferinde bir döngü, bir koşul ve bir ara liste yazdırır. Java 8 ile gelen Akış API'si aynı işi bir işlem hattı olarak yazmayı sağlar.

5.8.1Akış ve işlem hattı

Buradaki akış, InputStream gibi giriş/çıkış (G/Ç) akışlarından farklı bir kavramdır; yalnızca adları aynıdır. Bir akış veri saklamaz. Bir kaynağın (liste, dizi, dosya satırları) üzerinden geçer ve kaynağı değiştirmez. Şekil 5.24 bir hattı gösterir.

List<Integer> notlar = Arrays.asList(45, 82, 67, 90, 38, 75);
List<Integer> gecenler = notlar.stream()
    .filter(n -> n >= 50)
    .map(n -> n + 5)
    .sorted()
    .collect(Collectors.toList());
System.out.println(gecenler);

[72, 80, 87, 95]
[45, 82, 67, 90, 38, 75]
[72, 80, 87, 95]
[72, 80, 87, 95]

Hat dört adımdır. filter 50 ve üstündeki notları geçirir: 82, 67, 90, 75. map her birine 5 ekler: 87, 72, 95, 80. sorted bunları sıralar. collect(Collectors.toList()) sonucu yeni bir listede toplar. Notun programındaki ikinci satır kaynağın değişmediğini, üçüncü satır Java 16'daki kısa yazımı (.toList()), dördüncü satır ise aynı işin döngüyle yazılmış hâlini gösterir. Döngü sürümü bir ara liste, bir koşul ve ayrı bir sıralama çağrısı ister. Akış sürümü her adımı adıyla söyler. Gereken içe aktarmalar java.util.* ve java.util.stream.Collectors'tır.

Collectors.toList() ile .toList() arasında küçük bir fark vardır. İlki değiştirilebilir bir liste döndürür (pratikte bir ArrayList). İkincisi değiştirilemez bir liste döndürür; ona add çağrılırsa UnsupportedOperationException fırlatılır.

5.8.2Ara ve uç işlemler

Ara işlem yeni bir akış döndürür ve zincir sürer. Uç işlem akış dışında bir sonuç (ya da hiçbir şey) döndürür ve hattı çalıştırır. Uç işlemi olmayan bir hat hiçbir şey yapmaz. Tablodaki işlemlerin birkaçı notun programında denenmiştir:

import java.util.*;
import java.util.stream.*;
public class Ana68 {
    public static void main(String[] args) {
        List<List<Integer>> ic = Arrays.asList(Arrays.asList(1, 2), Arrays.asList(3), Arrays.asList(4, 5));
        System.out.println(ic.stream().flatMap(List::stream).collect(Collectors.toList()));
        System.out.println(Stream.of(3, 1, 3, 2, 1).distinct().collect(Collectors.toList()));
        System.out.println(Stream.of(1, 2, 3, 4, 5, 6).skip(2).limit(3).collect(Collectors.toList()));
        System.out.println(Stream.of(4, 8, 15).count());
        System.out.println(Stream.of(4, 8, 15).anyMatch(x -> x > 10) + " " + Stream.of(4, 8, 15).allMatch(x -> x > 3)
                + " " + Stream.of(4, 8, 15).noneMatch(x -> x > 20));
        System.out.println(Stream.of(4, 8, 15).max(Integer::compare) + " " + Stream.<Integer>empty().findFirst());
        Stream.of("a", "b").peek(s -> System.out.print("peek " + s + "; ")).forEach(s -> System.out.print("forEach " + s + "; "));
        System.out.println();
        long n = Stream.of(1, 2, 3).peek(x -> System.out.print("görülmez ")).count();
        System.out.println("count " + n);
    }
}

[1, 2, 3, 4, 5]
[3, 1, 2]
[3, 4, 5]
3
true true true
Optional[15] Optional.empty
peek a; forEach a; peek b; forEach b; 
count 3

flatMap üç iç listeyi tek bir sayı akışına açar. distinct tekrar eden 3 ve 1'i atar ve ilk görülme sırasını korur. skip(2).limit(3) ilk iki öğeyi atlar ve sonraki üçünü alır. max sonucu Optional içinde verir; boş akışta findFirst Optional.empty döndürür. peek satırı öğelerin hattan tek tek geçtiğini gösterir: “peek a” hemen ardından “forEach a” gelir. Son satır ise bir uyarıdır. JDK 21, count()'un sonucunu kaynağın boyundan doğrudan bildiği için hattı hiç çalıştırmaz ve peek'teki yazı görülmez. peek yalnızca hata ayıklama içindir; asıl iş onun içine konmaz.

5.8.3Tembel değerlendirme ve tek kullanım

List<String> adlar =
    Arrays.asList("Arda", "Ece", "Ayşe", "Can");
Stream<String> hat = adlar.stream()
    .filter(s -> s.startsWith("A"))
    .map(String::toUpperCase);
// Henüz hiçbir öğe işlenmedi.
List<String> sonuc =
    hat.collect(Collectors.toList());
System.out.println(sonuc);  // [ARDA, AYŞE]
hat.count();   // IllegalStateException

[ARDA, AYŞE]
Exception in thread "main" java.lang.IllegalStateException: stream has already been operated upon or closed

hat değişkeni bir Stream<String>'dir. İlk üç satır çalıştığında henüz hiçbir ad süzülmemiş, hiçbir harf büyütülmemiştir. collect çağrılınca hat çalışır ve sonuç [ARDA, AYŞE] olur. String::toUpperCase bir metot referansıdır; s -> s.toUpperCase() lambda'sının kısa yazımıdır. Son satır ikinci kuralı gösterir: akış tek kullanımlıktır. Uç işlemden sonra aynı akış yeniden kullanılırsa IllegalStateException fırlatılır. Gerekirse kaynaktan yeni bir akış alınır: adlar.stream().

Tembelliğin iki önemli sonucu vardır. Birincisi, öğeler hattan tek tek geçer. İlk öğe filter'dan ve map'ten geçer, ancak sonra ikinci öğe gelir. İkincisi, findFirst ve limit gibi işlemler sonucu bulunca durur ve kalan öğeler hiç işlenmez. Bu, sonsuz bir kaynakla bile çalışmayı mümkün kılar: Stream.iterate(1, x -> x * 2).filter(x -> x > 100).findFirst() 1, 2, 4, … diye sonsuza giden bir akıştan 128'i bulur ve durur. sorted ise bu kuralın istisnasıdır: sıralayabilmek için önce bütün öğeleri toplaması gerekir.

import java.util.*;
import java.util.stream.*;
public class SortedBekler {
    public static void main(String[] args) {
        List<Integer> l = Stream.of(3, 1, 2)
            .peek(x -> System.out.println("önce " + x))
            .sorted()
            .peek(x -> System.out.println("sonra " + x))
            .collect(Collectors.toList());
        System.out.println(l);
    }
}

önce 3
önce 1
önce 2
sonra 1
sonra 2
sonra 3
[1, 2, 3]

Üç “önce” satırı “sonra” satırlarından önce gelir; sorted hatta bir bekleme noktasıdır; bütün öğeler gelene kadar hiçbir öğeyi ileri geçirmez.

5.8.4Akış hattını adım adım izlemek

Tembelliği gözle görmek için filter ve map'e birer yazdırma satırı ekleyelim:

List<String> adlar = Arrays.asList("Arda", "Ece", "Ayşe", "Can");
Stream<String> hat = adlar.stream()
    .filter(s -> { System.out.println("filter " + s);
                   return s.startsWith("A"); })
    .map(s -> { System.out.println("map " + s);
                return s.toUpperCase(); });
System.out.println("hat hazır");
List<String> sonuc = hat.collect(Collectors.toList());
System.out.println(sonuc);

hat hazır
filter Arda
map Arda
filter Ece
filter Ayşe
map Ayşe
filter Can
[ARDA, AYŞE]

Hat kurulurken hiçbir lambda çalışmaz ve çıktı boştur. “hat hazır” satırı bu yüzden bütün işlemlerden önce yazılır. collect hattı çalıştırınca ilk öğe Arda filter'a girer, “A” ile başladığı için geçer ve hemen map'e gider. İkinci öğeye ancak o zaman sıra gelir. Ece koşulu sağlamaz ve map'e hiç ulaşmaz. Ayşe geçer ve büyütülür. Can elenir. Sonuçta filter 4 kez, map yalnızca 2 kez çalışmıştır. Şekil 5.25 iki anı gösterir.

Aynı hatta collect yerine findFirst kullanılırsa hat ilk sonucu bulunca durur:

filter Arda
map Arda
ARDA

Yalnızca Arda işlenmiştir; Ece, Ayşe ve Can için hiçbir lambda çağrılmamıştır. Döngüyle yazılmış bir koddaki break'in karşılığı budur.

5.8.5reduce, Collectors ve ilkel akışlar

List<String> meyveler = Arrays.asList(
    "elma", "kivi", "muz", "erik", "incir");
int toplam = Arrays.asList(4, 8, 15, 16, 23)
    .stream().reduce(0, Integer::sum);
Map<Integer, List<String>> boy = meyveler
    .stream().collect(
        Collectors.groupingBy(String::length));
String hepsi = meyveler.stream()
    .collect(Collectors.joining(", "));
int t = IntStream.rangeClosed(1, 100).sum();
Optional<String> z = meyveler.stream()
    .filter(m -> m.startsWith("z")).findFirst();
System.out.println(z.orElse("yok"));

yok
toplam = 66
boy = {3=[muz], 4=[elma, kivi, erik], 5=[incir]}
hepsi = elma, kivi, muz, erik, incir
t = 5050
OptionalDouble[50.5] OptionalDouble.empty
{3=1, 4=3, 5=1}
20
ilk e: elma
Optional[27]

reduce(0, Integer::sum) öğeleri tek bir değere indirger. Başlangıç değeri 0'dır ve her öğe bir önceki sonuca eklenir: 0 + 4 + 8 + 15 + 16 + 23 = 66. Collectors.groupingBy(String::length) meyveleri uzunluklarına göre gruplar ve bir Map<Integer, List<String>> üretir. Collectors.joining(", ") dizgileri araya ayıraç koyarak birleştirir. IntStream.rangeClosed(1, 100) 1'den 100'e kadar int değerlerinden oluşan bir akıştır. İlkel akışlar (IntStream, LongStream, DoubleStream) kutulama yapmaz ve sum, average gibi hazır uç işlemler sunar; toplam 5050'dir.

findFirst'ün dönüş tipi Optional<String>'dir. Optional, “sonuç olmayabilir” durumunu null yerine açıkça ifade eden bir kaptır. “z” ile başlayan meyve yoktur; orElse("yok") boş kap için verilen varsayılanı döndürür. ifPresent ise yalnızca değer varsa bir iş yapar. Ek satırlar üç şeyi daha gösterir. average bir OptionalDouble döndürür, çünkü boş akışta ortalama tanımsızdır. groupingBy'a ikinci toplayıcı olarak counting() verilebilir. mapToInt nesne akışından ilkel akışa geçer. Boş bir Optional üzerinde get() çağırmak NoSuchElementException: No value present fırlatır. Bu yüzden get yerine orElse ya da ifPresent tercih edilir.

5.8.6Yan etkiler ve paralel akışlar

Akışlar “ne yapılacağını” tarif eder; hattaki lambdaların dış dünyayı değiştirmemesi beklenir. Dış bir değişkeni ya da koleksiyonu değiştiren lambdaya yan etkili denir. Sonuç map, collect, reduce ile üretilmelidir. Bu kural paralel akışlarda zorunlu hâle gelir. parallel() ya da parallelStream(), işi ortak ForkJoinPool'un iş parçacıklarına böler.

List<Integer> liste = new ArrayList<>();
IntStream.range(0, 10000).parallel()
    .forEach(liste::add);          // YANLIŞ: paylaşılan liste

List<Integer> dogru = IntStream.range(0, 10000).parallel()
    .boxed()
    .collect(Collectors.toList()); // DOĞRU: 10000 öğe

İlk hatta birden çok iş parçacığı aynı ArrayList'e aynı anda add yapar. ArrayList iş parçacığı güvenli değildir. İki iş parçacığı aynı hücreye yazabilir ya da biri iç diziyi büyütürken öteki eski diziye yazabilir. Sonuç çalıştırmaya göre değişir. Notun ölçüm programı ilk hattı 12 çekirdekli bir makinede 200 kez çalıştırmıştır:

200 deneme: AIOOBE 58, eksik 91 (en az 638, en çok 10000), tam 51, diğer 0; çekirdek 12
200 deneme: AIOOBE 51, eksik 145 (en az 969, en çok 10000), tam 4, diğer 0; çekirdek 12

Üç sonuç da görülmüştür: ArrayIndexOutOfBoundsException, 10 000'den az öğe ve bazen tesadüfen doğru boyut. Doğru sonucun ara sıra çıkması hatayı daha da tehlikeli yapar; bir sınama bunu yakalamayabilir. İkinci hat her çalıştırmada 10 000 öğe ve doğru sırayı verir. collect her iş parçacığına kendi ara listesini verir ve bunları sonda güvenle birleştirir.

boyut 6805
doğru 10000 0 9999

Paralel akış her zaman hızlı değildir. İşi bölmek, iş parçacıklarına dağıtmak ve sonuçları birleştirmek bir maliyettir. Küçük veride, ucuz işlemlerde, G/Ç bekleyen işlerde ve sıraya bağlı işlemlerde (sorted, findFirst) paralel akış yavaşlatabilir. Paralelliğe geçmeden önce ölçülür. Akışlarla ilgili sık hatalar şunlardır: akışı ikinci kez kullanmak, asıl işi peek içinde yapmak, forEach ile dış koleksiyon doldurmak, paralel akışı kendiliğinden hızlı saymak.

5.9Doğru koleksiyonu seçmek

5.9.1Seçim tablosu

Koleksiyon seçimi iki soruyla başlar: hangi işlem en sık yapılacak ve sıra önemli mi? Tablo 5.32 tipik ihtiyaçları karşılayan sınıfları verir.

Değişken arayüz tipinde tanımlanırsa (List, Set, Map, Queue, Deque) ihtiyaç değiştiğinde yalnızca new satırı değişir. Önce doğru arayüz, sonra gerçekleme seçilir.

5.9.2Değiştirilemez koleksiyonlar

Bazı koleksiyonların oluşturulduktan sonra hiç değişmemesi istenir: haftanın günleri, sabit renk listesi, bir yapılandırma tablosu. Java 9 ile gelen fabrika metotları bu tür koleksiyonları tek satırda üretir:

List<String> r = List.of("kırmızı", "yeşil");
Set<Integer> asal = Set.of(2, 3, 5);
Map<String, Integer> puan =
        Map.of("Ali", 90, "Banu", 85);
System.out.println(r);
System.out.println(puan.get("Banu"));
r.add("mavi");

[kırmızı, yeşil]
85
Exception in thread "main" java.lang.UnsupportedOperationException

List.of, Set.of ve Map.of değiştirilemez (immutable) koleksiyonlar döndürür. Okuma serbesttir; add, remove, put ise UnsupportedOperationException fırlatır. Bu koleksiyonlar null öğe kabul etmez. Set.of(1, 1) gibi tekrar içeren bir çağrı da IllegalArgumentException: duplicate element: 1 fırlatır.

Java 1.2'den beri bulunan ikinci yol Collections.unmodifiableList'tir. Bu metot yeni bir koleksiyon değil, bir salt okunur görünüm döndürür:

List<String> liste = new ArrayList<>();
liste.add("a");
List<String> salt =
        Collections.unmodifiableList(liste);
liste.add("b");
System.out.println(salt);
salt.add("c");

[a, b]
[a, b, x] [a, b]
Exception in thread "main" java.lang.UnsupportedOperationException

salt görünümü üzerinden değişiklik yapılamaz, ama alttaki liste değişirse görünüm de değişir: “b” eklenince salt [a, b] olur. Notun programında ayrıca List.copyOf(liste) (Java 10+) ile bağımsız bir kopya alınmıştır. Sonra listeye “x” eklenir; görünüm bunu gösterir, kopya ise [a, b] olarak kalır. Sınıf içindeki bir listeyi dışarıya “yalnızca okunsun” diye vermek için görünüm, gerçekten sabit bir liste için List.of ya da List.copyOf kullanılır. Değiştirilemez koleksiyonlar hash anahtarları ve sabitler için de güvenli seçimlerdir.

5.10Örnek problemler

public class Fibonacci {
    public static int fibonacci(int sayi) {
        List<Integer> liste = new ArrayList<>();
        liste.add(0);
        liste.add(1);
        for (int i = 2; i < sayi + 1; i++) {
            liste.add(liste.get(i - 2) + liste.get(i - 1));
        }
        return liste.get(sayi);
    }
    public static void main(String[] args) {
        int sonuc = fibonacci(10);
        System.out.println(sonuc);
    }
}

Liste 0 ve 1 ile başlar. Döngü i = 2'den i = 10'a kadar dokuz kez döner ve her turda son iki öğenin toplamını ekler. fibonacci(10) dönerken listede 11 öğe vardır (indis 0…10): [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]. Son üçü 21, 34, 55'tir ve program 55 yazar. fibonacci(1)'de i = 2 için 2 < 2 yanlıştır ve döngü hiç dönmez; liste.get(1) = 1 döner. Liste gerçekten gerekli değildir: yalnızca son iki değeri tutan iki değişken yeterlidir ve bellek O(n)'den O(1)'e iner. Notun programı ek çağrılarla bir sınırı da gösterir:

import java.util.*;
public class Fibonacci {
    public static int fibonacci(int sayi) {
        List<Integer> liste = new ArrayList<>();
        liste.add(0);
        liste.add(1);
        for (int i = 2; i < sayi + 1; i++) {
            liste.add(liste.get(i - 2) + liste.get(i - 1));
        }
        return liste.get(sayi);
    }
    public static void main(String[] args) {
        int sonuc = fibonacci(10);
        System.out.println(sonuc);
        System.out.println(fibonacci(1) + " " + fibonacci(0) + " " + fibonacci(46));
        System.out.println(fibonacci(47));
    }
}

55
1 0 1836311903
-1323752223

fibonacci(46) = 1 836 311 903 int'e sığan son Fibonacci sayısıdır. 47'nci terim int sınırını aşar ve taşma yüzünden negatif bir sayı çıkar. Koleksiyon içindeki Integer'lar da ilkel int'in sınırlarına bağlıdır; daha büyük değerler için Long ya da BigInteger kullanılır.

public class TekrarSiz {
    static List<String> tekrarSiz(List<String> giris) {
        Set<String> gorulen = new LinkedHashSet<>(giris);
        return new ArrayList<>(gorulen);
    }

    public static void main(String[] args) {
        List<String> l = Arrays.asList("b", "a", "b", "c", "a");
        System.out.println(tekrarSiz(l));
    }
}

[b, a, c]
[a, b, c] [a, b, c]

new LinkedHashSet<>(giris) listedeki öğeleri sırayla kümeye ekler; tekrarlar atılır, ilk görülme sırası korunur. Sonuç [b, a, c]'dir. TreeSet alfabetik sıra verirdi: [a, b, c]. HashSet ise sıra garanti etmez. Programın ikinci satırında HashSet'in sonucu da [a, b, c] çıkmıştır; tek harfli dizgilerin hash kodları ardışık sayılar olduğu için kovalar alfabetik sıraya denk gelmiştir. Bu bir tesadüftür ve güvenilmez. Metodun maliyeti O(n)'dir: her öğe için bir ortalama O(1) ekleme.

static boolean dengeliMi(String ifade) {
    Deque<Character> yigin = new ArrayDeque<>();
    for (char c : ifade.toCharArray()) {
        if (c == '(' || c == '[') {
            yigin.push(c);
        } else if (c == ')' || c == ']') {
            if (yigin.isEmpty()) return false;
            char ac = yigin.pop();
            if (c == ')' && ac != '(') return false;
            if (c == ']' && ac != '[') return false;
        }
    }
    return yigin.isEmpty();
}

Açılan parantez yığına itilir. Kapanan parantez gelince yığının üstündeki açılan parantez çıkarılır ve türü karşılaştırılır. Yığın boşsa ya da tür uymuyorsa ifade dengesiz demektir. Sonda yığın boş değilse kapanmamış parantez kalmıştır. “(a[b]c)”'de ] gelince üstte [, ) gelince üstte ( vardır ve sonda yığın boştur: true. “(a[b)c]”'de ) gelince üstte [ vardır: false. “((”'de sonda yığında iki parantez kalır: false. Notun programı üç ek ifadeyi de dener (“())”, boş dizgi ve “[(x)](y)”):

true false false false true true 

Yığın kullanılmasının nedeni, son açılan parantezin ilk kapanması gerekmesidir. Bu tam olarak LIFO davranışıdır. Yığın Stack değil ArrayDeque olarak seçilmiştir. Metot ifadeyi bir kez tarar ve her karakter için O(1) iş yapar; toplam maliyet O(n)'dir.

Deque<Integer> d = new ArrayDeque<>();
d.offerLast(1);
d.offerFirst(2);
d.offerLast(3);
d.push(4);
System.out.println(d);
System.out.println(d.pollLast() + d.pop());
System.out.println(d);

Map<String, Integer> m = new TreeMap<>();
m.put("b", 1);
m.put("a", 2);
m.put("b", 3);
Set<Integer> s = new TreeSet<>(m.values());
s.add(2);
System.out.println(m + " " + s + " " + m.size());

[4, 2, 1, 3]
7
[2, 1]
{a=2, b=3} [2, 3] 2

Deque şöyle değişir: 1 → [1]; başa 2 → [2, 1]; sona 3 → [2, 1, 3]; push(4) başa → [4, 2, 1, 3]. pollLast() 3'ü, pop() 4'ü döndürür. İki Integer + ile toplanır, çünkü ifadede dizgi yoktur: 7. Kalan deque [2, 1]'dir. İkinci parçada "b" ikinci put ile 3 olur; eşleme {a=2, b=3}'tür. Değerlerden kurulan küme [2, 3]'tür. s.add(2) tekrar olduğu için eklenmez ve eşlemenin boyutu 2'dir.

static String enSikKelime(String[] kelimeler) {
    Map<String, Integer> sayac = new HashMap<>();
    for (String k : kelimeler) {
        sayac.put(k, sayac.getOrDefault(k, 0) + 1);
    }
    String enIyi = null;
    int enFazla = 0;
    for (Map.Entry<String, Integer> g : sayac.entrySet()) {
        if (g.getValue() > enFazla) {
            enFazla = g.getValue();
            enIyi = g.getKey();
        }
    }
    return enIyi;
}

su
null

İlk döngü kelimeleri getOrDefault ile sayar. İkinci döngü entrySet üzerinde gezer ve en büyük sayıyı tutan kelimeyi saklar. “su, çay, su, kahve, su, çay” için su (3) döner. Boş dizide hiçbir kelime yoktur ve metot null döndürür; çağıran bu durumu denetlemelidir. Eşit sayıda geçen iki kelime varsa hangisinin döneceği HashMap'in gezinme sırasına bağlıdır, yani belirsizdir. Maliyet O(n)'dir.

Map<String, List<Integer>> notlar = new TreeMap<>();
notlar.put("Ali", new ArrayList<>());
notlar.get("Ali").add(80);
notlar.get("Ali").add(90);
notlar.put("Banu", new ArrayList<>(Arrays.asList(70)));
for (Map.Entry<String, List<Integer>> g : notlar.entrySet()) {
    int toplam = 0;
    for (int n : g.getValue()) {
        toplam += n;
    }
    System.out.println(g.getKey() + " ort: " + toplam / g.getValue().size());
}

Ali ort: 85
Banu ort: 70
{Ali=[80, 90]}

Eşlemenin değeri bir listedir. notlar.get("Ali") o listeyi döndürür ve .add(80) doğrudan o listeye ekler; eşlemeye yeniden put yapmak gerekmez. Ortalama tam sayı bölmesiyle hesaplanır: 170 / 2 = 85. Notun programının son satırı Java 8'deki computeIfAbsent kalıbını gösterir. Bu metot anahtar yoksa yeni bir liste oluşturup ekler, varsa var olanı döndürür; “önce put et, sonra get et” iki adımı tek çağrıya iner.

Sunumdaki ikinci alıştırma, loto çekilişini shuffle kullanmadan bir Random ve bir TreeSet ile yazar:

Random r = new Random();
Set<Integer> cekilen = new TreeSet<>();
while (cekilen.size() < 6) {
    cekilen.add(r.nextInt(49) + 1);  // 1 … 49
}
System.out.println(cekilen);

[1, 32, 37, 40, 43, 45]

Küme tekrarı kendisi engeller. Aynı sayı ikinci kez gelirse add onu eklemez ve döngü bir tur daha döner. TreeSet sayıları sıralı tutar. Çıktı her çalıştırmada farklıdır. Bu yöntemde döngünün kaç kez döneceği rastgeledir, ama 49 sayıdan 6'sı seçilirken tekrar olasılığı küçük olduğu için birkaç fazla turla biter.

5.11Sık yapılan hatalar

Bu kesim, koleksiyonlarla çalışırken en sık görülen hataları gerçek derleyici ve çalışma anı iletileriyle birlikte toplar.

IlkelTip.java:4: error: unexpected type
        List<int> notlar = new ArrayList<>();
             ^
  required: reference
  found:    int
1 error

YanlisTip.java:5: error: incompatible types: int cannot be converted to String
        isimler.add(42);
                    ^
Note: Some messages have been simplified; recompile with -Xdiags:verbose to get full output
1 error

List<Integer> liste = new ArrayList<>();
Collections.addAll(liste, 10, 20, 30);
liste.remove(1);                   // indeks 1
System.out.println(liste);
liste.remove(Integer.valueOf(10)); // değer 10
System.out.println(liste);

List<Integer> a = new ArrayList<>();
Collections.addAll(a, 1000, 1000);
System.out.println(a.get(0) == a.get(1));
System.out.println(a.get(0).equals(a.get(1)));

[10, 30]
[30]
false
true
true

Çıktının ilk iki satırı remove örneğine, sonraki iki satırı 1000 ile yapılan karşılaştırmaya aittir. Son satır notun programına eklenen 100 denemesidir: aynı karşılaştırma önbellek aralığında true verir.

[9, 2, 3]
Exception in thread "main" java.lang.UnsupportedOperationException

List<String> l = new ArrayList<>();
Collections.addAll(l, "a", "b", "c");
System.out.println(l.get(3));

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 3 out of bounds for length 3

List<String> adlar = new ArrayList<>();
Collections.addAll(adlar,
        "Zeynep", "Çağla", "Can", "Ömer");
Collections.sort(adlar);
System.out.println(adlar);
Locale tr = Locale.forLanguageTag("tr-TR");
Collections.sort(adlar, Collator.getInstance(tr));
System.out.println(adlar);

[Can, Zeynep, Çağla, Ömer]
[Can, Çağla, Ömer, Zeynep]
[Ilgaz, irmik, ufuk, üzüm, İzmir, ılık] [Ilgaz, ılık, irmik, İzmir, ufuk, üzüm]

İlk iki satır sunumdaki çıktıdır. Notun programına eklenen üçüncü satır sorunun boyutunu gösterir. Doğal sırada büyük “I” küçük harflerden önce, “İ” ve “ı” ise en sona düşer. Türkçe Collator ile sıra Ilgaz, ılık, irmik, İzmir, ufuk, üzüm olur. Bu sıralayıcı büyük-küçük harf farkını ikincil sayar; “ı” ile “i” ayrı harflerdir.

5.12Özet

• Koleksiyon Çerçevesi üç unsurdan oluşur: arayüzler (ne yapılır), gerçeklemeler (nasıl yapılır) ve Collections sınıfındaki algoritmalar. Iterable → Collection → List/Queue/Set hiyerarşisinin yanında Map ayrı bir daldır ve Iterable değildir.
• Değişken ve parametre arayüz tipinde tanımlanır; böylece gerçekleme yalnız new satırında değişir.
• Jenerik tipler yanlış tipi derleme zamanında yakalar. Tip argümanı referans tipidir; ilkel değerler otomatik kutulama ve kutudan çıkarma ile sarmalayıcılara dönüşür. null'ı kutudan çıkarmak NullPointerException fırlatır.
• ArrayList dinamik dizidir: get/set O(1), sona ekleme amortize O(1), ortaya ekleme ve silme O(n). Kapasite dolunca yaklaşık 1,5 katına büyür; kapasite size() değildir.
• LinkedList çift yönlü bağlı listedir: uçlarda O(1), get(i) O(n). Çoğu durumda ArrayList daha iyi seçimdir.
• Vector ve Stack eski ve senkronizedir. Yığın ve kuyruk için ArrayDeque kullanılır; push/pop/peek baş uçta, offer sonda, poll baştadır.
• Queue işlemlerinin iki biçimi vardır: add/remove/element istisna fırlatır, offer/poll/peek false/null döndürür.
• PriorityQueue ikili yığındır: add/poll O(log n), peek O(1). println(pq) iç diziyi yazar ve sıralı değildir; öğeler Comparable olmalı ya da bir Comparator verilmelidir.
• HashSet/HashMap hash tablosudur: kova hashCode'dan hesaplanır, kovada equals ile karşılaştırılır; ortalama O(1), sıra yoktur. LinkedHash… eklenme sırasını korur, Tree… kırmızı-siyah ağaçla sıralı tutar ve O(log n)'dir.
• Eşit nesnelerin hash kodları eşit olmalıdır; equals'ı geçersiz kılan sınıf hashCode'u da geçersiz kılar. Hash'li koleksiyondaki nesnenin bu alanları değiştirilmez.
• TreeSet/TreeMap aralık sorguları sunar; kural “başlangıç dahil, bitiş hariç”tir. HashMap'te put eski değeri döndürür, olmayan anahtar için get null döndürür; Hashtable null kabul etmez.
• Yineleyici for-each'in arkasındaki mekanizmadır. Gezinirken silme it.remove() ya da removeIf ile yapılır; listenin kendi remove'u modCount'u değiştirir ve ConcurrentModificationException'a yol açar.
• Collections.sort kararlı TimSort'tur (O(n log n)). Doğal sıra Comparable.compareTo ile, başka sıralar Comparator ile tanımlanır; karşılaştırmada çıkarma değil Integer.compare kullanılır. shuffle Fisher–Yates'tir; binarySearch sıralı listede O(log n) çalışır ve bulamazsa −(ekleme noktası) − 1 döndürür.
• Akış bir işlem hattıdır. Hatta bir kaynak, tembel ara işlemler (filter, map, sorted) ve hattı çalıştıran uç işlem (collect, reduce, count) bulunur. Öğeler hattan tek tek geçer; akış tek kullanımlıktır; lambdalar yan etkisiz olmalıdır, özellikle paralel akışlarda.
• List.of/Set.of/Map.of değiştirilemez koleksiyon, Collections.unmodifiableList salt okunur görünüm, List.copyOf bağımsız değiştirilemez kopya üretir.

5.13Kavram listesi

Terimlerin İngilizce karşılıkları ve öteki bölümlerdeki kullanımları terim sözlüğünde bulunur.

• koleksiyon collection
• Koleksiyon Çerçevesi Collections Framework
• jenerikler generics
• tip güvenliği type safety
• sarmalayıcı sınıf wrapper class
• otomatik kutulama / kutudan çıkarma autoboxing / unboxing
• arayüz / gerçekleme interface / implementation
• liste list
• dinamik dizi dynamic array
• bağlı liste linked list
• indis index
• yığın stack
• kuyruk queue
• öncelikli kuyruk priority queue
• çift uçlu kuyruk deque
• küme set
• hash / hash tablosu hashing / hash table
• hash kodu hash code
• eşleme map
• yineleyici iterator
• doğal sıra natural ordering
• karşılaştırıcı comparator
• anonim sınıf anonymous class
• lambda ifadesi lambda expression
• karıştırma shuffle
• ikili arama binary search
• değiştirilemez immutable
• iş parçacığı güvenliği thread safety

5.14Kendini Dene

1. List<Integer> l = new ArrayList<>(Arrays.asList(5, 6, 7)); listesine sırayla l.add(0, 4), l.remove(Integer.valueOf(6)), l.remove(2) ve l.add(l.size(), 8) uygulanıyor. Liste ve l.indexOf(8) nedir?

   Cevap

   [4, 5, 6, 7] → değer 6 silinir: [4, 5, 7] → indis 2 (7) silinir: [4, 5] → sona 8: [4, 5, 8]. indexOf(8) 2'dir.

2. Boş bir Deque<String> d = new ArrayDeque<>() için sırayla push("x"), offer("y"), push("z"), addLast("w") çağrılıyor. Sonra String a = d.pop(); String b = d.pollLast(); çalışıyor. d ve a + b nedir?

   Cevap

   [x] → [x, y] → [z, x, y] → [z, x, y, w]. pop baştaki z'yi, pollLast sondaki w'yi alır. d = [x, y], a + b = "zw".

3. new PriorityQueue<Integer>(Collections.reverseOrder()) kuyruğuna 7, 2, 9, 4 ekleniyor. İki poll()'un sonucu ve kalan boyut nedir?

   Cevap

   Ters sırada en büyük önce çıkar: 9, sonra 7. Kuyrukta 2 öğe (2 ve 4) kalır.

4. "kelebek" dizgisinin karakterleri bir TreeMap<Character, Integer>'te merge(c, 1, Integer::sum) ile sayılıyor. Eşleme nasıl yazdırılır?

   Cevap

   {b=1, e=3, k=2, l=1}. Harfler k-e-l-e-b-e-k'tir: e üç, k iki, l ve b birer kez geçer; TreeMap anahtarları sıralı yazar.

5. TreeSet 15, 5, 25, 10, 20 öğelerini içeriyor. headSet(15), subSet(10, 21) ve tailSet(26) nedir?

   Cevap

   [5, 10] (15 hariç), [10, 15, 20] (10 dahil, 21 hariç) ve [] (26 ve üstünde öğe yok).

6. Arrays.asList("ayva", "kiraz", "erik", "dut", "armut") listesinde stream().filter(x -> x.length() > 3).map(x -> x.substring(0, 2)).sorted().collect(Collectors.toList()) ne üretir? mapToInt(String::length).sum() kaçtır?

   Cevap

   “dut” elenir; kalanların ilk iki harfi ay, ki, er, ar'dır ve sıralanınca [ar, ay, er, ki] olur. Uzunluk toplamı 4 + 5 + 4 + 3 + 5 = 21'dir.

7. [2, 3, 5, 8] listesinde for-each içinde if (x == 5) sayilar.remove(x); çalışıyor. İstisna fırlatılır mı? Liste ne olur?

   Cevap

   Fırlatılmaz. 5 (indis 2) silinince size 3 olur; cursor zaten 3'tür ve hasNext() false döner. Döngü sessizce biter ve 8 hiç denetlenmez. Liste [2, 3, 8]'dir. Kod hatalıdır, ama bu veriyle bunu belli etmez.

8. Collections.binarySearch(Arrays.asList(2, 4, 6, 8, 10), 9) ne döndürür?

   Cevap

   9 yoktur; 8'den sonra, 10'dan önce, yani indis 4'e girmelidir. Dönüş −(4) − 1 = −5'tir.

9. Bir Ogrenci sınıfı yalnızca equals'ı geçersiz kılmıştır. Aynı alanlı iki nesne hem bir ArrayList'e hem bir HashSet'e ekleniyor ve ikinci nesneyle contains soruluyor. Sonuçlar neden farklıdır?

   Cevap

   ArrayList.contains yalnızca equals kullanır ve true döner. HashSet ise önce hashCode ile kovayı bulur. Object'ten gelen hash kodları farklı olduğu için iki nesne farklı kovalara düşer; küme iki öğe tutar ve contains false döner. Çözüm hashCode'u aynı alanlardan yazmaktır.

5.15İleri okuma

• Oracle, The Java Tutorials, “Collections” ve “Aggregate Operations” bölümleri: arayüzleri, gerçeklemeleri, algoritmaları ve akış hatlarını resmî örneklerle adım adım anlatır.
• J. Bloch, Effective Java (3. baskı, Addison-Wesley, 2018), Madde 11, 14, 45–48 ve 64. hashCode, Comparable, akışların ölçülü ve yan etkisiz kullanımı ve nesnelere arayüzleriyle başvurma üzerine kısa, gerekçeli kurallar verir.
• M. Naftalin ve P. Wadler, Java Generics and Collections (O'Reilly): jeneriklerin ve koleksiyon sınıflarının iç yapısını ve tasarım gerekçelerini ayrıntılı inceler.
• C. S. Horstmann, Core Java, Volume I: Fundamentals (12. baskı, 2022), Bölüm 9: koleksiyonları hash tablosu, ağaç ve görünümlerin işleyişiyle birlikte anlatır.

5.16Kaynaklar

• Oracle, The Java Tutorials: Collections (Interfaces, Implementations, Algorithms) ve Generics.
• Oracle, Java SE 21 API Documentation: java.util paketi (Collection, List, Map, Collections…) ve java.util.stream.
• J. Gosling ve diğ., The Java Language Specification, Java SE 21 Edition (4.5 Parameterized Types, 5.1.7 Boxing Conversion, 14.14.2 Enhanced for).
• P. Deitel ve H. Deitel, Java: How to Program, 11. baskı, Pearson (Bölüm 16: Generic Collections).
• K. Sierra ve B. Bates, Head First Java, 3. baskı, O'Reilly (Bölüm 11: Data Structures).
• C. S. Horstmann, Core Java, Volume I: Fundamentals, 12. baskı, Pearson (Bölüm 9: Collections).
• M. Naftalin ve P. Wadler, Java Generics and Collections, O'Reilly.
• J. Bloch, Effective Java, 3. baskı, Addison-Wesley (Madde 11: equals ile birlikte hashCode; Madde 64: nesnelere arayüzleriyle başvurmak).