Hash Table

// Demo Hash Table: implementasi HashMap dengan chaining untuk collision.

// === Hash Table dengan chaining ===
class HashTable<K, V>(private val kapasitas: Int = 16) {
    private val bucket: Array<MutableList<Pair<K, V>>> = Array(kapasitas) { mutableListOf() }
    private var size = 0

    private fun hash(key: K): Int {
        val h = key.hashCode()
        return ((h and 0x7FFFFFFF) % kapasitas)
    }

    // Hitung load factor untuk menentukan kapan harus rehash
    fun loadFactor(): Double = size.toDouble() / kapasitas

    fun put(key: K, value: V): V? {
        val idx = hash(key)
        val chain = bucket[idx]
        for (i in chain.indices) {
            if (chain[i].first == key) {
                val old = chain[i].second
                chain[i] = key to value
                return old
            }
        }
        chain.add(key to value)
        size++
        return null
    }

    fun get(key: K): V? {
        val idx = hash(key)
        for ((k, v) in bucket[idx]) {
            if (k == key) return v
        }
        return null
    }

    fun remove(key: K): V? {
        val idx = hash(key)
        val chain = bucket[idx]
        for (i in chain.indices) {
            if (chain[i].first == key) {
                val removed = chain[i].second
                chain.removeAt(i)
                size--
                return removed
            }
        }
        return null
    }

    fun size(): Int = size

    fun distribusi(): List<Int> = bucket.map { it.size }

    fun entries(): List<Pair<K, V>> = bucket.flatMap { it.toList() }
}

// === Hash Table dengan open addressing (linear probing) ===
class HashTableOpenAddressing<K, V>(private val kapasitas: Int = 16) {
    private val keys: Array<Any?> = arrayOfNulls(kapasitas)
    private val values: Array<Any?> = arrayOfNulls(kapasitas)
    private var size = 0

    private fun hash(key: K): Int = ((key.hashCode() and 0x7FFFFFFF) % kapasitas)

    fun put(key: K, value: V) {
        var idx = hash(key)
        while (keys[idx] != null && keys[idx] != key) {
            idx = (idx + 1) % kapasitas
        }
        if (keys[idx] == null) size++
        keys[idx] = key
        values[idx] = value
    }

    @Suppress("UNCHECKED_CAST")
    fun get(key: K): V? {
        var idx = hash(key)
        var iterasi = 0
        while (keys[idx] != null && iterasi < kapasitas) {
            if (keys[idx] == key) return values[idx] as V?
            idx = (idx + 1) % kapasitas
            iterasi++
        }
        return null
    }

    fun size(): Int = size
}

fun main() {
    println("=== Demo Hash Table ===")

    println("--- Hash Table dengan chaining ---")
    val ht = HashTable<String, Int>()
    ht.put("Budi", 25)
    ht.put("Siti", 30)
    ht.put("Dewi", 28)
    ht.put("Andi", 35)
    ht.put("Rina", 22)
    ht.put("Budi", 26)  // overwrite

    println("Get Budi: ${ht.get("Budi")}")
    println("Get Siti: ${ht.get("Siti")}")
    println("Get Tidak Ada: ${ht.get("Tidak Ada")}")
    println("Size: ${ht.size()}")
    println("Load factor: ${"%.4f".format(ht.loadFactor())}")
    println("Distribusi bucket: ${ht.distribusi()}")
    println("Entries: ${ht.entries()}")

    println()
    println("--- Hash Table dengan open addressing ---")
    val ht2 = HashTableOpenAddressing<String, Int>(kapasitas = 8)
    listOf("apple" to 1, "banana" to 2, "cherry" to 3, "date" to 4, "elderberry" to 5).forEach {
        ht2.put(it.first, it.second)
    }
    println("Get apple: ${ht2.get("apple")}")
    println("Get date: ${ht2.get("date")}")
    println("Get fig (tidak ada): ${ht2.get("fig")}")
    println("Size: ${ht2.size()}")

    println()
    println("--- Perbandingan HashMap Kotlin vs custom ---")
    val data = (1..1000).map { "key-$it" to it }
    val t0 = System.nanoTime()
    val kotlinMap = HashMap<String, Int>()
    data.forEach { kotlinMap[it.first] = it.second }
    val t1 = System.nanoTime()
    println("HashMap Kotlin insert ${data.size} entry: ${(t1 - t0)} ns")

    val t2 = System.nanoTime()
    val customMap = HashTable<String, Int>(kapasitas = 64)
    data.forEach { customMap.put(it.first, it.second) }
    val t3 = System.nanoTime()
    println("Custom HashTable insert ${data.size} entry: ${(t3 - t2)} ns")
    println("Load factor custom: ${"%.4f".format(customMap.loadFactor())}")
}

=== Demo Hash Table ===
--- Hash Table dengan chaining ---
Get Budi: 26
Get Siti: 30
Get Tidak Ada: null
Size: 5
Load factor: 0.3125
Distribusi bucket: [0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0]
Entries: [(Andi, 35), (Dewi, 28), (Budi, 26), (Rina, 22), (Siti, 30)]

--- Hash Table dengan open addressing ---
Get apple: 1
Get date: 4
Get fig (tidak ada): null
Size: 5

--- Perbandingan HashMap Kotlin vs custom ---
HashMap Kotlin insert 1000 entry: 392992 ns
Custom HashTable insert 1000 entry: 2369677 ns
Load factor custom: 15.6250

Load factor 0.3 -> rata-rata 0.3 entry per bucket (sehat)
Load factor 0.7 -> mulai sering collision (perlu resize)
Load factor 1.0 -> rata-rata 1 entry per bucket (chaining masih OK)
Load factor 2.0 -> open addressing tidak mungkin (penuh)