LeetCode Entry

706. Design HashMap

4.10.2023 easy 2023 kotlin

Design a HashMap

706. Design HashMap easy blog post substack image.png

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--
    }
}