Is this O(1) when I use the hashset?

Question

I have a HashSet of a type:

public Class Person
{
    int? _requestedHashCode;
    long Id;
    Name string;
    DateTime BirthDate;
    // Other properties


    public bool IsTransient()
    {
        return this.Id == default(long);
    }


    public override int GetHashCode()
    {
        if (!IsTransient())
        {
            if (!_requestedHashCode.HasValue)
                _requestedHashCode = this.Id.GetHashCode() ^ 31;

            return _requestedHashCode.Value;
        }
        else
            return base.GetHashCode();
    }


    public override bool Equals(object obj)
    {
        if (obj == null || !(obj is Person))
            return false;

        if (Object.ReferenceEquals(this, obj))
            return true;

        if (this.GetType() != obj.GetType())
            return false;

        Entity item = (Entity)obj;

        if (item.IsTransient() || this.IsTransient())
            return false;
        else
            return item.Id == this.Id;
    }
}

I have a method that receives as parameter the ID of the person, and I would like to get the person with O(1) performance:

public Person GetPerson(long paramIdPersonToDelete)
{
    return _myHashset.FirstOrDefault(x => x.Id == paramIdPersonToDelete);
}

Is my implementation correct? I am not sure what I need to modify; the comparison that needs the HashSet, if the HashSet uses GetHashCode(), or Equals() or both.

Thanks.

`FirstOrDefault` is always O(n), you are enumerating the HashSet — Tim Schmelter, Jun 16 '23 at 15:39
`FirstOrDefault(x => x.Id == paramIdPersonToDelete)` is not an O(1) operation. This will iterate through the HashSet till it finds a **Person** with the matching **Id**. In your case it would make more sense to use a `Dictionary`. You could format it like this: `Dictionary`. — AztecCodes, Jun 16 '23 at 15:45
Side note: I highly doubt the extra cost of the `if (!_requestedHashCode.HasValue)` is worth it. Just change the whole GetHashcode to `return this.Id.GetHashCode() ^ 31;` — Charlieface, Jun 16 '23 at 17:45

Tim Schmelter · Accepted Answer · 2023-06-16T16:04:32.363

5

First or FirstOrDefault are LINQ methods(so not optimized for HashSet<T>) that need to enumerate the sequence to find an item. That means they have O(n) complexity.

If you want O(1) you could use this approach:

public Person GetPerson(long paramIdPersonToDelete)
{
    return _myHashset.TryGetValue(new Person{ Id = paramIdPersonToDelete }, out Person actualPerson)
        ? actualPerson
        : null;
}

Of course you need to make Id public or - better - provide a constructor and make it readonly.

In this case it would be better to use a Dictionary<long, Person>.

edited Jun 16 '23 at 16:04

answered Jun 16 '23 at 15:47

Tim Schmelter

450,073
74
686
939

The reason I asked it is, if I create the person setting only the Id, the rest of the properties has the default values. If I have many properties with different ID and the rest of properties with the default values, is it enough to have different ID to be O(1)? – Álvaro García Jun 16 '23 at 16:08
@ÁlvaroGarcía: Yes, that's why it might be better to use a `Dictionary` if you want a mapping between the Id and a Person. Your hashcode/equals logic seems to be more complex than simply comparing the `Id`. – Tim Schmelter Jun 16 '23 at 16:13
1

@Alvaro This might help to answer that question: [What does it mean when an operation "approaches O(1)" as opposed to "is O(1)"?](https://stackoverflow.com/questions/19989075/what-does-it-mean-when-an-operation-approaches-o1-as-opposed-to-is-o1) – ProgrammingLlama Jun 16 '23 at 16:13

score 4 · Answer 2 · answered Jun 16 '23 at 15:50

O(1) Operation with Dictionary instead of FirstOrDefault

FirstOrDefault as you used it, is not an O(1) operation. In your case a Dictionary would make way more sense.

Here is an example how you could fix it:

Code Example:

Dictionary<long, Person> people = new Dictionary<long, Person>();

// Adding a Person object to the Dictionary
Person personExample = new Person();
people.Add(personExample.Id, personExample);

// Method to look up person in dictionary by using the Id which is provided as parameter
public Person GetPerson(long paramIdPerson)
{
    if (people.TryGetValue(paramIdPerson, out Person person))
    {
        return person;
    }
    return null;
}

Is this O(1) when I use the hashset?

2 Answers2

O(1) Operation with Dictionary instead of FirstOrDefault