Pilihan koleksi sangat memengaruhi performance. ArrayList cepat untuk random access tetapi lambat untuk insert di tengah. LinkedList kebalikannya. HashMap memberi lookup O(1) tetapi tidak menjaga urutan, sementara TreeMap menjaga urutan tetapi lookup O(log n). Pada bab ini kita akan membandingkan keempat implementasi dengan step counter, mendemokan manfaat initialCapacity, dan menyusun tabel ringkasan Big-O untuk acuan cepat.

ArrayList vs LinkedList #

ArrayList menyimpan elemen di array backing yang otomatis di-resize bila penuh. LinkedList menyimpan elemen di node terpisah dengan pointer next/prev. Perbedaan struktur ini menyebabkan perbedaan performance yang dramatis pada operasi tertentu.

OperasiArrayListLinkedList
add di akhirO(1) amortized (resize jarang)O(1) (Node baru)
get(i) randomO(1) (array index)O(n) (traverse)
insert(i) di tengahO(n) (array copy)O(1) (relink)
remove(i) di tengahO(n) (array copy)O(1) (relink)
IterationCepat (cache locality)Lambat (pointer chasing)
Memori per elemen4-8 bytes24-32 bytes (Node overhead)

Untuk mayoritas kasus, ArrayList lebih cepat karena cache locality. LinkedList hanya unggul bila sering insert/remove di tengah dan jarang random access.

HashMap vs TreeMap #

HashMap memakai hash table dengan bucket. Lookup rata-rata O(1), worst case O(n) bila banyak collision. TreeMap memakai red-black tree yang menjaga key terurut. Lookup O(log n).

KarakteristikHashMapTreeMap
Lookup rata-rataO(1)O(log n)
Iteration orderTidak terjaminSorted by key
Memori overheadTable + Entry per itemTree node per item
Null keyDiizinkan (1 null)Tidak diizinkan
Cocok untukCache, lookup cepatRange query, sorted iteration

Pilih TreeMap hanya bila perlu iterasi terurut atau range query (subMap, headMap, tailMap). Untuk kasus lain, HashMap selalu lebih cepat.

Pre-size dengan initialCapacity #

ArrayList dan HashMap mempunyai konstruktor yang menerima initialCapacity. Bila kita tahu ukuran akhir collection, set capacity awal agar tidak ada resize.

kotlin Tanpa pre-size vs dengan pre-size 
// Tanpa pre-size: ArrayList default cap = 16
val list1 = ArrayList<Int>()
for (i in 1..1000) list1.add(i)
// ArrayList akan resize ~6 kali (16 → 32 → 64 → ... → 1024)

// Dengan pre-size: kapasitas awal sudah cukup
val list2 = ArrayList<Int>(1000)
for (i in 1..1000) list2.add(i)
// Tidak ada resize, hemat 6x array copy

Untuk HashMap, aturan umum: set initialCapacity = expectedSize / 0.75 + 1 (default load factor 0.75) agar tidak terjadi rehash. Bila expected size 1000, set capacity ke 1334.

Demo Step-Counting #

Cuplikan berikut membandingkan keempat koleksi dengan step counter. Untuk random access LinkedList, simulasi menghitung ~500 langkah traversal. Untuk TreeMap, simulasi menghitung ~10 langkah (log2 1000):

kotlin 
// Demo collection performance: ArrayList vs LinkedList, HashMap vs TreeMap,
// pre-size dengan initialCapacity. Menggunakan step counter (bukan nanotime).

import java.util.TreeMap

class CollectionProfiler {
    var steps: Long = 0
    var allocations: Long = 0

    fun reset() { steps = 0; allocations = 0 }
    fun step(n: Long = 1) { steps += n }
    fun alloc(n: Long = 1) { allocations += n }
    fun report(label: String): String {
        return "  %-30s steps=%-12d allocations=%-6d".format(label, steps, allocations)
    }
}

fun main() {
    println("=== Collection Performance ===")
    println()
    println("Catatan: 'steps' = operasi internal (array copy, traversal).")
    println("         'allocations' = objek tambahan yang dibuat.")
    println()

    val profiler = CollectionProfiler()
    val N = 1000

    // === 1. Append ke ArrayList ===
    println("=== 1. ArrayList append (cap awal = 16) ===")
    profiler.reset()
    val arrayList = ArrayList<Int>(16) // default small capacity
    for (i in 1..N) {
        arrayList.add(i)
        profiler.step()
        // Setiap kali array internal full, Kotlin reallocate
        // Hitung berapa kali resize terjadi
    }
    var arrayResizes = 0
    var cap = 16
    while (cap < N) { cap *= 2; arrayResizes++ }
    profiler.alloc(arrayResizes.toLong())
    println(profiler.report("ArrayList (no presize)"))
    println("    Resize terjadi: $arrayResizes kali (array copy)")
    println()

    // === 2. ArrayList dengan initialCapacity ===
    println("=== 2. ArrayList append (pre-size = $N) ===")
    profiler.reset()
    val sizedList = ArrayList<Int>(N) // pre-size yang tepat
    for (i in 1..N) {
        sizedList.add(i)
        profiler.step()
    }
    // Tidak ada resize karena kapasitas sudah cukup
    println(profiler.report("ArrayList (presized)"))
    println("    Resize terjadi: 0 kali (kapasitas awal cukup)")
    println()

    // === 3. LinkedList append ===
    println("=== 3. LinkedList append ===")
    profiler.reset()
    val linkedList = java.util.LinkedList<Int>()
    for (i in 1..N) {
        linkedList.add(i)
        profiler.step()
        profiler.alloc() // Node object baru per append
    }
    println(profiler.report("LinkedList append"))
    println("    Alokasi: $N Node objects (overhead per elemen)")
    println()

    // === 4. Random access: ArrayList vs LinkedList ===
    println("=== 4. Random access (index 500) ===")
    profiler.reset()
    repeat(100) {
        arrayList[500]  // O(1) — direct array access
        profiler.step()
    }
    println(profiler.report("ArrayList.get(500)"))

    profiler.reset()
    repeat(100) {
        // LinkedList.get(i) harus traverse dari head
        linkedList[500]  // O(n) — traverse
        profiler.step(500) // 500 langkah traversal
    }
    println(profiler.report("LinkedList.get(500)"))
    println()

    // === 5. HashMap vs TreeMap lookup ===
    println("=== 5. HashMap vs TreeMap lookup (key='key-500') ===")
    val hashMap = HashMap<String, Int>(N)
    val treeMap = TreeMap<String, Int>()
    for (i in 1..N) {
        hashMap["key-$i"] = i
        treeMap["key-$i"] = i
    }

    profiler.reset()
    repeat(100) {
        hashMap["key-500"]  // O(1) rata-rata
        profiler.step() // 1 langkah hash lookup
    }
    println(profiler.report("HashMap.get(key-500)"))

    profiler.reset()
    repeat(100) {
        treeMap["key-500"]  // O(log n) - traverse pohon
        profiler.step(10) // ~log2(1000) ≈ 10 langkah
    }
    println(profiler.report("TreeMap.get(key-500)"))
    println()

    // === 6. Iteration: ArrayList vs LinkedList ===
    println("=== 6. Iteration (sum semua elemen) ===")
    profiler.reset()
    var sum1 = 0
    for (x in arrayList) { sum1 += x; profiler.step() }
    println(profiler.report("ArrayList.iterate"))

    profiler.reset()
    var sum2 = 0
    for (x in linkedList) { sum2 += x; profiler.step() }
    println(profiler.report("LinkedList.iterate"))
    println()

    // === 7. Tabel ringkasan ===
    println("=== 7. Ringkasan Big-O ===")
    val tabel = listOf(
        Triple("ArrayList.add", "O(1) amortized", "Resize ganda bila full"),
        Triple("ArrayList.get(i)", "O(1)", "Direct array index"),
        Triple("LinkedList.add", "O(1)", "Alokasi Node baru"),
        Triple("LinkedList.get(i)", "O(n)", "Traverse dari head"),
        Triple("HashMap.get(k)", "O(1) avg", "Hash + bucket"),
        Triple("TreeMap.get(k)", "O(log n)", "BST traversal"),
        Triple("HashMap.iterate", "O(n)", "Sequential bucket"),
        Triple("TreeMap.iterate", "O(n) in-order", "In-order traversal")
    )
    tabel.forEach { (op, bigO, keterangan) ->
        println("  %-25s %-15s %s".format(op, bigO, keterangan))
    }
    println()
    println("Sum ArrayList: $sum1, Sum LinkedList: $sum2 (sama = ${sum1 == sum2})")
}

Output yang Dihasilkan:

text 
=== Collection Performance ===

Catatan: 'steps' = operasi internal (array copy, traversal).
         'allocations' = objek tambahan yang dibuat.

=== 1. ArrayList append (cap awal = 16) ===
  ArrayList (no presize)         steps=1000         allocations=6     
    Resize terjadi: 6 kali (array copy)

=== 2. ArrayList append (pre-size = 1000) ===
  ArrayList (presized)           steps=1000         allocations=0     
    Resize terjadi: 0 kali (kapasitas awal cukup)

=== 3. LinkedList append ===
  LinkedList append              steps=1000         allocations=1000  
    Alokasi: 1000 Node objects (overhead per elemen)

=== 4. Random access (index 500) ===
  ArrayList.get(500)             steps=100          allocations=0     
  LinkedList.get(500)            steps=50000        allocations=0     

=== 5. HashMap vs TreeMap lookup (key='key-500') ===
  HashMap.get(key-500)           steps=100          allocations=0     
  TreeMap.get(key-500)           steps=1000         allocations=0     

=== 6. Iteration (sum semua elemen) ===
  ArrayList.iterate              steps=1000         allocations=0     
  LinkedList.iterate             steps=1000         allocations=0     

=== 7. Ringkasan Big-O ===
  ArrayList.add             O(1) amortized  Resize ganda bila full
  ArrayList.get(i)          O(1)            Direct array index
  LinkedList.add            O(1)            Alokasi Node baru
  LinkedList.get(i)         O(n)            Traverse dari head
  HashMap.get(k)            O(1) avg        Hash + bucket
  TreeMap.get(k)            O(log n)        BST traversal
  HashMap.iterate           O(n)            Sequential bucket
  TreeMap.iterate           O(n) in-order   In-order traversal

Sum ArrayList: 500500, Sum LinkedList: 500500 (sama = true)

Mari kita bedah hasil pengukuran di atas:

  1. ArrayList tanpa pre-size: terjadi 6 kali resize (16 → 32 → 64 → 128 → 256 → 512 → 1024). Setiap resize meng-copy seluruh elemen ke array baru, sehingga total copy adalah ~1000 + ~1000 = 2000 elemen.
  2. ArrayList dengan pre-size: tidak ada resize. Hemat 6x array copy. Bila ukuran akhir diketahui, selalu pre-size.
  3. LinkedList append: setiap add mengalokasikan satu Node object (24-32 bytes di JVM 64-bit). Untuk 1000 elemen, ada 1000 Node + array references.
  4. Random access arrayList[500]: O(1) — langsung akses array index. Untuk LinkedList, harus traverse 500 node dari head, jadi O(n).
  5. HashMap lookup: O(1) rata-rata — hash function menghasilkan index bucket, lalu cek equality. Untuk TreeMap, harus traverse pohon BST, jadi O(log n) ≈ 10 langkah untuk 1000 elemen.
  6. Iteration: kedua koleksi O(n), tetapi ArrayList lebih cepat di praktik karena cache locality (elemen bersebelahan di memori). LinkedList mengalami cache miss karena pointer chasing.

Cache Locality #

CPU modern mempunyai cache L1/L2/L3 yang berukuran kecil tetapi sangat cepat. Bila elemen yang diakses berdekatan di memori (seperti array), cache hit rate tinggi. Bila elemen tersebar (seperti linked list node), cache miss sering terjadi dan CPU menunggu data dari RAM (~100 ns).

kotlin Cache locality pada iteration 
// ArrayList: cache-friendly
for (x in arrayList) sum += x  // 1 cache line per 16 Int (64 bytes / 4 bytes)

// LinkedList: cache-unfriendly
for (x in linkedList) sum += x  // cache miss per node (data tersebar)

Untuk 1 juta elemen, perbedaan ini bisa mencapai 5-10x lipat waktu eksekusi, walaupun Big-O keduanya O(n).

Referensi Lanjutan #

  • Collections overview — ringkasan tipe koleksi Kotlin beserta kompleksitas operasi umumnya
  • Sequences — dokumentasi Sequence untuk pemrosesan lazy yang menghindari koleksi antara

Selanjutnya #

Untuk operasi chain seperti map.filter.map, koleksi List membuat intermediate list di setiap step. Bab berikutnya membahas Sequence sebagai alternatif lazy yang hemat alokasi. Materi tersebut ada di chapter Sequence Performance.