.net collection for fast insert/delete

Question

I need to maintain a roster of connected clients that are very shortlived and frequently go up and down. Due to the potential number of clients I need a collection that supports fast insert/delete. Suggestions?

Answer 1

Consider the hash-based collections for this, e.g. HashSet, Dictionary, HashTable, which provide constant time performance for adding and removing elements.

More information from the .NET Framework Developer's Guide:

• Hashtable and Dictionary Collection Types
• HashSet Collection Type

Answer 2

You could use a Hashtable or strongly typed Dictionary<Client>. The client class might override GetHashCode to provide a faster hash code generation, or if using Hashtable you can optionally use an IHashCodeProvider.

Answer 3

How do you need to find the clients? Is a Tuple/Dictionary necessary? You're more than likely to find something that solves your problem in the Jeffrey Richter's Power Collections library which has lists, trees, most data structures you can think of.

Answer 4

Well, how much do you need to query it? A linked-list has fast insert/delete (at any position), but isn't as quick to search as (for example) a dictionary / sorted-list. Alternatively, a straight list with a bit/value pair in each - i.e. "still has value". Just re-use logically empty cells before appending. Delete just clears the cell.

For reference types, "null" would do here. For value-types, Nullable<T>.

Answer 5

I was very impressed by the Channel9 interview with Peter Sestoft:

channel9.msdn.com/shows/Going+Deep/Peter-Sestoft-C5-Generic-Collection-Library-for-C-and-CLI/

He is a professor at the Copenhagen IT University who helped to create the The C5 Generic Collection Library:

www.itu.dk/research/c5/

It might be overkill or it might be just the speedy collection you were looking for ...

hth,

-Mike