Хеш-таблица (hashtable) — это структура данных, представляющая собой специальным образом организованный набор элементов хранимых данных. Все данные хранятся в виде пар «ключ-значение». Данная структура похожа на словарь (map), но имеет особенности такие как применение хеш-функции для увеличения скорости поиска. Принцип работы данной структуры схож с каталогом книг. Все книги разложены в алфавитном порядке, но не на одном стеллаже, а для каждой буквы выделен отдельный стеллаж, поэтому нам не нужно по порядку перебирать все книги, а можно подойти к нужному стеллажу и искать уже там. Давайте рассмотрим пример реализации хеш-таблицы на языке C#.

Хеш таблица (Hashtable) VS словарь (Dictionary<TKey, TValue>).

Что общего:

1. Оба работают как хранилище ключ-значение
2. Оба обеспечивают (псевдо)константный доступ к значению по ключу
3. Оба хранят данные в массиве корзин (расходы по памяти у обоих в линейной зависимости от количества элементов)

В чем разница:

1. Таблица приводит ключи и значения к object, что добавляет расходов по памяти и скорости (на boxing/unboxing)
2. Таблица, в отличии от словаря, поддерживает многопоточное чтение / однопоточную запись. Словарь же не рассчитан на несколько одновременных читателей / одного писателя (я однажды на этом запорол релиз, будьте аккуратней)
3. У таблицы есть враппер для получения потокобезопасной таблицы. У словаря я такого не увидел.
4. Таблица и словарь по разному обсчитывают коллизии. Таблица пользуется двойным хешированием, словарь хранит что то типа указателя на следующий элемент прямо в корзине (не знаю как этот метод называется). 

Хеш-функция (англ.hash function от hash — «превращать в фарш», «мешанина»^[1]), или функция свёртки — функция, осуществляющая преобразование массива входных данных произвольной длины в выходную битовую строку установленной длины, выполняемое определённым алгоритмом. Преобразование, производимое хеш-функцией, называется хешированием. Исходные данные называются входным массивом, «ключом» или «сообщением». Результат преобразования называется «хешем», «хеш-кодом», «хеш-суммой», «сводкой сообщения».

Коллизия хеш-функции — это когда у двух разных входных элементов таблицы hash будет одинаковым. Коллизии встречаются в разнообразных алгоритмах хеширования, однако это не является нормой и в «правильных» алгоритмах их возникновение сведено к минимальному значению.