# 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.

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

if (!hasNext) {
next = nextNode
} else {
}
}

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

val hash: Int = kv.first.hash
if (nodes[hash] == null) {
} else {
}
}

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

val hash: Int = kv.first.hash
if (nodes[hash] == null) {
} else {
}
}

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

if (!hasNext) {
next = nextNode
} else {
}
}

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.

1. HashMap - Kotlin Programming Language