LeetCode Entry

705. Design HashSet

30.05.2023 easy 2023 kotlin

Write a HashSet.

705. Design HashSet easy blog post substack

Telegram

https://t.me/leetcode_daily_unstoppable/228

Problem TLDR

Write a HashSet.

Intuition

There are different hash functions. Interesting implementations is In Java HashMap https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/HashMap.java

Approach

Use key % size for the hash function, grow and rehash when needed.

Complexity

• Time complexity: \(O(1)\)
• Space complexity: \(O(n)\)

Code

class MyHashSet(val initialSz: Int = 16, val loadFactor: Double = 1.6) {
            var buckets = Array<LinkedList<Int>?>(initialSz) { null }
            var size = 0

            fun hash(key: Int): Int = key % buckets.size

            fun rehash() {
            if (size > buckets.size * loadFactor) {
                val oldBuckets = buckets
                buckets = Array<LinkedList<Int>?>(buckets.size * 2) { null }
                    oldBuckets.forEach { it?.forEach { add(it) } }
                }
            }

            fun bucket(key: Int): LinkedList<Int> {
                val hash = hash(key)
                if (buckets[hash] == null) buckets[hash] = LinkedList<Int>()
                    return buckets[hash]!!
                }

                fun add(key: Int) {
                    val list = bucket(key)
                    if (!list.contains(key)) {
                        list.add(key)
                        size++
                        rehash()
                    }
                }

                fun remove(key: Int) {
                    bucket(key).remove(key)
                }

                fun contains(key: Int): Boolean =
                   bucket(key).contains(key)
}