Skip to main content

HashSet<T> vs .Net 4.0 SortedSet<T>

HashSet<T> has been there for a while, it can store objects in such a way that the time to add an item to the set or remove it or search for an item is O(1), constant time.
It uses hash based implementation to achieve this constant time for these operations, however when you want to iterate this collection in a sorted way, the operation is intensive, as the values within the HashSet is not sorted, you need to create a sorted collection and then iterate this collection.
As the values are stored within the collection indirectly based on hash, the sort operation is expensive and also a new collection has to be created.

This is where SortedSet<T> comes into play, this collection type was introduced in .Net 4.0, when you add item to this collection, the item is placed in the collection according to the sort criteria, thus when you need to iterate this sorted collection, it is much faster then the HashSet.

SortedSet has it's own cons, now that the items has to be placed in the correct position in the collection according to the sort order the Add() operation and Remove() operation don't take constant time anymore.

Searching for an element, would mean that a binary search has to be done on the collection which is logarithmic time.

The conclusion is that these Sets can be used accordingly to the requirements that you have and you are not forced to choose one collection over the other, if you need to iterate over a sorted collection, then a SortedSet would be the best choice.

.Net 4.0 also introduces the ISet<T> interface, both HashSet and SortedSet implements this interface, so you can always program to an interface and change your type in the middle of the implementation if you feel HashSet would do better then SortedSet.

Btw, why do you need to use sets anyways ?, cos' then they can be manipulated with set operation like Union, Intersect etc.. and that they can contain only unique elements.

Comments

Popular posts from this blog

Hosting WCF services on IIS or Windows Services?

There came one of those questions from the client whether to use II7 hosting or windows service hosting for WCF services. I tried recollecting a few points and thought of writing it down. WCF applications can be hosted in 2 main ways - In a Windows service - On IIS 7 and above When WCF was first released, IIS 6 did not support hosting WCF applications that support Non-HTTP communication like Net.TCP or Net.MSMQ and developers had to rely on hosting these services on Windows Services. With the release of IIS 7, it was possible to deploy these Non-Http based applications also on IIS 7. Following are the benefits of using IIS 7 to host WCF applications Less development effort Hosting on Windows service, mandates the creating of a Windows service installer project on windows service and writing code to instantiate the service, whereas the service could just be hosted on IIS by creating an application on IIS, no further development is needed, just the service implementa

The maximum nametable character count quota (16384) has been exceeded

Some of our services were growing and the other day it hit the quote, I could not update the service references, nor was I able to run the WCFTest client. An error is diplayed saying " The maximum nametable character count quota (16384) has been exceeded " The problem was with the mex endpoint, where the XML that was sent was too much for the client to handle, this can be fixed by do the following. Just paste the lines below within the configuration section of the devenve.exe.config and the svcutil.exe.config files found at the locations C:\Program Files\Microsoft Visual Studio 9.0\Common7\IDE , C:\Program Files\Microsoft SDKs\Windows\v6.0A\bin Restart IIS and you are done. The detailed error that you get is the following : Error: Cannot obtain Metadata from net.tcp://localhost:8731/ Services/SecurityManager/mex If this is a Windows (R) Communication Foundation service to which you have access, please check that you have enabled metadata publishing at the specified address. F

ASP.NEt 2.0 Viewstate and good practices

View state is one of the most important features of ASP.NET because it enables stateful programming over a stateless protocol such as HTTP. Used without strict criteria, though, the view state can easily become a burden for pages. Since view state is packed with the page, it increases size of HTTP response and request. Fortunately the overall size of the __VIEWSTATE hidden field (in ASP.NET 2.0) in most cases is as small as half the size of the corresponding field in ASP.NET 1.x. The content of the _VIEWSTATE field (in client side) represent the state of the page when it was last processed on the server. Although sent to the client, the view state doesn't contain any information that should be consumed by the client. In ASP.NET 1.x, if you disable view state of controls, some of them are unable to raise events hence control become unusable. When we bind data to a grid, server encodes and put whole grid in to view state, which will increase size of view state (proportional to the