CODEWITHSUNDEEP
scaladata-structuresfunctional-programminghashmap
hispanicprogrammer
hispanicprogrammer

Reputation: 437

How does Scala implement HashMap data structure?

I have lately become obsessed with functional programming and I am really into Scala. Just out of curiosity I decided to start implementing my own data structures. I started with a SinglyLinkedList where I differentiated with two case classes the case Empty and the case Cons(head,tail). I was wondering if anybody could point me into how I could implement a HashMap? Thank in advance for you help :)

Upvotes: 1

Views: 1050

Answers (2)

Mateusz Kubuszok
Mateusz Kubuszok

Reputation: 27535

I assuming that you mean immutable HashMap? Then you can take a look at tries.

In HashMap you are assuming that if objects are equal, then they have the same hash, and of they have different hashes, they are not equal. So, what you can do is to:

  • create a trie where path from root to leaf is the hash of the key
  • in the node have e.g. list of pairs (key -> value)
  • then finding key-value pair would be about traversing trie, and then travesing the list

If the hash is good then (usually) you should have very view conflicts, so you spend more time in the trie part than in the list part.

Using it in FP is about using tricks to allow reuse partis of the trie when you copy/add/remove values, so that it would stay relatively cheap. How to do that effectively is a bit longer topic but you can take a look at articles like:

or just looking at Scala code for an immutable HashMap. It even refers paper that it was based on.

Upvotes: 2

Boris Azanov
Boris Azanov

Reputation: 4481

HashMap[K, V] should contain hash-vector, something like Vector[List[V]]. And hash function. Try to implement this trait.

hint: try to do this using immutable data structures 

trait HashMap[K, V] {

  val hashVector: Vector[List[V]] = ???

  def hash(key: K): Int = ???

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

  def get(key: Key): V = ???

  def getOrElse(key: Key, defaultValue: V): V = ???
}

Data structure description: HashMap is like HashTable, contains array with links to chains elements with same hash(key) values.

also you could define some helpful constructors:

object HashMap {
  def empty[K, V]: HashMap[K, V] = ???

  def fromSeqPairs[K, V](seq: Seq[(K, V)]): HashMap[K, V] = ???

  def filled[K, V](seq: Seq[K], defaultValue: V): HashMap[K, V] = ???
}

Upvotes: 1

Related Questions