If your Java app feels slow and blaming the database sounds too expensive you probably have a LinkedList doing membership checks like it owes money. Java Flight Recorder or JFR will point the finger fast. The real story is simple and ugly. LinkedList does linear scans for contains which creates lots of node objects and forces the garbage collector to work overtime. HashSet trades some hashCode and equals work for near constant time lookups and far fewer allocations for large collections.

How LinkedList becomes a performance trap

LinkedList is faithful to sequential access and insertions at the ends. It is terrible for membership heavy workloads. contains on a LinkedList is O(n) which means every call walks nodes and touches memory in a cache unfriendly way. Each node is an extra object so allocation churn goes up and garbage collection gets invited to the party.

Why that matters for throughput

More allocations mean more GC pauses or more work per cycle. That reduces application throughput and increases latency. HashSet does more CPU per lookup because of hashCode and equals but it avoids the repeated O(n) scans and the node allocations that trigger the GC machinery. For large sets HashSet wins almost every time.

What Java Flight Recorder will show you

Run JFR under a realistic load and look at method samples and allocation stacks. You will see hot contains calls in the samples and node allocations in the allocation stacks when LinkedList is guilty. If HashSet is used instead you will still see hashCode and equals activity but far fewer allocations and fewer samples tied to list traversal.

Common causes of the problem

• Using LinkedList for frequent contains queries
• Not presizing HashSet which causes repeated rehashing and growth costs
• Expensive or inconsistent hashCode and equals implementations

Quick fixes that actually work

• Replace LinkedList with HashSet when you only care about membership. Your CPU may grumble but your GC will thank you.
• Use ArrayList when you need indexed reads and sequential access for better cache friendliness.
• Create a HashSet with an expected size using new HashSet(expectedSize) to reduce rehashing and allocation churn.
• Optimize hashCode and equals by simplifying logic or caching results when it is safe to do so.
• Consider primitive friendly collections from libraries like fastutil when primitives dominate to avoid boxing overhead.

How to verify your changes with profiling

• Record a realistic load with Java Flight Recorder and save the recording.
• Inspect method samples and allocation stacks to find the hottest contains calls and allocation sites.
• Change the data structure or presize your collection and repeat the recording.
• Compare allocation counts and sample hotspots to confirm improvement.

Profiling guided changes beat random guessing unless you enjoy surprises in production. Presizing HashSet and improving hashCode often give the biggest wins for collections heavy workloads. If you want a small win with big bragging rights run JFR and point at the flame graph while colleagues guess that increasing the heap will fix everything.