What is the best structure to implement an Identity Map?

Question

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?

Answer 1

I'd be more inclined to use a custom class backed by a Dictionary<T,T> than a DataTable. Presumably this would be built on top of a data access layer that could use LINQ or DataTables, etc. to access the relational data, but if the object is available in the custom map, you would at least avoid having to reconstitute it from the relational data.

Answer 2

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.