title: C# dictionary for large number of items
body: <p>I would like to understand the cost of storing a large number of items in the memory in C#. The data structure I need to use is a dictionary or similar. Let's say the number of items I would like to have is around 100 million, but the application will not immediately reach that number. It will take a long time till we are on the order of the limit.</p>
  
  <p>I'm worried about the cost of operation that is amortised, but which I cannot afford to be too expensive at any given moment. So usually with dynamic data structures, when the structure is full, it re-allocates itself. In case of dictionary, I think it will even reindex every item. So let's say we are the point that application maintains 20 million items which just reaches the capacity of the dictionary. Then when a new dictionary storage is allocated, those 20 million items needs to be re-indexed.</p>
  
  <p>This is why I was thinking that an array of dictionaries might be a good idea. Let's say I create 256 dictionaries.This immediately puts a bound on the size of each internal dictionary to less than 1 million items, which should be manageable to build up dynamically with all the indexing happening on the way up to 1 million items. The cost of that seems to be just one extra indexation per operation to find the correct dictionary to look into.</p>
  
  <p>Is this a reasonable approach? Is my analysis correct or will the C# dictionary perform better I think for some reason? Is there any other solution that would be better? I'm looking for a data structure that has the same time complexity as C# dictionary.</p>
  
  <p>Edit: The dictionary key is a random value, so I can just take the first bite of it to find my index into the array of 256 dictionaries very cheaply.</p>
  
  <p>I'm currently not considering a database as I want all the items to be immediately available with very little cost. I do need look up in constant time with very little overhead. I can afford insert to be slower, but still constant time. Same with delete, can be little slower, but constant time required.</p>
  
  <p>It should be possible to fit all the items in the memory. The items are small, about 50 bytes of data each. So the data structure must not have too much of an overhead for each item.</p>