extends Map[K,V]?

I think you just need to implement iterator, which isn't a big pain, and change put to +, evict to -.