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

Доступ к элементам осуществляется по его ключу. Основные операции, которые могут выполняться с хеш-таблицей?
- Insert — добавить новый элемент в хеш-таблицу
- Delete — удалить элемент из хеш-таблицы по ключу
- Search — получить значение по ключу
Подпишись на группу Вконтакте и Телеграм-канал. Там еще больше полезного контента для программистов.
А на YouTube-канале ты найдешь обучающие видео по программированию. Подписывайся!
Основной принцип работы хеш-таблицы заключается в том, что в качестве входных параметров она принимает пары ключ-значение. Затем с помощью специальной хеш функции получает короткий ключ на основе полученного ключа. И наконец добавляет данные в таблицу. Если в таблице уже существует значения с таким хешем, то объединяет их в коллекции. Внутри коллекции поиск выполняется по изначальному полученному ключу.
Теперь приступим к реализации данной структуры данных. Для простоты будем рассматривать структуру из пары двух строк. Данная реализация является весьма примитивной, но позволяет разобраться в структуре и алгоритме работы данного типа данных.
Элемент данных хеш-таблицы
using System; namespace HashTable { /// <summary> /// Элемент данных хеш таблицы. /// </summary> public class Item { /// <summary> /// Ключ. /// </summary> public string Key { get; private set; } /// <summary> /// Хранимые данные. /// </summary> public string Value { get; private set; } /// <summary> /// Создать новый экземпляр хранимых данных Item. /// </summary> /// <param name="key"> Ключ. </param> /// <param name="value"> Значение. </param> public Item(string key, string value) { // Проверяем входные данные на корректность. if(string.IsNullOrEmpty(key)) { throw new ArgumentNullException(nameof(key)); } if(string.IsNullOrEmpty(value)) { throw new ArgumentNullException(nameof(value)); } // Устанавливаем значения. Key = key; Value = value; } /// <summary> /// Приведение объекта к строке. /// </summary> /// <returns> Ключ объекта. </returns> public override string ToString() { return Key; } } }
Хеш-таблица
using System; using System.Collections.Generic; using System.Linq; namespace HashTable { /// <summary> /// Хеш-таблица. /// </summary> /// <remarks> /// Используется метод цепочек (открытое хеширование). /// </remarks> public class HashTable { /// <summary> /// Максимальная длина ключевого поля. /// </summary> private readonly byte _maxSize = 255; /// <summary> /// Коллекция хранимых данных. /// </summary> /// <remarks> /// Представляет собой словарь, ключ которого представляет собой хеш ключа хранимых данных, /// а значение это список элементов с одинаковым хешем ключа. /// </remarks> private Dictionary<int, List<Item>> _items = null; /// <summary> /// Коллекция хранимых данных в хеш-таблице в виде пар Хеш-Значения. /// </summary> public IReadOnlyCollection<KeyValuePair<int, List<Item>>> Items => _items?.ToList()?.AsReadOnly(); /// <summary> /// Создать новый экземпляр класса HashTable. /// </summary> public HashTable() { // Инициализируем коллекцию максимальным количество элементов. _items = new Dictionary<int, List<Item>>(_maxSize); } /// <summary> /// Добавить данные в хеш таблицу. /// </summary> /// <param name="key"> Ключ хранимых данных. </param> /// <param name="value"> Хранимые данные. </param> public void Insert(string key, string value) { // Проверяем входные данные на корректность. if (string.IsNullOrEmpty(key)) { throw new ArgumentNullException(nameof(key)); } if (key.Length > _maxSize) { throw new ArgumentException($"Максимальная длинна ключа составляет {_maxSize} символов.", nameof(key)); } if (string.IsNullOrEmpty(value)) { throw new ArgumentNullException(nameof(value)); } // Создаем новый экземпляр данных. var item = new Item(key, value); // Получаем хеш ключа var hash = GetHash(item.Key); // Получаем коллекцию элементов с таким же хешем ключа. // Если коллекция не пустая, значит заначения с таким хешем уже существуют, // следовательно добавляем элемент в существующую коллекцию. // Иначе коллекция пустая, значит значений с таким хешем ключа ранее не было, // следовательно создаем новую пустую коллекцию и добавляем данные. List<Item> hashTableItem = null; if (_items.ContainsKey(hash)) { // Получаем элемент хеш таблицы. hashTableItem = _items[hash]; // Проверяем наличие внутри коллекции значения с полученным ключом. // Если такой элемент найден, то сообщаем об ошибке. var oldElementWithKey = hashTableItem.SingleOrDefault(i => i.Key == item.Key); if (oldElementWithKey != null) { throw new ArgumentException($"Хеш-таблица уже содержит элемент с ключом {key}. Ключ должен быть уникален.", nameof(key)); } // Добавляем элемент данных в коллекцию элементов хеш таблицы. _items[hash].Add(item); } else { // Создаем новую коллекцию. hashTableItem = new List<Item>{ item }; // Добавляем данные в таблицу. _items.Add(hash, hashTableItem); } } /// <summary> /// Удалить данные из хеш таблицы по ключу. /// </summary> /// <param name="key"> Ключ. </param> public void Delete(string key) { // Проверяем входные данные на корректность. if (string.IsNullOrEmpty(key)) { throw new ArgumentNullException(nameof(key)); } if (key.Length > _maxSize) { throw new ArgumentException($"Максимальная длинна ключа составляет {_maxSize} символов.", nameof(key)); } // Получаем хеш ключа. var hash = GetHash(key); // Если значения с таким хешем нет в таблице, // то завершаем выполнение метода. if (!_items.ContainsKey(hash)) { return; } // Получаем коллекцию элементов по хешу ключа. var hashTableItem = _items[hash]; // Получаем элемент коллекции по ключу. var item = hashTableItem.SingleOrDefault(i => i.Key == key); // Если элемент коллекции найден, // то удаляем его из коллекции. if (item != null) { hashTableItem.Remove(item); } } /// <summary> /// Поиск значения по ключу. /// </summary> /// <param name="key"> Ключ. </param> /// <returns> Найденные по ключу хранимые данные. </returns> public string Search(string key) { // Проверяем входные данные на корректность. if (string.IsNullOrEmpty(key)) { throw new ArgumentNullException(nameof(key)); } if (key.Length > _maxSize) { throw new ArgumentException($"Максимальная длинна ключа составляет {_maxSize} символов.", nameof(key)); } // Получаем хеш ключа. var hash = GetHash(key); // Если таблица не содержит такого хеша, // то завершаем выполнения метода вернув null. if(!_items.ContainsKey(hash)) { return null; } // Если хеш найден, то ищем значение в коллекции по ключу. var hashTableItem = _items[hash]; // Если хеш найден, то ищем значение в коллекции по ключу. if (hashTableItem != null) { // Получаем элемент коллекции по ключу. var item = hashTableItem.SingleOrDefault(i => i.Key == key); // Если элемент коллекции найден, // то возвращаем хранимые данные. if (item != null) { return item.Value; } } // Возвращаем null если ничего найдено. return null; } /// <summary> /// Хеш функция. /// </summary> /// <remarks> /// Возвращает длину строки. /// </remarks> /// <param name="value"> Хешируемая строка. </param> /// <returns> Хеш строки. </returns> private int GetHash(string value) { // Проверяем входные данные на корректность. if (string.IsNullOrEmpty(value)) { throw new ArgumentNullException(nameof(value)); } if (value.Length > _maxSize) { throw new ArgumentException($"Максимальная длинна ключа составляет {_maxSize} символов.", nameof(value)); } // Получаем длину строки. var hash = value.Length; return hash; } } }
Вызов
using System; namespace HashTable { class Program { static void Main(string[] args) { // Создаем новую хеш таблицу. var hashTable = new HashTable(); // Добавляем данные в хеш таблицу в виде пар Ключ-Значение. hashTable.Insert("Little Prince", "I never wished you any sort of harm; but you wanted me to tame you..."); hashTable.Insert("Fox", "And now here is my secret, a very simple secret: It is only with the heart that one can see rightly; what is essential is invisible to the eye."); hashTable.Insert("Rose", "Well, I must endure the presence of two or three caterpillars if I wish to become acquainted with the butterflies."); hashTable.Insert("King", "He did not know how the world is simplified for kings. To them, all men are subjects."); // Выводим хранимые значения на экран. ShowHashTable(hashTable, "Created hashtable."); Console.ReadLine(); // Удаляем элемент из хеш таблицы по ключу // и выводим измененную таблицу на экран. hashTable.Delete("King"); ShowHashTable(hashTable, "Delete item from hashtable."); Console.ReadLine(); // Получаем хранимое значение из таблицы по ключу. Console.WriteLine("Little Prince say:"); var text = hashTable.Search("Little Prince"); Console.WriteLine(text); Console.ReadLine(); } /// <summary> /// Вывод хеш-таблицы на экран. /// </summary> /// <param name="hashTable"> Хеш таблица. </param> /// <param name="title"> Заголовок перед выводом таблицы. </param> private static void ShowHashTable(HashTable hashTable, string title) { // Проверяем входные аргументы. if(hashTable == null) { throw new ArgumentNullException(nameof(hashTable)); } if(string.IsNullOrEmpty(title)) { throw new ArgumentNullException(nameof(title)); } // Выводим все имеющие пары хеш-значение Console.WriteLine(title); foreach (var item in hashTable.Items) { // Выводим хеш Console.WriteLine(item.Key); // Выводим все значения хранимые под этим хешем. foreach(var value in item.Value) { Console.WriteLine($"\t{value.Key} - {value.Value}"); } } Console.WriteLine(); } } }
Заключение
На платформе .NET уже есть готовая реализация данной структуры данных. Она содержится в пространстве имен System.Collections и называется аналогично Hashtable. Исходный код доступен в репозитории github https://github.com/shwanoff/HashTable.
Также рекомендую прочитать статью Словарь (map) C#, которая также очень тесно связана с данной темой. А еще подписывайтесь на группу ВКонтакте, Telegram и YouTube-канал. Там еще больше полезного и интересного для программистов.