Как работает хеш-таблица (Dictionary) и почему она быстрее для поиска?

Question

Dictionary использует:Хеш-функцию для преобразования ключа в индексМассив "ведёрок" (buckets)Разрешение коллизий через цепочкиПоиск за O(1) в среднем случае.

YeaHub · Accepted Answer

Принцип работы:Хеширование ключа:int index = key.GetHashCode() % buckets.Length;Хранение данных:buckets[0] → null
buckets[1] → [key1/value1] → [key2/value2] → null
buckets[2] → [key3/value3] → nullПоиск:Вычисляем хеш ключаИдём по цепочке в нужном bucketПример коллизии:var dict = new Dictionary<string, int>();
dict.Add("abc", 1); // Хеш 123 → bucket 3
dict.Add("cba", 2); // Хеш 123 → bucket 3 (коллизия)