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

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

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

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

Java

Java Generics — Bounded Wildcards (ковариантность и контравариантность)

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

В данной статье мы обсудим инвариантность, ковариантность и контравариантность Java, а также разберемся при чем здесь дженерики и Bounded Wildcards. Вариантность Вариантность (variance) показывает как производные типы наследуются в зависимости от наследования между их исходными типами. Производные типы — это контейнеры, делегаты и прочие классы, которые оперируют другими типами внутри себя. Например, List<Integer> — это […]

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

АТД: Дек

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

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

Java

Интернирование строк в Java

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

Интернирование — это техника хранения только одной иммутабельной копии объекта для повторяющихся значений объекта. Каждая такая уникальная копия называется intern-ом. Интернирование строк же означает, что всегда будет создаваться и храниться только одна уникальная копия строки для строк с одинаковым содержимым. Зачем это нужно Интернирование строк позволяет оптимизировать работу с строками как в аспекте времени, так […]

Java

Организация Java объектов в памяти

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

В данной статье мы рассмотрим, как устроены Java объекты в памяти. Стандарт Java не указывает, какой должна быть организация памяти объектов, поэтому мы рассмотрим эти аспекты на примере open-source HotSpot JVM. Java Object Структура, описывающая Java Object, который неявно является родительским классом для всех объектов в Java, состоит из Mark Word и Klass Word. Mark […]

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

АТД: Очередь

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

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

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

АТД: Стек

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

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

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

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

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

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

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

АТД: Список

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

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

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

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

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

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