Search code examples
c#data-structuresidentity-map

What is the best structure to implement an Identity Map?

Although a DataTable is a memory hog, wouldn't a DataTable be the best choice to implement and IdentityMap if the set of objects is very large since retrieval time is O(1)?

Update

If I decide to use IDictionary, do I sacrifice speed when retrieving my objects?

Solution

  • Any of Dictionary<,>, SortedList<,> or SortedDictionary<,> would be obvious choices - but note tha sorting becomes an issue here... Dictionary<,> doesn't guarantee any particular order; the other two order by the keys rather than insertion order.

    Note also that dictionary won't play very nicely with data-binding. It might be preferable to create something like a Collection<T>, but encapsulate a Dictionary<,> for lookups. It all depends on the scenario, of course.

    More information on the performance etc differences between SortedList<,> etc can be found here.