Hash Map Implementation in Kotlin

1. Introduction

In this tutorial, we will learn how to implement a simple HashMap structure using Kotlin programming language.

A HashMap is a widely used data structure that implements the map interface, mapping keys to values. It allows us to store and retrieve objects based on a key. In essence, it's an associative array. Under the hood, a HashMap uses an array and a hashing technique to store the data.

2. Implementation Steps

1. Define an inner Entry class that will represent the individual key-value pairs.

2. Implement a method to compute a hash for the keys.

3. Implement core methods like put, get, remove, and size.

4. Handle collisions using linked lists.

3. Implementation in Kotlin Programming

class HashMap<K, V> {
    private data class Entry<K, V>(val key: K, var value: V) {
        var next: Entry<K, V>? = null
    }
    private val capacity = 16
    private val table = arrayOfNulls<Entry<K, V>>(capacity)
    private var size = 0
    // Computes the index in the array
    private fun hash(key: K): Int = (key.hashCode() and Int.MAX_VALUE) % capacity
    // Inserts or updates the key-value pair
    fun put(key: K, value: V): V? {
        val index = hash(key)
        var existing = table[index]
        while (existing != null) {
            if (existing.key == key) {
                val oldValue = existing.value
                existing.value = value
                return oldValue
            }
            existing = existing.next
        }
        val entry = Entry(key, value)
        entry.next = table[index]
        table[index] = entry
        size++
        return null
    }
    // Fetches the value by key
    fun get(key: K): V? {
        var current = table[hash(key)]
        while (current != null) {
            if (current.key == key) {
                return current.value
            }
            current = current.next
        }
        return null
    }
    // Removes the key-value pair by key
    fun remove(key: K): V? {
        val index = hash(key)
        var prev: Entry<K, V>? = null
        var current = table[index]
        while (current != null) {
            if (current.key == key) {
                if (prev == null) {
                    table[index] = current.next
                } else {
                    prev.next = current.next
                }
                size--
                return current.value
            }
            prev = current
            current = current.next
        }
        return null
    }
    // Returns the size of the map
    fun size(): Int = size
}
fun main() {
    val hashMap = HashMap<String, Int>()
    hashMap.put("One", 1)
    hashMap.put("Two", 2)
    hashMap.put("Three", 3)
    println("Size of map: ${hashMap.size()}")
    println("Value of 'Two': ${hashMap.get("Two")}")
    hashMap.remove("Two")
    println("Size after removal: ${hashMap.size()}")
    println("Value of 'Two' after removal: ${hashMap.get("Two")}")
}

Output:

Size of map: 3
Value of 'Two': 2
Size after removal: 2
Value of 'Two' after removal: null

Explanation:

1. Entry class: Represents the individual key-value pair and contains a reference to the next Entry. This reference is useful for handling collisions.

2. hash method: Computes an index in the array for a given key.

3. put method: Inserts a new key-value pair or updates the value if the key already exists.

4. get method: Retrieves the value associated with a given key.

5. remove method: Removes the key-value pair based on the given key.

6. size method: Returns the current number of entries in the hash map.

7. The main function showcases basic operations such as inserting key-value pairs, fetching a value, and removing a key-value pair.