Beside all of the above said please to note following as well:
- You could {Pre} initialize hash bucket array in Dictionary object by passing the initial size in Parentheses (in brackets) to constructor. E.g. 301?
Dictionary<string, string> dictionary = new Dictionary<string, string>( 301 );
Depending on what you need to be faster add or get, you may also find important to focus on optimization towards Add/Remove or just Retrieve. Meaning that, sometimes it is required to locate and retrieve faster rather than add or remove them. In your case you mentioned in example dictionary.Add method, but the question was as well asked for faster replacement in general for whole class Dictionary<TKey, TValue> So i assume, you are interested not only in add method, but as well the get method to be faster. In that case next bullet may be considered as a faster solution in specific patterns of Key data.
Faster then Dictionary and SortedList(int) can only be just pure Static/Dynamic Generic type of Array Array<String>... but it is a trade-off of BIG O(N): time / space.
Explaining:
a.1) Dictionary can get values in O(1) (if there are no many collision of hash values!)
a.2) Dictionary add is sometimes O(1) and sometimes O(n). so if you add one item after another, then roughly for every next element index equal to next prime number you would receive a time complexity of O(n) which is bigger just 0(1). Source: Understanding Generic Dictionary in-depth
b.1) Array Element is accessed simply by int index value in pre-allocated memory segment...
Array[Index] ( Time Complexity = O(1) ).
hence it is always faster than following operations in case of dictionary: LoopSearchInEntryListTargetElement(TransformToBucketArrayIndex(GetHashCode()))
Entry List may be iterated from 1 to 100 cycles in case of collisions.
b.2) Setting a Value to Array is as well just an int type value assignment operations in memory ( Time Complexity O(1) ).
in case of Dictionary this would sometimes require resize and/or reorganize.
In your case: if you know that all distinct values of key string are not more then some uint.MaxValue (Unsigned 32-bit integer) (in 32 bit environment) and Maximum length of String of Any Key is NOT MORE then 4 (assuming that charset is from char(0) to char(255) ) --> You could easily transform any of that type of String to corresponding int value (used as an Index in our Array<string>) for Writing or Reading a String value fastest way possible.
That would always be O(1) time complexity for both Getting and/or Assigning a Value in Array. (Contains(TKey) could be written as TKeyValueArray[index] != NULL !Note: if TValues can be null as well in your scenario, then create a custom class or generic type of structure similar to KeyValuePair but with additional boolean field - Flag Set or NotSet)
Rough Example (hint): take byte code and do simple math for each char byte code from string index [0, 1, 2, 3]
(
index =
SomeKeyString [ 0 ] * 256 * 256 * 256
+ SomeKeyString [ 1 ] * 256 * 256
+ SomeKeyString [ 2 ] * 256
+ SomeKeyString [ 3 ]
)
the formula and approach can be optimized per case (if strings have only Latin 1 Alphabet Characters then there is no need to use as much memory or you can have more lengthy TKey strings represented in your array).
this is in case of desperate need of performance.
*Latin 1 Alphabet uses 191 characters
ISO 8859-1 encodes what it refers to as "Latin alphabet no. 1", consisting of 191 characters from the Latin script... *
Sorry for just providing not thoroughly explained hints, I will try to provide more detailed answer in case of interest.
Also please read this
Initial capacity of collection types, e.g. Dictionary, List
