codingblog

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

Существуют два основных способа реализации хеш-таблиц:

- Метод цепочек (открытое хеширование) — все элементы данных с совпадающем хешем объединяются в список.

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

В данном примере мы будем реализовывать первый вариант.

На рисунке ниже представлена схематичная структура хеш-таблицы.

Доступ к элементам осуществляется по его ключу. Основные операции, которые могут выполняться с хеш-таблицей?

- Insert — добавить новый элемент в хеш-таблицу

- Delete — удалить элемент из хеш-таблицы по ключу

- Search — получить значение по ключу

Основной принцип работы хеш-таблицы заключается в том, что в качестве входных параметров она принимает пары ключ-значение. Затем с помощью специальной хеш функции получает короткий ключ на основе полученного ключа. И наконец добавляет данные в таблицу. Если в таблице уже существует значения с таким хешем, то объединяет их в коллекции. Внутри коллекции поиск выполняется по изначальному полученному ключу.

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

Класс элемента данных хеш-таблицы

Класс хеш-таблицы

Работа с хеш-таблицей

Результат работы приложения

На платформе .NET уже есть готовая реализация данной структуры данных. Она содержится в пространстве имен System.Collections и называется аналогично Hashtable. Я не претендую на правильность, оптимальность и красоту реализации. Единственная цель, которую я преследую, поделиться полезной информацией о программировании, которая может кому-то пригодиться.

Источник: https://shwan.ru/hashtable/

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

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

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

1. Add — добавление нового элемента с уникальным ключом.

2. Remove — удаление элемента по ключу.

3. Update — изменить хранимое значение по ключу.

4. Get — получить хранимое значение по ключу.

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

Теперь рассмотрим программный код.

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

Объявим класс словаря, его свойства и реализуем основные операции

Теперь проверим работу словаря обратившись к нему

Ну и наконец запустим приложение и посмотрим результат работы на консоли

Заключение

На платформе .NET уже есть готовая реализация данной структуры данных. Она содержится в пространстве имен System.Collections и называется Dictionary. Я не претендую на правильность, оптимальность и красоту реализации. Единственная цель, которую я преследую, поделиться полезной информацией о программировании, которая может кому-то пригодиться.

Источник: https://shwan.ru/map/

Множество (set) — это структура данных, представляющая собой не организованный набор уникальных элементов одного типа. Данная структура очень тесно связано с математическим понятием теории множеств. В наиболее упрощенном понимании, множество — это набор уникальных однотипных данных, рассматриваемых как единое целое. Давайте рассмотрим пример реализации множества и основных операций выполняемых с множествами на языке C#.

На рисунке ниже схематически представлены два множества A и B, а также основные операции: объединение, пересечение, разность.

Давайте подробнее рассмотрим все наиболее часто встречающиеся операции над множествами:

1. Add — добавление элемента. Если такой элемент уже присутствует, то он не будет добавлен.

Remove — удаление элемента из множества.

2. Union — объединение множеств. Создается новое множество, включающее в себя все элементы из множества А и множества В. Если элемент содержится в обоих множествах, он будет добавлен однократно.

3. Difference — разность множеств. Создается новое множество, включающее в себя все элементы множества А, которые не входят в множество В.

4. Intersection — пересечение множеств. Создается новое множество, включающее в себя все элементы входящие одновременно и в множество А, и в множество В.

5.Subset — проверка на подмножество. Чтобы быть подмножеством, все элементы множества А должны содержаться в множестве В. Тогда множество А является подмножеством множества В.

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

Реализация класса Set.cs

Для начала объявим класс и его свойства

Теперь реализуем операции добавления и удаления элементов множества

Теперь реализуем операцию объединения множеств

Реализуем операцию пересечения множеств

Реализуем операцию разности множеств

Ну и наконец сделаем проверку на подмножество и реализуем интерфейс IEnumerable

Теперь проверим работу нашего класса

В результате получаем следующий вывод на экран

Заключение

На платформе .NET все операции над множествами уже оптимально реализованы в рамках LINQ запросов, поэтому реализовывать самостоятельно нет необходимости. Я не претендую на правильность, оптимальность и красоту реализации. Единственная цель, которую я преследую, поделиться полезной информацией о программировании, которая может кому-то пригодиться.

Источник https://shwan.ru/set/

Связный список (Linked List) представляет собой коллекцию связанных элементов, которые содержат в себе хранимые данные, а также ссылку на связанные с ним элементы (один или несколько). Основным преимуществом данной структуры данных перед обычным массивом является ее динамичность — возможность легко менять количество элементов. Давайте рассмотрим пример реализации на языке C# элементарного односвязного списка.

Для начала необходимо упомянуть, что существует несколько видов связных списков. Вот наиболее часто используемые из них:

1. Односвязный список

2. Двусвязный список

3. Кольцевой список

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

Элемент списка

Рассмотрим класс элемента связного списка. Для того, чтобы сделать его более универсальным мы используем Универсальный параметр T. Это позволит динамически указывать тип данных при использовании списка.

Список элементов

Теперь рассмотрим сам класс связного списка. Для него мы также используем Универсальный (generic) тип T, а также реализуем интерфейс IEnumerable, чтобы в дальнейшем было удобно перебирать элементы списка с помощью цикла foreach. Выделим основные необходимые свойства класса:

Теперь реализуем метод добавления данных в коллекцию

Удаление данных из коллекции

Ну и наконец вспомогательные методы для полной очистки связного списка и перебора элементов в цикле

Использование

Теперь нам остается проверить работу нашего списка. Для этого создадим несколько элементов и проверим работу списка.

В итоге получаем следующий вывод на консоль

Заключение

Здесь представлена элементарная реализация данной динамической структуры данных. На практике она уже реализована намного лучше внутри платформы .NET в виде списка List<T>, но для того, чтобы понять внутреннюю структуру лучше рассматривать более простые примеры. Источник https://shwan.ru/linked-list/

Angular — это фреймворк позволяющий быстро и удобно разрабатывать одностраничные веб приложения. В своей основе он использует язык программирования TypeScript. Давайте рассмотрим процесс создания процесс создания SPA-приложения (Single Page Application) с помощью данного фреймворка от идеи до публикации.

Данная статья достаточно объемна, поэтому будет разбита на несколько частей и опубликована в моем блоге. Для разработки будет использоваться Angular 5, Visual Studio 2017. Итак, нашей целью является разработка простого приложения представляющее собой доску объявлений, куда можно публиковать короткие объявления. Приступ. Перед началом работы не забываем, что предварительно необходимо установить node.js.

Часть 1 - Создание проекта и первоначальное выделение компонентов на основе статической html-старицы

Часть 2 - Выделение более специализированных компонентов, реализация взаимодействия с базой данных

Часть 3 - Завершение выделения всех компонентов, публикация приложения.