run-dev

,

Что такое Хэш-таблица в C#?

Хэш-таблица — это структура данных, которая предоставляет быстрый доступ к данным по ключу. В C# хэш-таблицы реализуются с помощью класса Dictionary<TKey, TValue> из пространства имен System.Collections.Generic.

Принцип работы хэш-таблицы

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

Создание и использование Dictionary<TKey, TValue>

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary<int, string> dict = new Dictionary<int, string>();
        
        dict[1] = "Apple";
        dict[2] = "Banana";
        dict[3] = "Cherry";

        Console.WriteLine(dict[2]);
    }
}

Основные операции

Добавление элементов

Метод Add добавляет новую пару ключ-значение:

dict.Add(4, "Date");

Доступ к элементам

Можно получить значение по ключу:

string fruit = dict[1];

Безопасный доступ через TryGetValue:

if (dict.TryGetValue(5, out string value))
{
    Console.WriteLine(value);
}

Удаление элементов

dict.Remove(2);

Проверка наличия ключа

if (dict.ContainsKey(3))
{
    Console.WriteLine("Key exists");
}

Перебор элементов

foreach (var kvp in dict)
{
    Console.WriteLine($"{kvp.Key}: {kvp.Value}");
}

Различия Dictionary и Hashtable

  • Dictionary<TKey, TValue> типизированный, а Hashtable хранит объекты типа object.
  • Dictionary быстрее, так как не требует упаковки (boxing) и распаковки (unboxing).
  • Hashtable используется редко, предпочтение отдается Dictionary<TKey, TValue>.

Применение хэш-таблиц

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

Больше записей