Investigate potential alternative data structures for s.c.i.HashCollision{Map,Set}Node

[joshlemer]

Currently HashMapCollisionNodes use an underlying Vector[(K, V)] to represent a hash collision bucket. However, we can probably achieve better performance using a mutable data structure, which the builder can take advantage of during a build phase.
The properties we are looking for are:

• Very small memory overhead, there should not be big wasted space i.e. in the case of an ArrayBuffer
• Should support the following operations
  • inPlaceUpdateByKeyOrElseAdd(key: Key, value: Value): Unit
    • upserts the key/value
    • order doesn't matter here, at the front/middle/back is fine for adding.
  • updateByKeyOrElseAdd(key: Key, value: Value): Unit
    • non-mutating form of the above, for use after builder publishes
  • inPlaceRemoveByKey(key: Key): Unit
  • removeByKey(key: Key): Unit
    • non-mutating form of the above, for use after builder publishes

I am personally leaning towards an unrolled linked list of some sort, since this would allow for very fast traversing, mutating, and prepending, as well as pretty-fast immutable updates, and very fast immutable prepends.

[joshlemer]

When considering potential data structures, this issue should be kept in mind:
#11203