.NET Collections - Capacity [modified]

[devvvy]

How come there's no such properties as "List|Dictionary.Capacity" - and, does anybody knows if inserting to last slot what's dotnet Collection behavior? Allocate 2xCapacity? In absence of MyDict.Capacity, how can I manipulate this? Also, when you insert an element if Reference type into collection class, Collection class only stores a "Pointer" or "Reference", not a "Copy" IDictionary SomeDict = new Dictionary<SomeClass, string>(MAXITEMS); SomeClass o = new SomeClass(); o.a = -1; o.b = -1; o.c = -1; o.d = -1; SomeDict.Add(o, Guid.NewGuid().ToString()); Observer this on debugger: *o *SomeDict.ElementAt(0).Key They'd give you same reference. So, I'm not quite sure why I'd pick a LinkedList over a Dictionary - my guess is, Dictionary's Hash table in the back is still one contiguous block of memory, where as LinkedList is not (but also because it's slots of memory all over the place, access is slower?) But there's no MSDN doc or article which describes this (For example, LinkedList references to payload/elements are stored in usual "array" of reference? If so it too has allocation problem if you keep adding). So really is allocation the only concern? Thanks Good reference but a bit unclear in some respect...[^] Another discussion[^]

dev

modified on Monday, April 25, 2011 7:16 AM

[Luc Pattyn]

There is List<T>.Capacity[^]. You can add elements till Count equals Capacity before the internal array gets resized automatically. This[^] might interest you. There isn't a Capacity for hash-based collections, as it wouldn't be very meaningful; what can be added to a Dictionary, without growing it, depends on the current situation of the buckets and the hash value of the new entries. [ADDED AFTER OP GOT MODIFIED] Yes, a collection of reference types stores references. Form.Controls contains the (references to) the Controls of a Form, storing a copy of the Controls would be quite useless as the copy would become stale pretty soon, and changing a property would be irrelevant to the Form. As far as storage goes, there are three types of collections: - the regular ones, not hash-based, such as List, SortedList, Set, ...; they internally have a single array. - the dictionary ones, based on hashing; they use a more complex scheme to improve the search performance. - the linked-list ones; they store individual items, without using arrays. If you're interested, google "skip list" and/or read A Skip List in C#[^] [/ADDED] :)

Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum

Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.

[devvvy]

Thanks Luc, but for Dictionary, it's internal Hash table still needs to be stored some where right? I presume allocation resembles that of IList - i.e. a dict would allocate a block of contigious memory where hash+reference to actual elements are stored. (i.e. if you keep adding to it, eventually it'd reach "Capacity" specified by Dictionary's constructor) Further if LinkedList does the same internally, sounds to me real difference between SortedDictionary and LinkedList, don't you think? (LinkedList needs to store an array of references some where and in which case it must have fixed size, unless internally it uses a List). Forgot to say, both Dictionary and LinkedList supports "ElementAt($INDEX$)", but LinkedList cannot do lookup by Key

dev

[Luc Pattyn]

I suggest you look up "linked list" and "hash table" in Wikipedia, or in a relevant book. The former is normally not implemented with an array, the latter probably uses an array and more. And if you need to know the details of the (current) implementation in .NET, read the documentation and investigate using a tool such as Reflector. :)

Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum

Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.

[devvvy]

hum... I implemented/handcoded linked list before when I was doing C++, just want to know how it's done in dot net, internally (And hopefully don't have to observe on debugger for everything...)

dev

[devvvy]

Further, note LinkedList constructor - you may not specify Capacity (Suspect internal when you add an element SomeClass to the list, LinkedList class would wrap it inside a "Node" object, and node object would have reference to "Next" node. (It's a double linked list behind the scene)[^] Dictionary - you *can* specify capacity (I suspect therefore when inserting to last slot, reallocation would occur - not sure grow by how much however.)

dev

modified on Monday, April 25, 2011 7:59 AM

[AspDotNetDev]

devvvy wrote:

I suspect therefore when inserting to last slot, reallocation would occur - not sure grow by how much however.

I think dictionaries are typically implemented to grow once a certain percent of capacity has been reached, though "capacity" would be somewhat of a misnomer. So maybe once the array is at least 70% full, then it resizes (read about load factor). Also, dictionaries don't need to resize, as they typically contain collision lists... the resizing is done for performance. As far as how much they would grow, that would probably be some constant multiplier (e.g., by 2x each growth). Some implementations allow you to specify these values (growth factor and resize threshold). If you want to see how .Net implements the Dictionary class, I recommend using Reflector or ILSpy. You might also consider monitoring your memory usage with very large dictionaries. The MSDN documentation might also contain some info about the constants used.

Chris Maunder wrote:

Fixign now.

But who's fixing the fixign?

[AspDotNetDev]

devvvy wrote:

I'm not quite sure why I'd pick a LinkedList over a Dictionary

Linked lists and dictionaries are very different data structures. Linked lists contain a list of items. Dictionaries contain a bag of key/value pairs. Linked lists are typically ordered by the order items are inserted. You typically access items in a linked list by nodes (current, next, first). In a dictionary, you access values using a key. Dictionaries may use an array and a bunch of linked lists to store data internally. Linked lists will typically use independent nodes that point to other nodes (i.e., nodes are linked using pointers). As far as why you would choose one over the other, there are plenty of reasons for that (e.g., random access time for a certain element).

Chris Maunder wrote:

Fixign now.

But who's fixing the fixign?

[Jason Christian]

One of the reasons the implementation details are not in the documentation, is because they can change with new versions of .NET. The implementation details are intentionally hidden from the user so they can be modified/improved if needed, while providing the same external functionality (and general performance characteristics). If you want to explore the details of the implementation for a particular version of .NET, then Reflector/ILSpy/etc is the way to go. But don't count on those details to be the same in the next release.

[Charvak Karpe]

AspDotNetDev wrote:

Linked lists are typically ordered by the order items are inserted.

That may be the case, since I'm not sure about "typical" usage. However, linked lists have the special feature that it is easy to insert elements in the middle. Therefore, I'd argue that they aren't ordered by insertion order. An array seems more likely to have elements ordered by order of insertion. But I'm surprised nobody before you pointed out how different linked lists and dictionaries are in terms of algorithmic efficiency and functionality.