Dictionaries in C#

Key-value pair storage where keys are unique. Used for fast lookups, insertion and deletion based on key.

How they work

Dictionary uses internally int[] buckets and Entry[] entries. Buckets is an array of integers that maps to a index of entries. Key is then used to get an int hashcode and applied modulo will point at the bucket slot. When multiple keys have save bucket index - collision happen, bucket becomes linked-list and multiple items will be stored into same bucket, which has a performance implications. When a number of current elements reaches the number of buckets, new bucket array is allocated and its size is set to a closest higher prime number of a doubled current items count -> closest_prime(current_size * 2).
Prime numbers are either picked up from prepared static list build in .net (max prime is 7199369) or calculated on the run.
During resizing, - each item has to be re-hashed and copied which may be expensive. - allocated size is doubled - there is also previous bucket array allocated for a short while in parallel until it is collected by GC

Beware

• resizing - causes memory spike and has performance impact. Set capacity ahead to reduce its occurrence.
• collisions - causes performance deterioration, in a worst case Dict will become linked list - GetHashCode must return evenly distributed numbers
• slow GetHashCode calculation - causes performance deterioration