У хеш таблицы есть две особенности, которые делают ее особенной структурой данных: возможность хранить данные в формате ключ-значение и быстродействие, в среднем все операции занимают константное время O(1).

Большинство хешей построены на базе массивов и специальной хеш-функции. Массивы позволяю почти моментально получать данные по индексу, а хеш-функция позволяет вычислить индекс в этом массиве на основании ключа.

Хеш-функция и коллизии
Хорошая хеш-функция должна давать как можно меньше коллизий, равномерно распределять ключи по хешу и должна быть последовательной. То есть для одинакового ключа должен быть одинаковый хеш.

Коллизии возникают когда для разных ключей генерируется одинаковый хеш. Такая ситуация является вполне нормальной, потому-что невозможно создать идеальную хеш функцию.

Самый простой и популярный способ работы с коллизиями является использование в качестве значения в массиве связанные список. В таком случае если элементы будут иметь одинаковый хеш, то они просто складываются в этот список.

Потом когда нам нужно получить значение по ключу, то сначала мы вычисляем хеш и находим нужную ячейку в массиве. Потом мы проходимся по связанному списку и находим значение для нужного нам ключа. Но в случае коллизий скорость работы хеша может упасть до O(n). Потому что поиск элемента в массиве занимает O(1), но вот поиск по связанному списку — O(n).

Коэффициент заполнения
Показывает насколько заполнена хеш-таблица, он используется для того чтобы знать когда увеличивать внутренний массив. Считается как отношение между количеством элементов в таблице и общей вместительностью. Оптимальным считается значение 0.7, если оно больше, то нужно увеличивать внутренний массив.

Когда использовать?

• Для хранения данных в виде ключ-значения.
• Для исключения дубликатов. С помощью хеш-таблицы можно очень эффективно находить дубликаты.
• Для реализации разных словарей и кэша.

Простая реализация: What is an example of a Hashtable implementation in C#?