Dictionary<key,item> trimming internally

[John Rivers]

I was playing around with using Dictionary<> to implement a sparse
array

using something like

class Key { byte x, y, z; }

where the "space" is 16,777,216 entries
but there are only ever going to be maximum of 10,000 entries

but it seems to me the internal hash array only grows - it never
shrinks

looking at the code with reflector shows a private Resize() method
that only
grows the number of buckets

ideally I would like something that would automatically recycle
buckets
and so not generate any garbage

any ideas?

 

[Peter Duniho]

[...]
where the "space" is 16,777,216 entries
but there are only ever going to be maximum of 10,000 entries

but it seems to me the internal hash array only grows - it never
shrinks
[...]
ideally I would like something that would automatically recycle
buckets
and so not generate any garbage

any ideas?

Leave it alone.

Hash tables need a capacity that's somewhat larger than the number of
contained elements, for efficiency.

Collection classes in .NET don't generally trim capacity automatically
anyway, and the hashing classes in particular I would not expect to
provide that functionality in any way, as they need finer control over
the capacity relative to the number of contained elements.

If you want a hashing collection for which you can force a specific
number of hash buckets, you'll have to write your own. I suspect if you
do, you'll find it's a non-trivial problem to achieve the same
performance efficiency as the built-in classes, while still offering the
feature you want.

As far as the sparse array application goes, IMHO a hashing data
structure isn't really necessarily that ideal for the job anyway.
Performance can be good, but it's wasteful, even for other reasons
(hashing collections have more overhead as compared to others). If you
really have elements so far apart that a sparse array is a worthwhile
optimization, it's probably best to abstract the sparseness and store
the data in a regular array or perhaps a linked list. A hashing
collection is convenient, and will perform well, but will quickly use up
whatever space savings the sparse array might have achieved in the first
place.

Obviously this is application-dependent, but it's definitely something
to consider.

Pete

 

[John Rivers]

thanks for the reply

and good advice - I was worrying unnecessarily

I did some testing on the Dictionary<> with large data sets

and it behaves very well - the hash buckets look after themselves
because of

bucket = hash % bucketCount

and the entry structures are recycled - so once it has reached the
peak size
it doesn't grow any further - actually exactly what I wanted

my usage will have a very high frequency "churn" of items

in a way I wish it exposed something like LinkedListNode<> so the
memory
would manage itself automatically (I have a large fixed set of objects
moving between keys)