Returning a collection of unique elements: List<T> using Contains() or HashSet<T>

Question

I'm writing a binary PowerShell module and have recently started to add wildcard support to some cmdlets.

I'm not sure if I'm using an efficient way of creating the final collection of objects to write back to the pipeline.

I'm wondering if it might be slightly more efficient to use a HashSet<T> rather than a List<T> in this case, even though I've been told that Contains() doesn't have a large overhead on small collections (the final collection would can contain anywhere from 0 to ~25 elements).

Is List<T> appropriate in this case or should I try and use a HashSet<T> instead?

[Cmdlet(VerbsCommon.Get, "DatabaseUser")]
[Alias("gdbu")]
[OutputType(new Type[] { typeof(User)})]
public class GetDatabaseUserCmdlet : PSCmdlet
{
    [Parameter(ValueFromPipeline = true, 
               ValueFromPipelineByPropertyName = true, 
               ValueFromRemainingArguments = true)]
    public string[] Name { get; set; }

    [Parameter]
    public SwitchParameter IncludeSystemAccounts{ get; set; }

    List<User> _users = new List<User>();
    Hashtable _privateData;
    Server _server;
    Database _database;

    protected override void BeginProcessing()
    {
        _privateData = (Hashtable)MyInvocation.MyCommand.Module.PrivateData;
        _server = new Server((string)_privateData["Server"]);
        _database = _server.Databases[(string)_privateData["Database"]];
    }

    protected override void ProcessRecord()
    {
        var users = _database.Users.Cast<User>();

        if(IncludeSystemAccounts.IsPresent == false)
        {
            users = users.Where(user => user.IsSystemObject == false);
        }

        if (Name == null)
        {
            _users = users.ToList();
        }
        else
        {
            foreach(var item in Name)
            {
                var wildcard = new WildcardPattern(item, WildcardOptions.IgnoreCase);
                var result = users.Where(user => wildcard.IsMatch(user.Name));
                if(result != null)
                {
                    foreach(var user in result)
                    {
                        if(_users.Contains(user) == false)
                        {
                            _users.Add(user);
                        }
                    }
                }
            }
        }
    }

    protected override void EndProcessing()
    {
        WriteObject(_users);
    }
}

To give an example of how this cmdlet functions. Assume my database has 10 users: named User1 through User10 (not counting dbo, sys, etc.).

If I call the cmdlet like so:

Get-DatabaseUser -Name user[135], user[2-4] | Format-Table -Property Name

This is the expected (and actual result):

Name
----
User1
User3
User5
User2
User4

Answer 1

Checking if an item exists in a list or a hashset has very different order of complexity:

• \$O(N)\$ in a list: all items are checked one by one until a match is found. If no match, the entire list will be scanned
• (amortized) \$O(1)\$ in a hashset: calculate hashcode, check if it exists

With today's computers, the performance with ~25 elements should be virtually the same. Even if you had a 1000 elements, you might still not notice a difference. If in doubt, measure it.

Note that converting the list to a hashset would have the consequence of losing the ordering. An alternative could be a SortedSet, if you don't mind sorting instead of ordering. For a data structure that preserves ordering and the time complexity of hashset operations, you could consider a linked hashset implementation discussed for example here.

To conclude, if you know you will only ever have few entries (< 1000), the performance difference won't be noticeable. However, as a matter of principle, it might be a good idea to use a hashset anyway, especially if you don't care about the order of entries. A sorted set would be even better, to have consistent ordering, and fewer surprises.

---

You use the boolean literal false at many places, for example:

if(IncludeSystemAccounts.IsPresent == false)
{
    users = users.Where(user => user.IsSystemObject == false);

It's more natural to not use boolean literals like this, but write instead:

if (!IncludeSystemAccounts.IsPresent)
{
    users = users.Where(user => !user.IsSystemObject);