Алгоритмы и структуры данных

Консистентное хеширование

Опубликовано

Консистентное хеширование позволяет нам распределять ключи так, что при изменении количества бакетов будет рехешировано в среднем только K/N ключей, где K — количество ключей, а N — количество бакетов после изменения. Для сравнения, в большинстве стандартных имплементаций хеш-таблиц требуется рехешировать почти все ключи. Что такое хеширование? Хеширование — это отображение некоторого множества объектов в множество […]

Алгоритмы и структуры данных

АТД: Дек

Опубликовано

Дек (Deque) — это абстрактный тип данных, который вбирает в себя возможности как стека, так и очереди, то есть может работать с элементами как по LIFO, так и по FIFO принципу. Операции на деке Дек должен поддерживать следующие основные операции: Вставка в начало (pushFront) Вставка в конец (pushBack) Удаление элемента с начала (popFront) Удаление элемента […]

Алгоритмы и структуры данных

АТД: Очередь

Опубликовано

Очередь (queue) — это абстрактный тип данных, который содержит коллекцию элементов, организованных по принципу FIFO. Принцип FIFO (first in, first out — «первым пришёл — первым ушёл») предпологает, что элемент, первым попавшим в коллекцию, должен быть первым удален или обслужен. Принцип LIFO, по которому работает стек, полная противоположность этому — там элемент, пришедший первым, обслуживается самым последним, […]

Алгоритмы и структуры данных

АТД: Стек

Опубликовано

Стек (Stack) — это абстрактный тип данных, представляющий собой коллекцию элементов, организованных по принципу LIFO. Принцип LIFO (last in, first out, «последним пришёл — первым ушёл») предпологает, что элементы добавляются и удаляются только с одного конца. Данный принцип применяется в тех случаях, когда последние данные, добавленные в коллекцию, должны быть первыми удалены или обработаны. Операции на […]

Алгоритмы и структуры данных

Структура данных: связный список

Опубликовано

В данной статье мы рассмотрим еще одну популярную реализацию списка — связный список. Связный список — это коллекция элементов, порядок которых не зависит от положения в памяти. В ней каждый элемент — так называемая нода — имеет указатель на следующий. Связные списки наравне с массивами являются базовыми структурами данными, которые позволяют нам реализовать более сложные […]

Алгоритмы и структуры данных

АТД: Список

Опубликовано

Список (List) — это абстрактный тип данных, который предпологает хранение конечного набора значений в определенном порядке, причем каждое значение может повторяться более одного раза. Реализации списка часто используются для реализации более сложных структур данных, например Хэш-таблиц. Доступные операции Вот некоторые операции, которые могут быть доступны для списка: Проверка на пустоту списка Добавление элемента в конец […]

Алгоритмы и структуры данных

Структура данных: Хэш-таблица

Опубликовано

Хэш-таблица (Hash table) — это структура данных, реализующая интерфейс ассоциативного массива и позволяющая маппить ключ к значению. Особенность хэш-таблицы в том, что в среднем случае она поддерживает доступ к ключу за константное время. Идея Ключевая идея хэш-таблицы заключается в двух вещах: Использовании массива для хранения пар, что дает Хэширования Элементы массива же в хэш-таблице называются […]

Алгоритмы и структуры данных

АТД: Ассоциативный массив

Опубликовано

Ассоциативный массив (associative array) — это абстрактный тип данных (АТД), который предпологает хранение пар вида «(ключ, значение)». Данный тип данных также известен как «мапа» или словарь (map, dictionary).