Hash Table Implementation in Kotlin

1. Introduction

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

A Hash Table (or Hash Map) is a data structure that offers fast insertion, deletion, and search operations. It works by associating keys with specific values, and these key-value pairs are stored using a hash function to compute an index into an array of buckets or slots.

2. Implementation Steps

1. Define the basic structure of a HashTable that includes methods for insertion, deletion, and searching.

2. Use an array for storage, each entry of which contains a list (bucket) to handle hash collisions.

3. Implement a hash function to convert keys into indices in the array.

4. Insertion will involve adding a key-value pair to the corresponding bucket. If a collision occurs, append it to the bucket list.

5. Searching will involve finding the bucket for the given key and then searching the list.

6. Deletion involves removing the key-value pair from the bucket's list.

3. Implementation in Kotlin Programming

// 1. Define the basic structure for the HashTable
class HashTable<K, V>(private val size: Int) {
    private val storage: Array<MutableList<Pair<K, V>>> = Array(size) { mutableListOf() }
    
    // 3. Simple hash function to convert keys into indices
    private fun hash(key: K): Int = key.hashCode() % size
    
    // 4. Insert a key-value pair into the hash table
    fun put(key: K, value: V) {
        val index = hash(key)
        storage[index].add(Pair(key, value))
    }
    
    // 5. Retrieve a value for a given key from the hash table
    fun get(key: K): V? {
        val index = hash(key)
        for (entry in storage[index]) {
            if (entry.first == key) {
                return entry.second
            }
        }
        return null
    }
    
    // 6. Remove a key-value pair from the hash table
    fun remove(key: K) {
        val index = hash(key)
        val iterator = storage[index].iterator()
        while (iterator.hasNext()) {
            if (iterator.next().first == key) {
                iterator.remove()
                return
            }
        }
    }
}

// client code to test Hash Table Implementation in Kotlin
fun main() {
    val hashTable = HashTable<String, String>(10)
    hashTable.put("John", "Engineer")
    hashTable.put("Jane", "Doctor")
    hashTable.put("Mike", "Architect")
    println("John is an ${hashTable.get("John")}")
    println("Jane is an ${hashTable.get("Jane")}")
    hashTable.remove("Jane")
    println("After removing Jane: Jane is an ${hashTable.get("Jane")}")
}

Output:

John is an Engineer
Jane is an Doctor
After removing Jane: Jane is an null

Explanation:

1. The HashTable class is a generic class that can store any type of key-value pair.

2. An array storage is initialized to store buckets. Each bucket is a MutableList that can store multiple entries due to collisions.

3. A simple hash function is used to compute the index in the array based on the key's hash code.

4. The put method computes the index using the hash function and adds the key-value pair to the appropriate bucket.

5. The get method retrieves the bucket using the hash function and searches through the bucket's list for the given key.

6. The remove method deletes the key-value pair from the bucket's list.

7. In the main function, we create a hash table, insert key-value pairs, retrieve values, and then delete a key. The output demonstrates the insertion, retrieval, and deletion operations.