Collections internals: ArrayList ve HashMap

01 Collections Framework genel görünümü

Iterable
   └── Collection
        ├── List  → ArrayList, LinkedList
        ├── Set   → HashSet, TreeSet
        └── Queue / Deque

Map
 ├── HashMap
 ├── LinkedHashMap
 ├── TreeMap
 └── ConcurrentHashMap

Map, Collection interface’ini genişletmez; tekil eleman yerine key-value ilişkisi saklar. Bu derste ArrayList’i dinamik bir Object[], HashMap’i bucket dizisi ve node zincirleri/ağaçları olarak düşüneceğiz.

Genel sınıflandırmayı Oracle’ın Java Collections Framework dokümanında görebilirsin.

02 ArrayList içeride nasıl çalışır?

JAVAList<String> names = new ArrayList<>();

names.add("Ali");
names.add("Ayşe");
names.add("Mehmet");

İçeride kavramsal olarak iki temel alan bulunur:

JAVAObject[] elementData;
int size;

index      0         1          2        3      4
        +-------+--------+----------+------+------+ 
        | "Ali" | "Ayşe" | "Mehmet" | null | null |
        +-------+--------+----------+------+------+

size     = 3   → gerçek eleman sayısı
capacity = 5   → backing array uzunluğu

Generics type erasure’a uğradığı için ArrayList<String>ve ArrayList<Integer> aynı implementasyonu kullanır. Compiler, get() sonucundaki gerekli cast’i yönetir.

JAVAString name = (String) elementData[0];

03 Boş liste, ilk kapasite ve büyüme

Güncel OpenJDK’da varsayılan constructor hemen on elemanlık array oluşturmaz; paylaşılan boş bir array kullanır. İlk eleman eklendiğinde varsayılan kapasite genellikle 10 olur.

Başlangıç: []

İlk add sonrası:
[A, null, null, null, null, null, null, null, null, null]

Array boyutu değiştirilemediği için dolduğunda:

1. Daha büyük bir array oluşturulur.
2. Eski referanslar yeni array’e kopyalanır.
3. elementData yeni array’i göstermeye başlar.
4. Erişilemeyen eski array daha sonra GC tarafından temizlenir.

Güncel implementasyon tercih edilen büyümeyi yaklaşık eski kapasitenin yarısı kadar yapar: oldCapacity >> 1.

10 → 15 → 22 → 33 → 49 ...

04 add() ve amortized O(1)

JAVAif (size == elementData.length) {
    grow();
}

elementData[size] = value;
size++;

Yer varsa sona eklemek O(1), resize sırasında bütün referansları kopyalamak O(n) maliyetlidir. Resize her eklemede yapılmadığından uzun bir ekleme dizisinin eleman başına ortalama maliyeti sabite yaklaşır.

Başlangıç kapasitesi vermek

JAVAList<User> users = new ArrayList<>(100_000);

ArrayList<User> otherUsers = new ArrayList<>();
otherUsers.ensureCapacity(100_000);

Bu çağrılar listeye eleman koymaz; yalnızca tekrar tekrar büyütme ve kopyalama ihtiyacını azaltır. Gereğinden büyük kapasite ise boş yere bellek tüketir.

05 Index erişimi, araya ekleme ve silme

get(index) ve set(index, value), bounds kontrolünden sonra doğrudan array hücresine gider; ikisi de O(1)’dir.

JAVAif (index < 0 || index >= size) {
    throw new IndexOutOfBoundsException();
}

return (String) elementData[index];

Araya eklemede sonraki referanslar sağa, silmede sola kaydırılır.System.arraycopy() optimize olsa da maliyet taşınan eleman sayısıyla orantılıdır.

add(1, X)
[A][B][C][D][ ]  →  [A][X][B][C][D]

remove(1)
[A][B][C][D]     →  [A][C][D][null]

Silme sonunda boşalan hücre null yapılır; aksi halde liste artık kullanmadığı nesneyi GC için erişilebilir tutardı. Son elemanı silmek kaydırma gerektirmediği için daha ucuzdur.

Integer listesinde remove tuzağı

JAVAList<Integer> numbers = new ArrayList<>(List.of(10, 20, 30));

numbers.remove(1);                  // index 1'deki 20 silinir
numbers.remove(Integer.valueOf(1)); // 1 değeri silinir

06 Arama ve ArrayList karmaşıklıkları

ArrayList bir hash tablosu değildir. contains,indexOf ve değere göre remove elemanları baştan sona Objects.equals ile kontrol eder.

Çok sık üyelik kontrolü yapacaksan HashSet daha uygun olabilir. Genel amaçlı List implementasyonu olarak ise çoğu zaman ilk tercih ArrayList’tir.

07 Bellek ve trimToSize()

JAVAArrayList<String> values = new ArrayList<>(1_000_000);

values.clear();
values.trimToSize();

clear() size’ı sıfırlar fakat büyük backing array’i hemen küçültmek zorunda değildir. trimToSize() capacity’yi size’a yaklaştırır. Bunu sürekli çağırmak sonraki büyümelerde tekrar allocation ve kopyalama maliyeti yaratır; uzun süre yaşayacak ve artık büyümeyecek büyük listelerde anlamlıdır.

08 Thread safety, fail-fast iterator ve modCount

ArrayList thread-safe değildir. Birden fazla thread aynı listeyi kullanıyor ve en az biri yapısal değişiklik yapıyorsa koordinasyon veya senaryoya uygun concurrent collection gerekir.

JAVAList<String> synchronizedValues =
        Collections.synchronizedList(new ArrayList<>());

List<String> snapshotFriendly =
        new CopyOnWriteArrayList<>();

Iterator, oluşturulduğunda modCount değeriniexpectedModCount olarak kaydeder. Dolaşırken uyuşmazlık görürse genellikle ConcurrentModificationException üretir.

JAVAIterator<String> iterator = values.iterator();

while (iterator.hasNext()) {
    String value = iterator.next();
    if (value.equals("B")) {
        iterator.remove();
    }
}

values.removeIf(value -> value.equals("B"));

09 HashMap içeride nasıl çalışır?

JAVAMap<String, Integer> ages = new HashMap<>();

ages.put("Ali", 29);
ages.put("Ayşe", 28);
ages.put("Mehmet", 31);

Temel yapı kavramsal olarak şöyledir:

JAVANode<K, V>[] table;
int size;
int threshold;
float loadFactor;

static class Node<K, V> {
    int hash;
    K key;
    V value;
    Node<K, V> next;
}

table

index 0 → null
index 1 → Node(Ali, 29) → Node(Ayşe, 28)
index 2 → null
index 3 → Node(Mehmet, 31)
index 4 → null

Array’in her hücresine bucket veya bin denir.

10 put() adım adım

1. key.hashCode() hesaplanır.
2. Hash’in yüksek bitleri dağıtıma katılır.
3. Bucket index’i hesaplanır.
4. Bucket boşsa yeni node yerleştirilir.
5. Doluysa aynı key hash ve equals() ile aranır.
6. Aynı key varsa value değiştirilir; farklı key collision yapısına eklenir.
7. Size threshold’u aşarsa resize yapılır.

Bu yapının güncel ayrıntıları OpenJDK HashMap.java kaynağında görülebilir.

11 Hash spreading ve bucket index’i

JAVAint hashCode = key.hashCode();
int hash = hashCode ^ (hashCode >>> 16);
int index = (capacity - 1) & hash;

Capacity ikinin kuvveti olarak tutulur: 16, 32, 64, 128… Bu sayede modulo yerine bit maskesi kullanılabilir. Capacity 16 ikencapacity - 1 değeri ikilik sistemde 0000 1111dir; son dört bit bucket’ı seçer. Spreading, yüksek bitlerin de bu seçimde etkili olmasını sağlar.

12 Collision nedir?

Farklı key’ler aynı bucket’a düşebilir; bu normaldir.

table[5]
   │
   ▼
[hash, "Ali", 29]
   │ next
   ▼
[hash, "Ayşe", 28]
   │ next
   ▼
 null

JAVAif (node.hash == hash &&
    (node.key == key || key.equals(node.key))) {
    // Aynı key
}

13 get() ve HashMap karmaşıklıkları

get(key) hash’i hesaplar, bucket’ı bulur ve yalnızca o bucket içinde hash ile equals eşleşmesini arar. İyi dağılımda bucket’ların çoğu boş veya çok kısadır.

Temel performans iyi hashCode() dağılımına bağlıdır. API beklentisi için Java 25 HashMap dokümanına bakabilirsin.

14 equals() ve hashCode() key sözleşmesi

JAVApublic record UserId(long value) {}

Map<UserId, User> users = new HashMap<>();

Record otomatik olarak uyumlu equals/hashCode ürettiği için iyi bir key adayıdır. Bununla birlikte record component’larının da fiilen immutable olması gerekir.

15 Mutable key felaketi

JAVAMap<UserKey, String> map = new HashMap<>();

UserKey key = new UserKey("ali");
map.put(key, "data");

key.setUsername("ayse");

System.out.println(map.get(key));
// null olabilir

put sırasında:
hash("ali")  → bucket 3

key değiştirildi:
hash("ayse") → bucket 11

get bucket 11'e bakar;
node hâlâ bucket 3'tedir.

16 Capacity, load factor ve threshold

Güncel OpenJDK varsayımları:

initial capacity = 16
load factor      = 0.75
threshold        = capacity × load factor
                 = 16 × 0.75 = 12

Backing table genellikle ilk put() işlemine kadar tembel oluşturulur. Düşük load factor daha fazla boş bucket ve daha az collision; yüksek load factor daha az array belleği ve daha fazla collision ihtimali getirir. 0.75 genel amaçlı zaman-bellek dengesidir.

17 HashMap resize

capacity:  16 → 32 → 64 → 128
threshold: 12 → 24 → 48 → 96

Güncel OpenJDK, power-of-two kapasiteden yararlanır. Bir node eski index’inde kalır veya oldIndex + oldCapacity konumuna taşınır; karar (hash & oldCapacity) == 0 testiyle verilebilir.

JAVAHashMap<String, User> users =
        HashMap.newHashMap(100_000);

Java 19+ factory’si beklenen mapping sayısına göre kapasiteyi hesaplar. Büyük map’lerde gereksiz resize’ları azaltır; fakat aşırı büyük kapasite hem belleği hem de iteration maliyetini artırır.

18 Uzun bucket’lar ve treeification

Linked list:
A → B → C → D → E → F → G → H

Red-black tree:
         D
       /         B     F
     /    /     A   C E   G
                               H

Bucket sekiz node’a ulaştığında her zaman hemen ağaca dönüşmez; table capacity 64’ten küçükse önce resize tercih edilebilir. Çünkü collision’ın nedeni küçük tablo olabilir. Bu eşikler public API değil, güncel OpenJDK implementasyon ayrıntısıdır.

19 Null, aynı key ve iteration sırası

JAVAmap.put(null, "A");
map.put(null, "B");         // aynı key'in value'su değişir

map.put("first", null);

if (map.get("key") == null) {
    boolean reallyExists = map.containsKey("key");
}

HashMap bir null key ve birden fazla null value kabul eder. Aynı key ile ikinci put node eklemez, value’yu değiştirir ve eski value’yu döndürür. ConcurrentHashMap ise null key/value kabul etmez.

HashMap insertion order garantisi vermez. Ekleme sırası gerekiyorsaLinkedHashMap, key sırası gerekiyorsa TreeMapkullan. HashMap iteration maliyeti yalnızca size değil,capacity + size ile ilişkilidir.

20 HashMap thread-safe değildir

JAVAMap<String, Integer> counts = new ConcurrentHashMap<>();

counts.putIfAbsent(key, value);
counts.computeIfAbsent(key, ignored -> createValue());

Şu kontrol ve yazma çifti atomik değildir:

JAVAif (!map.containsKey(key)) {
    map.put(key, value);
}

İki thread aynı anda kontrolü geçebilir. Concurrent kullanımdaConcurrentHashMap ve onun atomik operasyonlarının garantilerine bakılmalıdır. Collections.synchronizedMap()mümkün olsa da daha kaba bir koordinasyon modelidir.

21 HashSet aslında ne kullanıyor?

HashSet içeride bir HashMap kullanır. Set elemanı map’in key’i, ortak dummy nesne ise value olur.

HashSet element → HashMap key
dummy object    → HashMap value

add / contains / remove
→ HashMap'in key operasyonları

Bu yüzden HashSet elemanları da doğru ve stabil equals/hashCode uygulamasına ihtiyaç duyar.

22 Sık karıştırılan liste üretimleri

JAVAString[] array = {"A", "B"};
List<String> fixed = Arrays.asList(array);

fixed.set(0, "X"); // geçerli
fixed.add("C");    // UnsupportedOperationException

List<String> independent =
        new ArrayList<>(Arrays.asList(array));

23 Hangisini ne zaman seçmelisin?