Re-Implement HashMap

In this article, I re-implement HashMap in order to cultivate my better understanding.

Here is what I’d like to implement.

  • key-value container, access value with key
  • can contain multiple key-value pairs
  • can access a value with $O\bigl(N\bigr)$
  • can access a value even hash collides

The basic idea is like below. The HashMap has an array inside. Calculate the index of the array from key or key’s hash. This enables to access value with $O\bigl(N\bigr)$ . However, same index could be calculated from different key (collision), so the node should know another node.

Fig-1 The Basic Idea of HashMap

Overall Code

Here I implemented the very basics.

class MyHashMap<K : Any, V : Any> {
  private class Node<K, V>(val key: K, val value: V) {

    var next: Node<K, V>? = null

    val hasNext: Boolean get() = (next != null)

    fun contains(key: K): Boolean {
      if (value == this.value) return true
      if (!hasNext) return false
      return requireNotNull(next).contains(key)
    }

    fun addNext(nextNode: Node<K, V>) {
      if (!hasNext) {
        next = nextNode
      } else {
        requireNotNull(next).addNext(nextNode)
      }
    }

    fun value(key: K): V? {
      if (key == this.key) return value
      if (!hasNext) return null
      return requireNotNull(next).value(key)
    }
  }

  private val nodes: Array<Node<K, V>?> = arrayOfNulls<Node<K, V>?>(DEFAULT_SIZE)

  fun contains(key: K): Boolean {
    val hash: Int = key.hash
    val node: Node<K, V>? = nodes[hash]
    if (node == null) return false
    return node.contains(key)
  }

  fun add(kv: Pair<K, V>) {
    val hash: Int = kv.first.hash
    val nodeToAdd = Node(kv.first, kv.second)
    if (nodes[hash] == null) {
      nodes[hash] = nodeToAdd
    } else {
      requireNotNull(nodes[hash]).addNext(nodeToAdd)
    }
  }

  fun value(key: K): V? {
    val hash: Int = key.hash
    val node: Node<K, V>? = nodes[hash]
    if (node == null) return null
    return node.value(key)
  }

  private val Any.hash get() = this.hashCode() % DEFAULT_SIZE

  companion object {
    private const val DEFAULT_SIZE = 100
  }
}

One by One

The data structure should have key and value, so the class have type parameters for it.

class MyHashMap<K : Any, V : Any> {

The key-value pair is represented by Node internally. The Node has next Node. In case that hash or index collides, the Node should know the referrence of next Node.

  private class Node<K, V>(val key: K, val value: V) {

    var next: Node<K, V>? = null

    val hasNext: Boolean get() = (next != null)

Here is the calculation of hash or index. The HashMap I implemented has an array internally, I need the index that is calculated from hashCode(). In this case, surplus divided by the size of array is enough.

  private val Any.hash get() = this.hashCode() % DEFAULT_SIZE

  companion object {
    private const val DEFAULT_SIZE = 100
  }

Now I can access the key-value pair by the index calculated from the key with $O\bigl(N\bigr)$ . If the Node accessed directly with the index has the key, the HashMap returns the value. Else inquire the Node recursively.

  fun contains(key: K): Boolean {
    val hash: Int = key.hash
    val node: Node<K, V>? = nodes[hash]
    if (node == null) return false
    return node.contains(key)
  }

  fun add(kv: Pair<K, V>) {
    val hash: Int = kv.first.hash
    val nodeToAdd = Node(kv.first, kv.second)
    if (nodes[hash] == null) {
      nodes[hash] = nodeToAdd
    } else {
      requireNotNull(nodes[hash]).addNext(nodeToAdd)
    }
  }

  fun value(key: K): V? {
    val hash: Int = key.hash
    val node: Node<K, V>? = nodes[hash]
    if (node == null) return null
    return node.value(key)
  }

Here is the implementation of Node. It returns the value if the key is identical, or inquire the next Node recursively.

  private class Node<K, V>(val key: K, val value: V) {

    var next: Node<K, V>? = null

    val hasNext: Boolean get() = (next != null)

    fun contains(key: K): Boolean {
      if (value == this.value) return true
      if (!hasNext) return false
      return requireNotNull(next).contains(key)
    }

    fun addNext(nextNode: Node<K, V>) {
      if (!hasNext) {
        next = nextNode
      } else {
        requireNotNull(next).addNext(nextNode)
      }
    }

    fun value(key: K): V? {
      if (key == this.key) return value
      if (!hasNext) return null
      return requireNotNull(next).value(key)
    }
  }

Conclusion

OK here I implemented the very basic idea of HashMap.

References

  1. HashMap - Kotlin Programming Language

About me

Experienced software developer. Technical lead at Fuller, Inc. My speciality is developing Android native app. I'm living in Tsukuba Japan, with my family, dogs, and cats :)

Here is more detailed profile.