4.10.2023
706. Design HashMap easy
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/359
Problem TLDR
Design a HashMap
Intuition
The simple implementation consists of a growing array of buckets, where each bucket is a list of key-value pairs.
Approach
For better performance:
use
LinkedList
start with smaller buckets size
Complexity
Time complexity:
O(1)Space complexity:
O(1), for all operations
Code
class MyHashMap() {
var table = Array<MutableList<Pair<Int, Int>>>(16) { mutableListOf() }
var count = 0
fun bucket(key: Int) = table[key % table.size]
fun rehash() = with(table.flatMap { it }) {
table = Array(table.size * 2) { mutableListOf() }
for ((key, value) in this) bucket(key) += key to value
}
fun put(key: Int, value: Int) = with(bucket(key)) {
if (removeAll { it.first == key }) count++
this += key to value
if (count > table.size) rehash()
}
fun get(key: Int) = bucket(key)
.firstOrNull { it.first == key }?.second ?: -1
fun remove(key: Int) {
if (bucket(key).removeAll { it.first == key }) count--
}
}