Size-hints and over-allocated arrays for `fromList[With]`

[sjakobi]

I'm thinking about a design involving "size-hints", where the user can give an estimate of the size of the resulting HashMap.

fromListWithSizeHint :: Hashable k => Int -> [(k, v)] -> HashMap k v

We we would use the size estimate to calculate the lengths of the BitmapIndexed arrays which we would then over-allocate. E.g., given a size estimate of 100, we would allocate a root array with length 32 (maxChildren). The arrays at the next level could be allocated with size 4 or 5. The following levels would be allocated purely on demand without any over-allocation, just like we currently do it. Once all the elements are inserted we'd do an array-shrinking pass over the levels where we used over-allocation.

[treeowl]

My main concern is that the shrinking pass could be pretty pricy, but it's worth trying. It would also be possible to try an array-doubling scheme without an estimate, but of course that would be even more marginal.