
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
'Backend' 카테고리의 다른 글
| [Backend] 데이터 구조 (Queue) (0) | 2025.09.11 |
|---|---|
| [Backend] 데이터 구조 (Stack) (0) | 2025.09.11 |
| [Backend] 데이터 구조 (List) (0) | 2025.09.11 |
| [Backend] Generic Tutorial (Kotlin) (1) | 2025.09.11 |
| [Backend] Template Method 패턴 (1) | 2025.09.03 |