FC47: DictionaryArray - Poor man's segmented dictionary

If you need to put millions of objects into a dictionary, without knowing the total count in advance, what do you use? Having a good implementation of segmented dictionary implementation would be ideal. If you do not have that, an array of dictionaries could be a poor man’s solution.

Here is a simple implementation:

The problem with such simple implementation is GetHashCode is called twice. Something it’s possible to do a simple approximation just for getting the parition.

I tested it out using 1 million items, with 1,103 partitions, no LOH allocations:

Such solution can be quite effective if such large container is only needed for a short duration. You populate the data, use it, then throw everything away, without the need of promoting to Gen2.

Notice Large object heap segment is considered part of Gen2, only collected during Gen2 garbage collection. It could even drag objects into Gen1/Gen2 due to card table scanning.

Source code: FrugalCafe/Common/DictionaryArray.cs at master · ProfFrugal/FrugalCafe (github.com)