что такое стек в java
Управление памятью Java
Это глубокое погружение в управление памятью Java позволит расширить ваши знания о том, как работает куча, ссылочные типы и сборка мусора.
Вероятно, вы могли подумать, что если вы программируете на Java, то вам незачем знать о том, как работает память. В Java есть автоматическое управление памятью, красивый и тихий сборщик мусора, который работает в фоновом режиме для очистки неиспользуемых объектов и освобождения некоторой памяти.
Поэтому вам, как программисту на Java, не нужно беспокоиться о таких проблемах, как уничтожение объектов, поскольку они больше не используются. Однако, даже если в Java этот процесс выполняется автоматически, он ничего не гарантирует. Не зная, как устроен сборщик мусора и память Java, вы можете создать объекты, которые не подходят для сбора мусора, даже если вы их больше не используете.
Для начала давайте посмотрим, как обычно организована память в Java:
Структура памяти
Стек (Stack)
Стековая память отвечает за хранение ссылок на объекты кучи и за хранение типов значений (также известных в Java как примитивные типы), которые содержат само значение, а не ссылку на объект из кучи.
Кроме того, переменные в стеке имеют определенную видимость, также называемую областью видимости. Используются только объекты из активной области. Например, предполагая, что у нас нет никаких глобальных переменных (полей) области видимости, а только локальные переменные, если компилятор выполняет тело метода, он может получить доступ только к объектам из стека, которые находятся внутри тела метода. Он не может получить доступ к другим локальным переменным, так как они не выходят в область видимости. Когда метод завершается и возвращается, верхняя часть стека выталкивается, и активная область видимости изменяется.
Возможно, вы заметили, что на картинке выше отображено несколько стеков памяти. Это связано с тем, что стековая память в Java выделяется для каждого потока. Следовательно, каждый раз, когда поток создается и запускается, он имеет свою собственную стековую память и не может получить доступ к стековой памяти другого потока.
Куча (Heap)
Эта часть памяти хранит в памяти фактические объекты, на которые ссылаются переменные из стека. Например, давайте проанализируем, что происходит в следующей строке кода:
Ключевое слово new несет ответственность за обеспечение того, достаточно ли свободного места на куче, создавая объект типа StringBuilder в памяти и обращаясь к нему через «Builder» ссылки, которая попадает в стек.
Для каждого запущенного процесса JVM существует только одна область памяти в куче. Следовательно, это общая часть памяти независимо от того, сколько потоков выполняется. На самом деле структура кучи немного отличается от того, что показано на картинке выше. Сама куча разделена на несколько частей, что облегчает процесс сборки мусора.
Типы ссылок
Если вы внимательно посмотрите на изображение структуры памяти, вы, вероятно, заметите, что стрелки, представляющие ссылки на объекты из кучи, на самом деле относятся к разным типам. Это потому, что в языке программирования Java используются разные типы ссылок: сильные, слабые, мягкие и фантомные ссылки. Разница между типами ссылок заключается в том, что объекты в куче, на которые они ссылаются, имеют право на сборку мусора по различным критериям. Рассмотрим подробнее каждую из них.
1. Сильная ссылка
Это самые популярные ссылочные типы, к которым мы все привыкли. В приведенном выше примере со StringBuilder мы фактически храним сильную ссылку на объект из кучи. Объект в куче не удаляется сборщиком мусора, пока на него указывает сильная ссылка или если он явно доступен через цепочку сильных ссылок.
2. Слабая ссылка
Попросту говоря, слабая ссылка на объект из кучи, скорее всего, не сохранится после следующего процесса сборки мусора. Слабая ссылка создается следующим образом:
После сбора мусора ключа из WeakHashMap вся запись удаляется из карты.
3. Мягкая ссылка
Подобно слабым ссылкам, мягкая ссылка создается следующим образом:
4. Фантомная ссылка
Ссылки на String
Ссылки на тип String в Java обрабатываются немного по- другому. Строки неизменяемы, что означает, что каждый раз, когда вы делаете что-то со строкой, в куче фактически создается другой объект. Для строк Java управляет пулом строк в памяти. Это означает, что Java сохраняет и повторно использует строки, когда это возможно. В основном это верно для строковых литералов. Например:
При запуске этот код распечатывает следующее:
Следовательно, оказывается, что две ссылки типа String на одинаковые строковые литералы фактически указывают на одни и те же объекты в куче. Однако это не действует для вычисляемых строк. Предположим, что у нас есть следующее изменение в строке // 1 приведенного выше кода.
Strings are different
При добавлении вышеуказанного изменения создается следующий результат:
Процесс сборки мусора
Как обсуждалось ранее, в зависимости от типа ссылки, которую переменная из стека содержит на объект из кучи, в определенный момент времени этот объект становится подходящим для сборщика мусора.
Объекты, подходящие для сборки мусора
Например, все объекты, отмеченные красным цветом, могут быть собраны сборщиком мусора. Вы можете заметить, что в куче есть объект, который имеет строгие ссылки на другие объекты, которые также находятся в куче (например, это может быть список, который имеет ссылки на его элементы, или объект, имеющий два поля типа, на которые есть ссылки). Однако, поскольку ссылка из стека потеряна, к ней больше нельзя получить доступ, так что это тоже мусор.
Чтобы углубиться в детали, давайте сначала упомянем несколько вещей:
Этот процесс запускается автоматически Java, и Java решает, запускать или нет этот процесс.
На самом деле это дорогостоящий процесс. При запуске сборщика мусора все потоки в вашем приложении приостанавливаются (в зависимости от типа GC, который будет обсуждаться позже).
На самом деле это более сложный процесс, чем просто сбор мусора и освобождение памяти.
Несмотря на то, что Java решает, когда запускать сборщик мусора, вы можете явно вызвать System.gc() и ожидать, что сборщик мусора будет запускаться при выполнении этой строки кода, верно?
Это ошибочное предположение.
Вы только как бы просите Java запустить сборщик мусора, но, опять же, Java решать, делать это или нет. В любом случае явно вызывать System.gc() не рекомендуется.
Поскольку это довольно сложный процесс и может повлиять на вашу производительность, он реализован разумно. Для этого используется так называемый процесс «Mark and Sweep». Java анализирует переменные из стека и «отмечает» все объекты, которые необходимо поддерживать в рабочем состоянии. Затем все неиспользуемые объекты очищаются.
Так что на самом деле Java не собирает мусор. Фактически, чем больше мусора и чем меньше объектов помечены как живые, тем быстрее идет процесс. Чтобы сделать это еще более оптимизированным, память кучи на самом деле состоит из нескольких частей. Мы можем визуализировать использование памяти и другие полезные вещи с помощью JVisualVM, инструмента, поставляемого с Java JDK. Единственное, что вам нужно сделать, это установить плагин с именем Visual GC, который позволяет увидеть, как на самом деле структурирована память. Давайте немного увеличим масштаб и разберем общую картину:
Поколения памяти кучи
Когда объект создается, он размещается в пространстве Eden (1). Поскольку пространство Eden не такое уж большое, оно заполняется довольно быстро. Сборщик мусора работает в пространстве Eden и помечает объекты как живые.
Если объект выживает в процессе сборки мусора, он перемещается в так называемое пространство выжившего S0(2). Во второй раз, когда сборщик мусора запускается в пространстве Eden, он перемещает все уцелевшие объекты в пространство S1(3). Кроме того, все, что в настоящее время находится на S0(2), перемещается в пространство S1(3).
Если объект выживает в течение X раундов сборки мусора (X зависит от реализации JVM, в моем случае это 8), скорее всего, он выживет вечно и перемещается в пространство Old(4).
Принимая все сказанное выше, если вы посмотрите на график сборщика мусора (6), каждый раз, когда он запускается, вы можете увидеть, что объекты переключаются на пространство выживших и что пространство Эдема увеличивалось. И так далее. Старое поколение также может быть обработано сборщиком мусора, но, поскольку это большая часть памяти по сравнению с пространством Eden, это происходит не так часто. Метапространство (5) используется для хранения метаданных о ваших загруженных классах в JVM.
Представленное изображение на самом деле является приложением Java 8. До Java 8 структура памяти была немного другой. Метапространство на самом деле называется PermGen область. Например, в Java 6 это пространство также хранит память для пула строк. Поэтому, если в вашем приложении Java 6 слишком много строк, оно может аварийно завершить работу.
Типы сборщиков мусора
Фактически, JVM имеет три типа сборщиков мусора, и программист может выбрать, какой из них следует использовать. По умолчанию Java выбирает используемый тип сборщика мусора в зависимости от базового оборудования.
3. Mostly concurrent GC (В основном параллельный сборщик мусора). Если вы помните, ранее в этой статье упоминалось, что процесс сбора мусора на самом деле довольно дорогостоящий, и когда он выполняется, все потоки приостанавливаются. Однако у нас есть в основном параллельный тип GC, который утверждает, что он работает одновременно с приложением. Однако есть причина, по которой он «в основном» параллелен. Он не работает на 100% одновременно с приложением. Есть период времени, на который цепочки приостанавливаются. Тем не менее, пауза делается как можно короче для достижения наилучшей производительности сборщика мусора. На самом деле существует 2 типа в основном параллельных сборщиков мусора:
Примечание переводчика. Информация про сборщики мусора для различных версий Java приведена в переводе:
Советы и приемы
Чтобы минимизировать объем памяти, максимально ограничьте область видимости переменных. Помните, что каждый раз, когда выскакивает верхняя область видимости из стека, ссылки из этой области теряются, и это может сделать объекты пригодными для сбора мусора.
Явно устанавливайте в null устаревшие ссылки. Это сделает объекты, на которые ссылаются, подходящими для сбора мусора.
Избегайте финализаторов (finalizer). Они замедляют процесс и ничего не гарантируют. Фантомные ссылки предпочтительны для работы по очистке памяти.
JVisualVM также имеет функцию создания дампа кучи в определенный момент, чтобы вы могли анализировать для каждого класса, сколько памяти он занимает.
Настройте JVM в соответствии с требованиями вашего приложения. Явно укажите размер кучи для JVM при запуске приложения. Процесс выделения памяти также является дорогостоящим, поэтому выделите разумный начальный и максимальный объем памяти для кучи. Если вы знаете его, то не имеет смысла начинать с небольшого начального размера кучи с самого начала, JVM расширит это пространство памяти. Указание параметров памяти выполняется с помощью следующих параметров:
Если приложение Java выдает ошибку OutOfMemoryError и вам нужна дополнительная информация для обнаружения утечки, запустите процесс с –XX:HeapDumpOnOutOfMemory параметром, который создаст файл дампа кучи, когда эта ошибка произойдет в следующий раз.
Заключение
Краткое руководство по стеку Java
Краткое и практическое руководство по общим операциям java.util.Стек.
1. Обзор
В этой краткой статье мы представим java.util.Stack class и начните смотреть, как мы можем его использовать.
Стек – это универсальная структура данных, представляющая коллекцию объектов LIFO (последний вход, первый выход), позволяющую выталкивать/выталкивать элементы в постоянное время.
2. Создайте стек
3. Синхронизация для стека
Стек является прямым подклассом вектора ; это означает, что аналогично своему суперклассу, это синхронизированная реализация.
4. Добавьте в стопку
Использование метода push() имеет тот же эффект, что и использование метода addElement(). T единственное отличие заключается в том, что addElement() возвращает результат операции, а не добавленный элемент.
Мы также можем добавить несколько элементов одновременно:
5. Извлечение из стека
Далее давайте посмотрим, как получить и удалить последний элемент в стеке :
6. Поиск элемента в стеке
6.1. Поиск
Стек позволяет нам искать элемент и получать его расстояние от вершины:
Результатом является индекс данного объекта. Если присутствует более одного элемента, возвращается индекс того |, который находится ближе всего к вершине|/. Элемент, находящийся в верхней части стека, считается находящимся в позиции 1.
6.2. Получение индекса элемента
Чтобы получить индекс элемента на S tack, мы также можем использовать методы indexOf() и lastIndexOf() :
7. Удалите элементы из стека
7.1. Удаление Указанных Элементов
Мы можем использовать метод removeElement() для удаления первого вхождения данного элемента:
Мы также можем использовать removeElementAt() для удаления элементов с указанным индексом в стеке :
7.2. Удаление Нескольких Элементов
Давайте быстро рассмотрим, как удалить несколько элементов из стека с помощью removeAll() API, который будет принимать Коллекцию в качестве аргумента и удалять все соответствующие элементы из стека :
Также можно удалить все элементы из стека с помощью clear() или removeAllElements() методов ; оба эти метода работают одинаково:
7.3. Удаление Элементов С Помощью Фильтра
8. Выполните итерацию по стеку
9. Потоковый API для стека Java
Stack – это коллекция, а это значит, что мы можем использовать ее с Java 8 Streams API. Использование Потока с Стеком аналогично использованию его с любой другой Коллекцией:
10. Резюме
Что такое стек в java
Сегодня будем говорить об алгоритмах и структурах данных для реализации фундаментальных типов данных — мультимножества, очереди и стека. Может быть, вы немного знакомы с ними, но сегодня мы рассмотрим их подробно. Начнем со стека.
Идея в том, что во многих приложениях есть множества объектов для обработки. Это простые операции. Нужно добавлять элементы к коллекции, удалять элементы из неё, проходить по всем объектам, проводя над ними какие-либо операции, проверять, не пуста ли она. Намерения вполне понятные. Ключевой момент: когда нужно удалить элемент коллекции, какой именно удалять? Есть две классические структуры данных: стек и очередь. Они различаются выбором элемента для удаления. В стеке мы удаляем последний добавленный элемент.
Подтемой сегодня будет модульное программирование. Идея в том, что бы полностью разделять интерфейс и реализацию. При наличии четко определенной структуры и типов данных, как стек или очередь, мы полностью скрываем детали реализации от клиента. Клиент может выбрать различные реализации но код должен использовать только базовые операции.
С другой стороны, реализация не может знать детально потребности клиента. Код должен лишь реализовать операции. В этом случае, многие клиенты могут использовать одну реализацию. Мы можем создавать модульные, многократно используемые библиотеки алгоритмов и структур данных, из которых строятся более сложные алгоритмы и структуры данных. Это позволяет при необходимости сосредоточиться на быстродействии. Это модульный стиль программирования, который возможен благодаря объектно-ориентированным языкам, как Java. Будем придерживаться этого стиля. Начнем разговор со стеков.
Давайте тщательно разберем реализацию стека прямо сейчас. Для разминки предположим, что у нас есть коллекция строк. Они могут быть короткими или длинными. Мы хотим иметь возможность сохранять коллекцию строк, удалять и выводить последние добавленные строки, проверять, пуста ли она.
Так вот наше API, конструктор для создания пустого стека. Для вставки используется метод push, аргумент которого — строка, для удаления — метод pop, который выводит строку, добавленную последней. Метод isEmpty возвращает логическое значение. В некоторых приложениях, мы будет включать метод Size.
Как обычно, сначала напишем клиент, а затем разберем реализацию.
Наш клиент читает строки из стандартного ввода и использует команду pop, которую обозначим дефисом. Итак, этот клиент читает строки из стандартного ввода. Если строка равна знаку дефис, берем строку сверху стека и печатаем её. В противном случае, если строка не равна дефису, она добавляется наверх стека.
Есть файл tobe.text, клиент будет вставлять строки «to be or not to» в стек. Затем, когда дело доходит до дефиса, он выдаст последний добавленный элемент, в данном случае это «to». Затем добавит «be» наверх стека и выдаст верхний элемент стека, то есть «be» и элемент, добавленный последним. Т.е. «Be» уйдет, «to» тоже, за ними идет «not» и так далее. Этот простой тестовый клиент можно использовать для проверки наших реализаций. Посмотрим код для реализации стека.
Первая реализация использует односвязный список. О связных списках можно подробнее почитать здесь. Нужно хранить односвязный список, который состоит из узлов, в свою очередь состоящих из строки и ссылки на следующий элемент списка.
В реализации стека, когда мы делаем добавление (push), то вставляем новый узел в начало списка. Когда извлекаем элемент, то удаляем первый элемент списка. Это последний добавленный элемент. Посмотрим, как выглядит этот код. Используем внутренний класс Java. То есть будем манипулировать объектами «узел», каждый из которых состоит из строки и ссылки на другой объект «узел». Таким образом операция pop для списка реализуется очень просто. Во-первых нужно вывести первый элемент в списке, поэтому сохраняем его. Возьмем first.item и сохраним в переменную item.
Чтобы избавиться от первого узла, просто сдвигаем указатель первого элемента списка на следующий за ним элемент. Теперь первый элемент готов быть удаленным сборщиком мусора. Остается только вывести элемент, который мы сохранили. Это была операция pop. Что насчет push операции?
Мы хотим добавить новый элемент в начало списка. Первое: сохраняем указатель на начало списка. Это oldfirst = first. Затем создаем новый узел, который поместим в начало списка. Это: first = new Node. Затем присваиваем ему значения. В поле item — строку, которую хотим вставить в начало списка В этом случае «not». И в поле next вставим указатель oldfirst, который теперь второй элемент списка. Так после этой операции, «first» указывает на начало списка. Элементы списка расположены в обратном порядке относительно их добавления в стек.
Эти 4 строки реализуют стековую операцию push(). А вот полная реализация на базе связного списка всего кода для реализации стека строк в Java. В этом классе конструктор ничего не делает, поэтому его нет.
Вот внутренний класс, который мы используем для элементов списка. Делаем его внутренним, чтобы ссылаться напрямую на него. И тогда единственной переменной стека является ссылка на первый узел в списке, и она на старте равна null. Тогда isEmpty просто проверка first на null. Push — это четыре строки кода, которые я уже показывал, pop — это 3 строки кода, которые были даны раньше. Это полный код односвязного списка, который является хорошей реализацией спускающегося списка для любого клиента.
Можно проанализировать алгоритм и предоставить информацию о его быстродействии клиентам. В этом случае видно, что каждая операция в худшем случае тратит постоянное время. Всего несколько инструкций для каждой из операций. Тут нет циклов. Это, очевидно, весьма неплохо.
Зависит от реализации и компьютера, здесь проанализирована типичная java реализация. Вы можете проверить её для различных сред выполнения, так что она показательна. Для каждого объекта в Java 16 байт идет на заголовок. Дополнительно 8 байт, потому что это внутренний класс. В классе Node есть 2 встроенные ссылки: одна на строку, другая на узел, каждая из них — 8 байт. Итак 40 байт для записи стека.
Если у нас есть стек размером N, он займет 40 N байт. Ещё немного занимает first элемент, это около N для целого стека. При большом N значение 40*N точно оценивает требуемую память. Оно не учитывает место для самих строк внутри клиента. Но с этим мы можем правильно оценить затраты ресурсов реализацией для различных клиентских программ.
Время постоянное, но есть и более быстрые реализации стека. Если стек используется во внутренних циклах неких алгоритмов, то важно поискать более быстрые реализации. Другой способ реализации стека — это использование массива для хранения элементов. Посмотрим на него.
Выбор между связанными структурами и массивами является фундаментальным и будет возникать снова и снова при разборе более продвинутых структур данных и алгоритмов. Рассмотрим массив применительно к стеку, чтобы быть готовыми к более продвинутым приложениям в дальнейшем.
При использовании массива, мы просто держим N элементов стека в массиве. И позиция массива c индексом N — это место расположения вершины стека, куда должен быть помещен следующий элемент. Таким образом, для push(), мы просто добавляем новый элемент в s[N]. А для pop() удаляем элемент s[N-1] и уменьшаем N.
Есть большой минус при использовании массива — его размер должен быть объявлен заранее, значит стек имеет ограниченную вместимость. С этим придется считаться, если количество элементов стека превышает размеры массива. Это фундаментальная проблема, с которой приходится иметь дело при любых структурах данных алгоритмов. В данном простом примере это окупится.
Итак, вот полная реализация стека, использующая массив для представления структуры стека. Здесь переменная экземпляра, представляющая собой массив строк. А также наша переменная N, которая представляет собой как размер стека, так и индекс следующей свободной позиции.
У этого класса есть конструктор. Он создает массив. Здесь мы немного сжульничали для упрощения, займемся этим позже. Обман состоит в требовании указывать размер стека. Это нормально для некоторых приложений, но слишком обременительно для многих других.
Клиент не знает размеров стека. Ему может потребоваться множество стеков одновременно. Они могут достичь максимальной вместимости в разное время. Нужно избавиться от такого требования, и мы это сделаем. Но, код становится почти тривиальным, если мы явно используем вместимость. Для проверки на пустоту мы проверяем, равен ли N нулю.
Для размещения элемента используем N как индекс массива, помещаем туда элемент и увеличиваем N. Вот это, N++, используется во многих языках программирования как сокращение для «используй индекс и увеличь его на 1». А для pop() мы уменьшаем индекс, затем используем его для возврата элемента массива. Таким образом, каждая из операций является однострочной. Это прекрасная реализация для некоторых клиентов. Это реализация стека с помощью массива, но она ломает API, требуя от клиента указания вместимости стека.
Итак, что с этим делать? Есть пара вещей, которые мы не рассмотрели. Мы не написали кода для выброса исключения, если клиент пытается извлечь элемент из пустого стека. Вероятно, следует это сделать. А что случится, если клиент поместит слишком много элементов? Поговорим об изменении размера, которое позволяет избежать переполнения.
Вопрос ещё в том, могут ли клиенты вставлять null элементы в структуру данных. В данном случае мы это позволяем. Но нужно позаботиться о проблеме лойтеринга, когда в массиве хранится ссылка на объект, который на самом деле не используется. Когда мы удаляем значение стека, то в массиве остается ссылка на него. Мы знаем, что больше не используем его, а Java нет.
Для более эффективного использования памяти нужно устанавливать удаленные элементы в Null. Так, чтобы не оставалось ссылок на старые элементы, и сборщик мусора мог освободить память, так как на неё больше никто не ссылается. Это деталь, но для максимально эффективного использования памяти необходимо это учесть.
статьи IT, алгоритмы, стек, java, теория программирования