All 16 Collections questions
More in Collections
How does Queue<T> differ from Stack<T> in terms of the order items are removed? What is the difference between IEnumerable<T>, ICollection<T>, and IList<T> in the collection interface hierarchy? When would you reach for a ConcurrentDictionary or an immutable collection? How do you avoid multiple enumeration of an IEnumerable? What is the performance and thread-safety difference between ConcurrentDictionary<TKey,TValue> and a regular Dictionary<TKey,TValue> guarded by a manual lock? How would you choose between List<T>, LinkedList<T>, and ImmutableList<T> based on their different Big-O characteristics for common operations? How does the 'yield return'-based lazy evaluation of collections (like LINQ or a custom iterator) differ from eagerly materializing a full collection, in terms of memory usage? How would you implement a custom, strongly-typed, read-only wrapper around a mutable collection to safely expose it from a class's public API?
Advertisement
Back to results for “Performance”
C# › Collections

How does Dictionary<TKey,TValue> handle hash collisions internally, and why does a poor GetHashCode() implementation degrade its performance?

Advanced

Answer

Dictionary<TKey,TValue> uses a hash table with SEPARATE CHAINING (or a similar bucket-based collision resolution) — when multiple keys hash to the same bucket, it falls back to a linear scan WITHIN that bucket using Equals(); a poorly-distributed GetHashCode() (e.g., one that always returns the same value) collapses the theoretical O(1) average lookup into effectively O(n), since every key lands in the same bucket.
public class BadKey {
  public override int GetHashCode() => 1; // terrible: every instance collides into the same bucket
}
// A Dictionary<BadKey, T> degrades to O(n) linear-scan performance
Real-world example Debugging a mysteriously slow Dictionary-based cache traced back to a custom key type with a poorly-implemented GetHashCode().

Common follow-ups: What's the contractual relationship that GetHashCode() and Equals() must maintain for a custom key type to work correctly?

Equality: Equals GetHashCode & IEquatable
All 16 Collections questions