Scala: What is the correct way to create a HashMap variant without linked lists?
How can the mouch Scala standard library be reused to create a HashMap variant that does not handle conflicts at all?
In the HashMap implementation in Scala, I can see that the traits of HashEntry, DefaultEntry and LinkedEntry are related, but I'm not sure if I have control over them.
a source to share
You can do this by expanding HashMap
(read the source code HashMap
to see what needs to be changed); basically you would override put
and +=
to not call findEntry
, and you would override addEntry
(from HashTable
) to just compute the hashcode and delete the entry. Then it won't handle conflicts at all.
But this is not wise, because the structure is HashEntry
specifically designed to handle collisions - the pointer next
becomes completely redundant at this point. Therefore, if you are doing this for performance reasons, this is a poor choice; you have overhead because you wrap everything in Entry
. If you don't want to check for collision, you are better off just storing the tuples (key, value) in a flat array, or using separate arrays of keys and values.
Keep in mind that you will now suffer from collisions in the hash value, not just the key. And it tends to HashMap
start small and then expand, so you initially destroy things that would have survived if it hadn't started small. You can override initialSize
as well if you knew how much you would add so you don't need to resize.
But, basically, if you want to write a custom high-speed insecure hashmap, you'd better write it from scratch or use some other library. If you change the version of the generic library, you get all the insecurity without any speed. If it's worth messing around with it, it's worth a complete overhaul. (For example, you should implement filters and such that map f: (Key,Value) => Boolean
instead of matching a tuple (K,V)
- that way you don't need to wrap and unwrap tuples.)
a source to share