BasicHashMap.kt

import java.util.*

/**
 * A basic implementation of a hash map to demonstrate internal workings
 */
class BasicHashMap<K, V> {

    private data class Entry<K, V>(val key: K, val value: V)

    private val loadFactor = 0.75

    private var arraySize = 16

    private var numberOfEntries = 0

    private var entries: Array<LinkedList<Entry<K, V>>> = Array(arraySize) { LinkedList<Entry<K, V>>() }

    fun put(key: K, value: V) {
        numberOfEntries++

        if (numberOfEntries > arraySize * loadFactor) {
            increaseCapacity()
        }

        put(key, value, entries)
    }

    private fun put(key: K, value: V, localEntries: Array<LinkedList<Entry<K, V>>>) {
        val index = calculateHashCode(key)
        val listAtArraySlot = localEntries[index]

        val newEntry = Entry(key, value)

        // Check if the key already exists in the LinkedList entries
        val indexOfEntryInList = listAtArraySlot.indexOfFirst { it.key == key }
        if (indexOfEntryInList >= 0) {
            listAtArraySlot[indexOfEntryInList] = newEntry
        } else {
            listAtArraySlot.offer(newEntry)
        }
    }

    private fun increaseCapacity() {
        println("Resizing for entry count of $numberOfEntries and capacity of $arraySize")
        // Increase size
        arraySize *= 2

        // Create a new array and add all the exiting items to the bigger table
        val localEntries: Array<LinkedList<Entry<K, V>>> = Array(arraySize) { LinkedList<Entry<K, V>>() }

        numberOfEntries = 0

        entries.forEach {
            it.forEach { entry ->
                put(entry.key, entry.value, localEntries)
            }
        }

        // Make the local copy the new entry array
        entries = localEntries
    }

    fun get(key: K): V? {
        val index = calculateHashCode(key)
        val listAtArraySlot = entries[index]

        return listAtArraySlot.find { it.key == key }?.value
    }

    fun remove(key: K) {
        val index = calculateHashCode(key)
        entries[index].clear()
        numberOfEntries--
    }

    private fun calculateHashCode(key: K): Int {
        return key.hashCode() % arraySize
    }

    override fun toString(): String {
        val sb = StringBuilder()
        entries.forEach { if (it.isNotEmpty()) sb.append(it).append('\n') }
        return sb.toString()
    }
}

fun main() {
    testHashMap()
}

fun testHashMap() {
    val aHashMap = BasicHashMap<String, String>()

    aHashMap.put("A", "Alpha")
    aHashMap.put("B", "Bravo")
    aHashMap.put("C", "Charlie")
    aHashMap.put("D", "Delta")
    aHashMap.put("E", "Echo")
    aHashMap.put("F", "Foxtrot")
    aHashMap.put("G", "Golf")
    aHashMap.put("H", "Hotel")
    aHashMap.put("I", "India")
    aHashMap.put("J", "July")
    aHashMap.put("K", "Kilo")
    aHashMap.put("L", "Lima")
    aHashMap.put("M", "Mike")
    aHashMap.put("N", "November")
    aHashMap.put("O", "Oscar")
    aHashMap.put("P", "Papa")
    aHashMap.put("Q", "Quebec")
    aHashMap.put("R", "Romeo")
    aHashMap.put("S", "Sierra")
    aHashMap.put("T", "Tango")
    aHashMap.put("U", "Uniform")
    aHashMap.put("V", "Victor")
    aHashMap.put("W", "Whiskey")
    aHashMap.put("X", "X-Ray")
    aHashMap.put("Y", "Yankee")
    aHashMap.put("Z", "Zulu")

    println(aHashMap)
}