706.design-hashmap.md

706. Design HashMap

Take a look at 705. Design HashSet for updated approaches, the implementation is similar.

Direct Access Table

class MyHashMap() {

    // Space complexity: O(U)
    private val array = IntArray(1000001) { -1 }

    // Time complextiy: O(1)
    fun put(key: Int, value: Int) {
        array[key] = value
    }

    // Time complextiy: O(1)
    fun get(key: Int): Int {
        return array[key] ?: -1
    }

    // Time complextiy: O(1)
    fun remove(key: Int) {
        array[key] = -1
    }
}

Chaining

We use linked list to handle collision.

Bucket of size 2, hash(key) = key % 2
[0]: sentinel
[1]: sentinel
...

// Add (1, 1)
[0]: sentinel
[1]: sentinel -> (1, 1)

// Add (2, 2)
[0]: sentinel -> (2, 2)
[1]: sentinel -> (1, 1)

// Add (3, 3)
[0]: sentinel -> (2, 2)
[1]: sentinel -> (1, 1) -> (3, 3)

// Add (2, 5)
[0]: sentinel -> (2, 5)
[1]: sentinel -> (1, 1) -> (3, 3)

// Add (4, 4)
[0]: sentinel -> (2, 5) -> (4, 4)
[1]: sentinel -> (1, 1) -> (3, 3)

data class MapNode(
    val key: Int,
    var value: Int,
    var next: MapNode? = null
)

class MyHashMap() {

    // The two numbers are prime numbers, just pick them randomly.
    private val size = 19997
    private val multipler = 12582917L
    private val bucket = Array<MapNode>(size) { MapNode(-1, -1) }

    fun put(key: Int, value: Int) {
        var prev: MapNode? = bucket[hash(key)]
        var node: MapNode? = prev?.next
        while (node != null) {
            if (node.key == key) {
                node.value = value
                return
            }
            prev = node
            node = node.next
        }
        prev?.next = MapNode(key, value)
    }

    fun get(key: Int): Int {
        var node: MapNode? = bucket[hash(key)]
        while (node != null) {
            if (node.key == key) return node.value
            node = node.next
        }
        return -1
    }

    fun remove(key: Int) {
        var prev: MapNode? = bucket[hash(key)]
        var node: MapNode? = prev?.next
        while (node != null) {
            if (node.key == key) {
                prev?.next = node.next
                return
            }
            prev = node
            node = node.next
        }
    }

    private fun hash(key: Int): Int {
        // We use the multiplication method to hash the key.
        return (key.toLong() * multipler % size).toInt()
    }
}

Open Addressing

class Probe() {
    private val size = 199997
    private val multipler = 12582917L
    private val table = Array<MapNode?>(size) { null }

    fun put(key: Int, value: Int) {
        var probe = 0
        var hash = hash(key, probe)
        while (table[hash] != null) {
            val node = table[hash]!!
            if (node.key == key) {
                node.value = value
                return
            }
            probe++
            hash = hash(key, probe)
        }
        table[hash] = MapNode(key, value)
    }

    fun get(key: Int): Int {
        var probe = 0
        var hash = hash(key, probe)
        while (table[hash] != null) {
            val node = table[hash]!!
            if (node.key == key) {
                return node.value
            }
            probe++
            hash = hash(key, probe)
        }
        return -1
    }

    fun remove(key: Int) {
        var probe = 0
        var hash = hash(key, probe)
        while (table[hash] != null) {
            val node = table[hash]!!
            if (node.key == key) {
                table[hash] = null
                return
            }
            probe++
            hash = hash(key, probe)
        }
    }

    private fun hash(key: Int, probe: Int): Int {
        return (key.toLong() * multipler % size).toInt()
    }
}