CODEWITHSUNDEEP
c#.netdata-structuresdictionaryhashtable
BaltoStar
BaltoStar

Reputation: 8977

possible to design a more consistently performant data structure than .NET Dictionary?

The .NET Dictionary<TKey,TValue>'s internal structure and process is a highly optimized design, as discussed by Simon Cooper in this excellent blog post.

The MSDN docs state that Add(TKey,TValue) is O(1) -- unless the Dictionary's element count is at capacity, necessitating that a dynamic resize operation first be performed, thus making Add() O(n) at these junctures.

As the Dictionary grows, resize operations become progressively more infrequent, and therefore it may be said that averaged over large n, Add() approaches O(1).

This is evidenced by Cooper in this graph of total elapsed time for n/2 add operations as a function of n.

However, the average worst case performance of Add() is O(n).

My question : Is it possible to design a more consistently performant data structure than the .NET Dictionary ?

Specifically, I want average worst case performance of add, delete, retrieve operations to all be O(1).

Note that consistency of performance ( "big O" ) is the only relevant design criteria. Memory utilization and absolute performance ( including degree of clustering & cache performance ) are not relevant design criteria.

Choosing an initial capacity much larger than anticipated needs is one option, but that is an initialization step, and I am looking for a data structure design.

Upvotes: 1

Views: 217

Answers (1)

TomTom
TomTom

Reputation: 62093

Have you simply tried creating a dictionary with a big enough size?

Generic O(1) is basically an array. Access via index. Or hierarchical arrays (4 byte key, array pointing to aray pointing to array pointing to array pretty much, to save space).

Anythig else - no, sorry.

Lots of high performance stuff uses preallocated arrays.

Upvotes: 3

Related Questions