Why does this check get slower over time?

A List searches. A HashSet knows.

Why does this check get slower over time?

The problem

Contains walks the whole list.

List<string> _found = new(); void Pickup( string id ){    if ( _found.Contains( id ) ) return;     _found.Add( id );    GiveReward( id );}

Every call compares id against every item so far. More items, more work.

Why it happens

A List has no idea where things are.

A HashSet files each item by its hash, so it can go straight to where an item would be.

List.Contains
checks item by item
HashSet.Contains
goes straight to it
10,000 items
10,000 checks, or about 1

The fix in code

Same code, different collection.

HashSet<string> _found = new(); void Pickup( string id ){    if ( !_found.Add( id ) ) return;     GiveReward( id );}

Add returns false if it was already there, so the check and the add are one call.

Watch out

When a List is still right.

A HashSet keeps no order and no duplicates.

Order or duplicates
List
Fast Contains
HashSet
A value per key
Dictionary

The rule

Asking "is it in there?" Use a HashSet.

Is it in there?
HashSet.Contains
Add if new
if ( set.Add( x ) )
Order matters
List