[Backend] 데이터 구조 (HashTable)

춣처 : GeeksforGeeks

HashTable

package org.example.hash

class IntStringHashTable {
    private var count: Int = 0
    private var capacity: Int = DEFAULT_CAPACITY
    private var table: Array<MutableList<Pair<Int,String>>?> = arrayOfNulls(capacity)

    companion object {
        private const val DEFAULT_CAPACITY: Int = 10
    }

    fun size(): Int = count

    fun add(key: Int, value: String) {
        if (count == table.size) {
            rehash()
        }

        val index = hash(key)

        if (table[index] == null) {
            table[index] = mutableListOf()
        }

        val list = table[index]!!
        for((i, pair) in list.withIndex()) {
            if(pair.first == key) {
                list[i] = Pair(key, value)
                return
            }
        }

        list.add(Pair(key, value))
        count++
    }

    fun remove(key: Int): String? {
        val index = hash(key)
        val list = table[index] ?: return null

        val iterator = list.iterator()
        while (iterator.hasNext()) {
            val entry = iterator.next()
            if (entry.first == key) {
                iterator.remove()
                count--
                return entry.second
            }
        }

        return null
    }

    fun search(key: Int): String? {
        val index = hash(key)
        val list = table[index] ?: return null

        for((k,v) in list) {
            if (k == key) {
                return v
            }
        }
        return null
    }

    fun clear() {
        for (i in table.indices) {
            table[i]?.clear()
            table[i] = null
        }

        count = 0
        capacity = DEFAULT_CAPACITY
        table = arrayOfNulls(capacity)
    }

    private fun hash(key: Int): Int{
        val h = key.hashCode()

        val mixedHash = h xor (h ushr 16)

        return mixedHash and (table.size - 1)
    }

    private fun rehash() {
        val oldTable = table

        capacity *= 2
        table = arrayOfNulls(capacity)

        count = 0
        for (list in oldTable) {
            if (list != null) {
                for (pair in list) {
                    add(pair.first, pair.second)
                }
            }
        }

        println("Fun rehash() : Table is rehashed!")
    }
}

 

 

결과

fun main() {
    val hashTable = IntStringHashTable()

    println("1. Data Insertion")
    for (i in 0..11) {
        hashTable.add(i, "Data $i")
        println("Hash element <key-value> : <$i - ${hashTable.search(i)}>")
    }

    println("\n2. Data Switch using the same key")
    hashTable.add(1, "Kotlin Advanced")
    println("Insert new value(\'Kotlin Advanced\' to the existing key 1: ${hashTable.search(1)}")

    println("\n3. Data Removal")
    val initialSize = hashTable.size()
    for (i in 1 until initialSize) {
        val removedValue = hashTable.remove(i)
        println("Removed element <key-value> : <$i - $removedValue>")
    }

    println("\n4. Data Clear")
    hashTable.clear()
    println("Cleared size : ${hashTable.size()}")
}

/*
1. Data Insertion
Hash element <key-value> : <0 - Data 0>
Hash element <key-value> : <1 - Data 1>
Hash element <key-value> : <2 - Data 2>
Hash element <key-value> : <3 - Data 3>
Hash element <key-value> : <4 - Data 4>
Hash element <key-value> : <5 - Data 5>
Hash element <key-value> : <6 - Data 6>
Hash element <key-value> : <7 - Data 7>
Hash element <key-value> : <8 - Data 8>
Hash element <key-value> : <9 - Data 9>
Fun rehash() : Table is rehashed!
Hash element <key-value> : <10 - Data 10>
Hash element <key-value> : <11 - Data 11>

2. Data Switch using the same key
Insert new value('Kotlin Advanced' to the existing key 1: Kotlin Advanced

3. Data Removal
Removed element <key-value> : <1 - Kotlin Advanced>
Removed element <key-value> : <2 - Data 2>
Removed element <key-value> : <3 - Data 3>
Removed element <key-value> : <4 - Data 4>
Removed element <key-value> : <5 - Data 5>
Removed element <key-value> : <6 - Data 6>
Removed element <key-value> : <7 - Data 7>
Removed element <key-value> : <8 - Data 8>
Removed element <key-value> : <9 - Data 9>
Removed element <key-value> : <10 - Data 10>
Removed element <key-value> : <11 - Data 11>

4. Data Clear
Cleared size : 0
*/

---

HashTable (in Generic<K,V>)

package org.example.hash

class GenericHashTable<K,V> {
    private var count: Int = 0
    private var capacity: Int = DEFAULT_CAPACITY
    private var table: Array<MutableList<Pair<K,V>>?> = arrayOfNulls(capacity)

    companion object {
        private const val DEFAULT_CAPACITY: Int = 10
    }

    fun size(): Int = count

    fun add(key: K, value: V) {
        if (count == table.size) {
            rehash()
        }

        val index = hash(key)

        if (table[index] == null) {
            table[index] = mutableListOf()
        }

        val list = table[index]!!
        for((i, pair) in list.withIndex()) {
            if(pair.first == key) {
                list[i] = Pair(key, value)
                return
            }
        }

        list.add(Pair(key, value))
        count++
    }

    fun remove(key: K): V? {
        val index = hash(key)
        val list = table[index] ?: return null

        val iterator = list.iterator()
        while (iterator.hasNext()) {
            val entry = iterator.next()
            if (entry.first == key) {
                iterator.remove()
                count--
                return entry.second
            }
        }

        return null
    }

    fun search(key: K): V? {
        val index = hash(key)
        val list = table[index] ?: return null

        for((k,v) in list) {
            if (k == key) {
                return v
            }
        }
        return null
    }

    fun clear() {
        for (i in table.indices) {
            table[i]?.clear()
            table[i] = null
        }

        count = 0
        table = arrayOfNulls(capacity)
    }

    private fun hash(key: K): Int{
        val h = key.hashCode()

        val mixedHash = h xor (h ushr 16)

        return mixedHash and (table.size - 1)
    }

    private fun rehash() {
        val oldTable = table

        capacity *= 2
        table = arrayOfNulls(capacity)

        count = 0
        for (list in oldTable) {
            if (list != null) {
                for (pair in list) {
                    add(pair.first, pair.second)
                }
            }
        }

        println("Fun rehash() : Table is rehashed!")
    }
}

 

---

HashTable (in Generic<K,V>) 

import kotlin.math.absoluteValue

class HashTable<K,V> (private var capacity: Int = DEFAULT_CAPACITY) {
    private var table: Array<Pair<K, V>?> = arrayOfNulls(capacity)
    private var count: Int = 0
    
    companion object {
        private const val DEFAULT_CAPACITY = 8
        private const val LOAD_FACTOR = 0.75
    }
    
    private val deleted: Pair<K, V>? = null
    
    fun size(): Int = count
    
    private fun hash(key: K): Int = (key.hashCode().absoluteValue % capacity)
    
    fun add(key: K, value: V) {
        if (count >= capacity * LOAD_FACTOR) rehash()
        
        var index = hash(key)
        
        while (true) {
            val current = table[index]
            if (current == null || current == deleted) {
                table[index] = Pair(key, value)
                count++
                return
            }
            if (current.first == key) {
                table[index] = Pair(key, value)
                return
            }
            index = (index + 1) % capacity
        }
    }
    
    fun search(key: K): V? {
        var index = hash(key)
        var probeCount = 0
        
        while (probeCount < capacity) {
            val current = table[index]
            
            if (current == null) return null
            if (current != deleted && current.first == key) return current.second
            index = (index + 1) % capacity
            probeCount++
        }
        
        return null
    }
    
    fun remove(key: K): V? {
        var index = hash(key)
        var probeCount = 0
        
        while (probeCount < capacity) {
            val current = table[index]
            
            if (current==null) return null
            if (current != deleted && current.first == key) {
                table[index] = deleted
                count--
                return current.second
            }
            
            index = (index + 1) % capacity
            probeCount++
        }
        return null
    }
    
    fun clear() {        
        count = 0
        capacity = DEFAULT_CAPACITY
        table = arrayOfNulls(capacity)
    }
    
    fun rehash() {
        val oldTable = table        
        capacity *= 2
        table = arrayOfNulls(capacity)
        
        count = 0
        for (pair in oldTable) {
            if (pair != null && pair != deleted) {
                add(pair.first, pair.second)
            }
        }
        
        println("Fun rehash() : Table resized to $capacity")
    }
}

 

결과

1. Data Insertion
Hash element <key-value> : <0 - Data 0>
Hash element <key-value> : <1 - Data 1>
Hash element <key-value> : <2 - Data 2>
Hash element <key-value> : <3 - Data 3>
Hash element <key-value> : <4 - Data 4>
Hash element <key-value> : <5 - Data 5>
Fun rehash() : Table resized to 16
Hash element <key-value> : <6 - Data 6>
Hash element <key-value> : <7 - Data 7>
Hash element <key-value> : <8 - Data 8>
Hash element <key-value> : <9 - Data 9>
Hash element <key-value> : <10 - Data 10>
Hash element <key-value> : <11 - Data 11>

2. Data Switch using the same key
Fun rehash() : Table resized to 32
Insert new value('Kotlin Advanced' to the existing key 1: Kotlin Advanced

3. Data Removal
Removed element <key-value> : <1 - Kotlin Advanced>
Removed element <key-value> : <2 - Data 2>
Removed element <key-value> : <3 - Data 3>
Removed element <key-value> : <4 - Data 4>
Removed element <key-value> : <5 - Data 5>
Removed element <key-value> : <6 - Data 6>
Removed element <key-value> : <7 - Data 7>
Removed element <key-value> : <8 - Data 8>
Removed element <key-value> : <9 - Data 9>
Removed element <key-value> : <10 - Data 10>
Removed element <key-value> : <11 - Data 11>

4. Data Clear
Cleared size : 0

---

참고 자료

 - Hash Tables in Kotlin: A Deep Dive into Efficient Data Storage | by chetan shingare | Medium

 - data class에서 hashcode?? 뭔지 모르겠어요 :: 알아가는 재미

 - https://www.geeksforgeeks.org/java/hashtable-keys-method-in-java/

 - https://mangkyu.tistory.com/102

 

Powered By. ChatGPT & Gemini