Introduction to Scala Hash Map

If You are interested to learn about the Scala map

Hash Map is a part of Scala Collection’s. It is used to store element and return a map. A Hash Map is a combination of key and value pairs which are stored using a Hash Table data structure. It provides the basic implementation of Map. Hash Map is used to store element. It use hash code to store elements and return a map.

Hash Map Example

In this example, we have created a HashMap.

import scala.collection.immutable._  
object MainObject{  
    def main(args:Array[String]){  
        var hashMap = new HashMap()  
        var hashMap2 = HashMap("A"->"Apple","B"->"Ball","C"->"Cat")  
        println(hashMap)  
        println(hashMap2)  
    }  
}  

Output:

Map()
Map(A -> Apple, B -> Ball, C -> Cat)

Scala HashMap Example: Adding and Accessing Elements

In the following example, we have created a HashMap. this program add elements and access elements as well.

import scala.collection.immutable._  
object MainObject{  
    def main(args:Array[String]){  
        var hashMap = HashMap("A"->"Apple","B"->"Ball","C"->"Cat")  
        hashMap.foreach {  
            case (key, value) => println (key + " -> " + value)       // Iterating elements  
        }  
        println(hashMap("B"))               // Accessing value by using key  
        var newHashMap = hashMap+("D"->"Doll")  
        newHashMap.foreach {  
            case (key, value) => println (key + " -> " + value)  
        }  
          
    }  
}  

Output:

A -> Apple
B -> Ball
C -> Cat
Ball
A -> Apple
B -> Ball
C -> Cat
D -> Doll

Adding and Accessing Elements :

In the below example, A HashMap is created. add elements and access elements also performed.

// Scala program to Adding and Accessing Elements HashMap
import scala.collection.mutable.HashMap
  
// Creating object 
object Geeks 
{ 
  
    // Main method 
    def main(args: Array[String]) 
    { 
        // Creating HashMap
        var hashMap = HashMap("C"->"Csharp", "S"->"Scala", "J"->"Java")
          
        // Iterating elements
        hashMap.foreach 
        {  
            case (key, value) => println (key + " -> " + value)         
        }  
          
        // Accessing value by using key 
        println(hashMap("S"))  
          
        // Adding element
        var HashMap2 = hashMap + ("P"->"Perl")  
        HashMap2.foreach 
        {  
            case (key, value) => println (key + " -> " + value)  
        }  
    } 
} 

Output:

S -> Scala
J -> Java
C -> Csharp
Scala
S -> Scala
P -> Perl
J -> Java
C -> Csharp

 
Removing an element from HashMap :
A HashMap is created than removing an element is performed using – sign. Below is the example to removing an element from HashMap.

// Scala program to removing Element HashMap
import scala.collection.mutable.HashMap
  
// Creating object 
object Geeks 
{ 
  
    // Main method 
    def main(args: Array[String]) 
    { 
        // Creating HashMap
        var hashMap = HashMap("C"->"Csharp", "S"->"Scala", "J"->"Java")
          
        // Iterating elements
        hashMap.foreach 
        { 
            case (key, value) => println (key + " -> " + value)         
        } 
          
        // Removing an element
        hashMap -= "C"
          
        println("After Removing")
        hashMap.foreach 
        { 
            case (key, value) => println (key + " -> " + value) 
        } 
    } 
} 

Output:

S -> Scala
J -> Java
C -> Csharp
After Removing
S -> Scala
J -> Java

With those requirements in mind, let’s write a short outline:

case class Entry[K, V](key: K, value: V)

class HashMap[K, V] private (entries: Vector[Vector[Entry[K, V]]]) {

  def add(key: K, value: V): HashMap[K, V] = ???

  def remove(key: K): HashMap[K, V] = ???

  def get(key: K): Option[V] = ???
}

• Class Entry represents a key-value pair
• I use Vector to hold the keys. Each key contains another Vector that holds all the values. Hence we have Vector[Vector[Entry[K, V]]]
• Since my hash map is immutable, add must return a new hash map. The original map is left untouched.
• get returns an Option that contains the value of that key if it exists and None otherwise
• ??? means throw new NotImplementedException(), which is quite convenient for writing code outline

Method add is quite straight forward:

def add(key: K, value: V): HashMap[K, V] = {
  val idx = indexFor(key)

  // if the table is empty, initialize and then run 'add' again
  if(entries.isEmpty) init.add(key, value)
  // otherwise, if 'key' exists, replace its old value
  // if not, associate 'value' with 'key'
  else {
    val chain = entries(idx)
    chain.indexWhere(_.key == key) match {
      case -1 => // key not found
        val e = Entry(key, value)
        new HashMap(entries.updated(idx, e +: chain))
      case i =>
        val replaced = chain(i).copy(value = value)
        new HashMap(entries.updated(idx, chain.updated(i, replaced)))
    }
  }
}

private val initialCapacity = 16

private def init: HashMap[K, V] = {
  new HashMap(Vector.fill(initialCapacity)(Vector.empty))
}

/** Returns the index of this key in the internal entry vector. */
private def indexFor(key: K): Int = {
  key.hashCode() & entries.length
}

remove is a bit tricky to write since we cannot do an ‘in-place’ removal (ahem, immutability …). So we have to use filter:

def remove(key: K): HashMap[K, V] = {
  val idx = indexFor(key)
  val updated = entries.updated(idx, entries(idx).filter(_.key != key))
  new HashMap(updated)
}

However, this is not the most efficient way because filter will go through the whole collection instead of stopping once the unwanted element is seen. A more efficient approach to this case is to not remove anything at all but just ‘mark’ the element as removed. But I will not implement that here

And lastly, we need to write out get method:

def get(key: K): Option[V] = {
  val idx = indexFor(key)
  entries(idx).find(_.key == key).map(_.value)
}

Method find of Vector already returns an Option if there is no element match with key so we don’t need to manually handle that. Utility methods like find is the reason why I love Scala so much. It allows me to leave work early.

And that’s it! We have completed our Hash Map implementation that satisfied the requirements we made at the beginning. You can use it like this:

val map = new HashMap[Int, String](Vector.empty)
val web = map.add(1, "web") // 1 -> "web"
val dev = web.add(2, "dev") // 1 -> "web", 2 -> "dev"