Словарь (map) — это структура данных, представляющая собой специальным образом организованный набор элементов хранимых данные. Все данные хранятся в виде пар ключ-значение. Доступ к элементам данных осуществляется по ключу. Ключ всегда должен быть уникальным в пределах одного словаря, данные могут дублироваться при необходимости. У данной структуры есть и другие часто встречающиеся названия: ассоциативный массив или Dictionary. Принцип работы словаря схож с камерой хранения: есть ячейка, в которой может храниться что угодно, но доступ к этой ячейке осуществляется по уникальному номеру, благодаря чему ее всегда легко найти. Давайте рассмотрим пример реализации словаря на языке C#.

На рисунке ниже представлена схематичная структура словаря.

Map

Map

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

  • Add — добавление нового элемента с уникальным ключом.
  • Remove — удаление элемента по ключу.
  • Update — изменить хранимое значение по ключу.
  • Get — получить хранимое значение по ключу.

Теперь приступим к реализации данной структуры данных. Будем использовать обобщенный класс с двумя принимаемыми типами для ключа и значения. Для хранения данных воспользуемся списком. Данная реализация является весьма примитивной, но позволяет разобраться в структуре и алгоритме работы данного типа данных.

Элемент словаря

using System;

namespace Map
{
    /// <summary>
    /// Элемент словаря.
    /// </summary>
    public class Item<TKye, TValue>
    {
        /// <summary>
        /// Ключ.
        /// </summary>
        public TKye Key { get; set; }

        /// <summary>
        /// Значение.
        /// </summary>
        public TValue Value { get; set; }

        /// <summary>
        /// Создать новый пустой экземпляр класса Item.
        /// </summary>
        public Item() { }

        /// <summary>
        /// Создано новый экземпляр класса Item.
        /// </summary>
        /// <param name="key"> Ключ. </param>
        /// <param name="value"> Значение. </param>
        public Item(TKye key, TValue value)
        {
            // Проверяем входные данные на корректность.
            if (key == null)
            {
                throw new ArgumentNullException(nameof(key));
            }

            if (value == null)
            {
                throw new ArgumentNullException(nameof(value));
            }

            Key = key;
            Value = value;
        }

        /// <summary>
        /// Приведение объекта к строке.
        /// </summary>
        /// <returns> Хранимое значение. </returns>
        public override string ToString()
        {
            return Value.ToString();
        }
    }
}

Словарь

using System;
using System.Collections.Generic;
using System.Linq;

namespace Map
{
    /// <summary>
    /// Словарь.
    /// </summary>
    public class Map<TKey, TValue>
    {
        /// <summary>
        /// Коллекция хранимых данных.
        /// </summary>
        private List<Item<TKey, TValue>> _items = new List<Item<TKey, TValue>>();

        /// <summary>
        /// Количество элементов.
        /// </summary>
        public int Count => _items.Count;

        /// <summary>
        /// Коллекция ключей.
        /// </summary>
        public IReadOnlyList<TKey> Keys => (IReadOnlyList<TKey>)_items.Select(i => i.Key).ToList();

        /// <summary>
        /// Добавить данные в словарь.
        /// </summary>
        /// <param name="item"> Элемент добавляемых данных в виде пары ключ-значение. </param>
        public void Add(Item<TKey, TValue> item)
        {
            // Проверяем входные данные на корректность.
            if(item == null)
            {
                throw new ArgumentNullException(nameof(item));
            }

            if(_items.Any(i => i.Key.Equals(item.Key)))
            {
                throw new ArgumentException($"Словарь уже содержит значение с ключом {item.Key}.", nameof(item));
            }

            // Добавляем данные в коллекцию.
            _items.Add(item);
        }

        /// <summary>
        /// Добавить данные в словарь.
        /// </summary>
        /// <param name="key"> Ключ, по которому доступны хранимые данные. </param>
        /// <param name="value"> Данные, хранимые в словаре. </param>
        public void Add(TKey key, TValue value)
        {
            // Проверяем входные данные на корректность.
            if (key == null)
            {
                throw new ArgumentNullException(nameof(key));
            }

            if (value == null)
            {
                throw new ArgumentNullException(nameof(value));
            }

            if (_items.Any(i => i.Key.Equals(key)))
            {
                throw new ArgumentException($"Словарь уже содержит значение с ключом {key}.", nameof(key));
            }

            // Создаем новый элемент хранимых данных.
            var item = new Item<TKey, TValue>()
            {
                Key = key,
                Value = value
            };

            // Добавляем данные в коллекцию.
            _items.Add(item);
        }

        /// <summary>
        /// Удалить данные из коллекции по ключу.
        /// </summary>
        /// <param name="key"> Ключ, по которому доступны данные. </param>
        public void Remove(TKey key)
        {
            // Проверяем входные данные на корректность.
            if (key == null)
            {
                throw new ArgumentNullException(nameof(key));
            }

            // Получаем элемент данных из коллекции по ключу.
            var item = _items.SingleOrDefault(i => i.Key.Equals(key));

            // Если данные найдены по ключу, 
            // то удаляем их из коллекции.
            if(item != null)
            {
                _items.Remove(item);
            }
        }

        /// <summary>
        /// Изменить хранимые данные по ключу.
        /// </summary>
        /// <param name="key"> Ключ, по которому доступны хранимые данные. </param>
        /// <param name="newValue"> Новое значение данных. </param>
        public void Update(TKey key, TValue newValue)
        {
            // Проверяем входные данные на корректность.
            if (key == null)
            {
                throw new ArgumentNullException(nameof(key));
            }

            if (newValue == null)
            {
                throw new ArgumentNullException(nameof(newValue));
            }

            if (!_items.Any(i => i.Key.Equals(key)))
            {
                throw new ArgumentException($"Словарь не содержит значение с ключом {key}.", nameof(key));
            }

            // Получаем элемент данных по ключу.
            var item = _items.SingleOrDefault(i => i.Key.Equals(key));

            // Если данные найдены по ключу, 
            // то изменяем хранимое значение на новое.
            if (item != null)
            {
                item.Value = newValue;
            }
        }

        /// <summary>
        /// Получит значение по ключу.
        /// </summary>
        /// <param name="key"> Ключ, по которому доступны хранимые данные. </param>
        /// <returns> Значение хранимых данных. </returns>
        public TValue Get(TKey key)
        {
            // Проверяем входные данные на корректность.
            if (key == null)
            {
                throw new ArgumentNullException(nameof(key));
            }

            // Получаем значение по ключу.
            var item = _items.SingleOrDefault(i => i.Key.Equals(key)) ??
                throw new ArgumentException($"Словарь не содержит значение с ключом {key}.", nameof(key));

            // Возвращаем значение хранимых данных.
            return item.Value;
        }
    }
}

Вызов

using System;

namespace Map
{
    class Program
    {
        static void Main(string[] args)
        {
            // Создаем словарь с начальными данными.
            var map = new Map<int, string>();
            map.Add(1, "Hello");
            map.Add(2, "world");
            map.Add(new Item<int, string>(3, "Hey"));
            map.Add(new Item<int, string>(4, "Space"));
            ShowMap(map, "Created map");

            // Изменяем один из элементов словаря.
            map.Update(2, "Beautiful World");
            ShowMap(map, "Updated map");

            // Удаляем один элемент словаря.
            map.Remove(4);
            ShowMap(map, "Cleared map");

            Console.ReadLine();
        }

        /// <summary>
        /// Вывести словарь на экран.
        /// </summary>
        /// <param name="map"> Словарь. </param>
        /// <param name="title"> Заголовок перед выводом словаря. </param>
        private static void ShowMap(Map<int, string> map, string title)
        {
            Console.WriteLine($"{title}: ");
            foreach(var key in map.Keys)
            {
                // Получаем значение словаря по ключу.
                var value = map.Get(key);
                Console.WriteLine($"{key} - {value}");
            }
            Console.WriteLine();
        }
    }
}

Заключение

На платформе .NET уже есть готовая реализация данной структуры данных. Она содержится в пространстве имен System.Collections и называется Dictionary. Исходный код доступен в репозитории github https://github.com/shwanoff/Map.

 
×
%d такие блоггеры, как: