Security basics, часть 1: симметричное и ассиметричное шифрование

Начнём с простой задачи: передать секретное сообщение по общедоступной сети.

Злоумышленник может прослушать канал связи, перехватить сообщение и даже поменять его. Такой тип атаки называется man in the middle🕵️

Что делать?

Самое простое — преобразовать сообщение, чтобы при перехвате злоумышленник ничего не понял. Например, сдвинуть каждую букву на 1:

Пирожок → Рйспзпл

Получатель выполнит обратную операцию и расшифрует сообщение.

Но для стандартных алгоритмов то же самое легко сделает и злоумышленник. Поэтому в преобразования вводится дополнительный параметр и формула становится сложнее. Например: символ → символ + k

Параметр (или ключ) вносит больше неопределённости в результат. Ключ может быть одним числом или состоять из нескольких чисел. Злоумышленнику нужно гораздо больше времени, чтобы взломать такой шифр.

🔸 Если для расшифровки используется тот же ключ, что и для шифрования, алгоритм называется симметричным.

Наиболее популярен алгоритм AES и его производные. Они, разумеется, более сложные, чем пример выше — сообщения делятся на блоки, блоки перемешиваются, внутри каждого блока выполняются десятки операций, и всё это проходит в несколько раундов.

На практике такой тип шифрования используется редко. Представьте, вы открыли сайт в браузере и хотите залогиниться. Чтобы безопасно передать пароль, вам с сервером нужен общий ключ. Но как получить его — непонятно.

🔸 Поэтому чаще применяется ассиметричное шифрование.

Создаётся пара ключей: один называется публичным, а другой — приватным.

🗝 Публичный ключ свободно распространяется и позволяет шифровать сообщения
🗝 Приватный ключ остаётся у получателя. И только он расшифрует полученное сообщение

Самый популярный ассимметричный алгоритм — RSA. Он основан на простых числах, вычислении степени и остатке от деления. Формулы несложные, а шифр получается вполне стойкий.

В последнее время в тренды выходит EdDSA. Он популярен тем, что активно используется в биткоине. Поддержка этого алгоритма появилась только в java 15.

Вообще алгоритмы шифрования используются не только для шифрования, но и входят в состав остальных инструментов безопасности. Но об этом позже🙂

Security basics, часть 2: цифровая подпись и немножко терминов

Давайте чётко обозначим разницу между терминами:

🔸 Хэширование

Цель — получить краткое представление объекта.

Objects.hash("пирожок") = 564453454

Результат не зависит от внешних параметров. Объект обратно восстановить нельзя. Самые популярный алгоритм — SHA, иногда используется MD5.

🔸 Кодирование

Цель — преобразовать сообщение для передачи. Используется при ограничениях на формат сообщений.

Пример: нужно передать JSON туда, где ожидается обычный текст.

Кодировка Base64 переводит любой битовый массив в простые символы — цифры, латинские буквы, +, / и =. Уйдут скобки, кавычки и всё, что может смутить канал передачи или библиотеку получателя.

Base64.encode("{"/пирожок"/}") = "TWFuIGlzIGRpc3Rp=

"

После получения закодированное сообщение приводится к исходному виду:

Base64.decode("TWFuIGlzIGRpc3Rp=") = "{"/пирожок"/}

"

🔸 Шифрование

Цель — защитить сообщение от посторонних. Зашифровать и прочитать сообщение могут только обладатели связанных ключей

Хэширование, кодирование и шифрование — это кирпичики, из которых собираются остальные механизмы безопасности.

🔹Например, электронная подпись

Это файлик с расширением .sig, который прилагается к сообщению и доказывает его подлинность.

Само сообщение передаётся в открытом виде и никак не скрывается.

❓ Как это работает?

Подпись может быть на основе любого алгоритма шифрования:

Симметричный алгоритм (редко используется):

▫️ Отправитель вычисляет хэш сообщения и шифрует его ключом
▫️ Получатель выполняет те же действия со своим ключом и сравнивает значение с присланной подписью
▫️ Если сообщение изменилось (поменялся хэш) или использовался не тот ключ, то значения не совпадут. Нет доверия такому документу🙂

Ассиметричный алгоритм:

▪️ Отправитель формирует подпись из хэша сообщения и приватного ключа
▪️ Получатель для проверки вызывает функцию, которая соотносит подпись, хэш сообщения и публичный ключ

Таким образом электронная подпись — это сочетание хэширования и шифрования. В JDK всё это находится в пакете java.security.

Security basics, часть 3: HTTPS

Вернёмся к ситуации, которую затронули пару дней назад.

Пользователь открывает сайт и хочет ввести пароль, данные карты или другую важную информацию. Симметричное шифрование здесь не подходит — непонятно как безопасно доставить ключ пользователю.

Все механизмы безопасности складываются из простых кирпичиков, и HTTPS не исключение:

🔸 Браузер присылает свой публичный ключ
🔸 Сервер присылает свой публичный ключ
🔸 Сервер и браузер вычисляют Общий ключ (shared secret) на основе своих приватных ключей и полученных публичных

Так через ассиметричное шифрование легко переходим к симметричному. Последний пункт выглядит как магия, но это всё математика. Спасибо криптографии за чудесные алгоритмы ❤️

Процесс выше называется TLS Handshake.

Скорее всего вы часто видели аббревиатуру SSL. Этот протокол появился в 90е и давно устарел, а ему на смену пришёл TLS. Но многие по старинке говорят SSL, иногда ещё пишется SSL/TLS.

Давайте опишем тот же процесс, но чуть подробней:

1️⃣ Браузер шлёт:

▫️ Алгоритмы, которые знает браузер
▫️ Свои публичные ключи и соответствующие алгоритмы
▫️ Случайное число №1

2️⃣ Сервер

Выбирает из списка алгоритмов подходящий для дальнейшего общения и запоминает публичный ключ браузера для выбранного алгоритма. Обратно шлёт

▫️ Названия выбранных алгоритмов
▫️ Свой публичный ключ
▫️ Сертификат
▫️ Случайное число №2

3️⃣ Обе стороны вычисляют Общий ключ и продолжают общаться

Больше технических подробностей читайте в статье TLS (SSL) handshakes explained. Разберём несколько вопросов "Зачем":

❓ Зачем браузер и сервер переходят на симметричное шифрование? Почему бы не продолжить шифровать сообщения публичными ключами?

Общий ключ короче и вычисления гораздо проще. Поэтому симметричные алгоритмы выполняются в тысячи раз быстрее ассиметричных.

❓ Зачем в сообщениях случайные числа?

Чтобы избежать Replay attack. Злоумышленник может прослушать сообщение и отправить от своего имени. Или отправить сообщение несколько раз, чтобы запутать получателя. Получатель запоминает число и не принимает сообщения с тем же числом.

❓ Зачем нужен сертификат?

Доказать, что сайт не фишинговый. В сертификате прописан:
▫️ Домен
▫️ Публичный ключ
▫️ Срок действия сертификата
▫️ Цифровая подпись

Сертификат подписывает:

🔹 Сам сервер своим приватным ключом. Браузер распознаёт самоподписанные сертификаты и выдаёт предупреждение. Но для разработки и тестирования такой вариант подойдёт
🔹 Специальная организация — Certificate Authority. Список СА хранится в операционной системе и в некоторых браузерах

Следить за сертификатами — задача девопса. Если срок действия сертификата истёк, то пользователи увидят надпись на весь экран, что сайту нельзя доверять.

❓ Зачем мне эта информация?

Чем выше ваша позиция, тем шире круг задач и проблем, которые нужно решать. И здесь очень важен общий кругозор. Плюс, чем больше вы знаете, как устроен мир, тем больше фундамент для ваших собственных решений🙂

На прошлой неделе мы обсуждали, как защитить данные. На этой неделе я запланировала другую тему — авторизация и аутентификации.

🔸 Аутентификация — проверить, что пользователь тот, за кого себя выдаёт

🔸 Авторизация — есть ли у пользователя права на конкретное действие

С этим редко бывают сложности. Гораздо интереснее темы, которые идут рядом: JWT, oAuth, SSO и как это всё работает со Spring Security.

Тут легко увлечься, но нельзя сказать, что такие задачи приходят каждый день. Так что сегодня расскажу о JWT, а остальное — как-нибудь потом🙃

Security basics, часть 4: JWT

Статей про JWT много, но все они делают упор на авторизацию. Но JWT используется по-разному, поэтому начну с общей схемы, а потом перейду на auth.

Возьмём как пример интернет-магазин. Пользователь что-то смотрит, добавляет товары в корзину, отмечает какие-то опции.

❓ Вопрос — где хранить корзину с товарами?

🔸 На сервере

Когда клиент начинает работу с приложением, на сервере создаётся запись типа

sessionID - { /*info*/ }

Там хранится информация для текущего сеанса.

Когда пользователь вводит логин-пароль, то получает обратно sessionID. SessionID сохраняется в cookies и автоматически добавляется в каждый запрос.

Так сервер понимает, какой пользователь прислал запрос, и с какой информацией работать.

🔸 На клиенте

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

Браузер отправил логин-пароль — получил обратно имя пользователя и количество накопленных баллов. Сохранил у себя.

Пользователю интересны варианты доставки? В запросе отправляется город, накопленные баллы и другая информация для расчёта.

И тут вопрос — что мешает клиенту передать ложную информацию? Например, что у него 9999999 бонусных баллов.

Тут мы подходим к JWT, он гарантирует корректность присланных ранее данных. Как это работает:

1️⃣ Сервер шлёт какую-то информацию и подписывает её:

"bonus":10
"bonus sign":"Dfhdy76" 

Подпись, напомню, вычисляется из хэша данных и приватного ключа сервера.

2️⃣ Клиент хранит данные у себя и обратно отправляет вместе с той же подписью:

"city":"moscow"
"bonus":10 
"bonus sign":"Dfhdy76" 

3️⃣ Сервер проверяет корректность своим публичным ключом. Если клиент пришлёт "bonus" : 99999, то сервер сразу распознает обман.

JWT токен состоит из 3х частей:

▪️ Заголовок с алгоритмом подписи:

{"alg":"HS256", "typ":"JWT"}

▪️ Что-то полезное:

{"bonus":10, "status":"vip"}

▪️ Подпись

По сути это два JSON и строка. Чтобы передавать это как цельный объект, каждая часть кодируется Base64. Части соединяются между собой через точку в одну строку:

eyJh.TYDkwI.SflKxwRJSM

И хотя механизм универсальный, чаще всего он используется для авторизации и помогает серверу понять, кто выполняет запрос:

🔹 Пользователь вводит логин пароль
🔹 Сервер отвечает JWT токеном, внутри которого что-то вроде

"userId":34563847638

🔹 Токен каждый раз передаётся в хэдере HTTP запроса
🔹 Сервер валидирует подпись

Важные дополнения:

JWT ничего не шифрует, только заверяет подлинность данных. Поэтому в JWT токенах не следует передавать пароли или что-то секретное.

Важно, чтобы JWT токены хранились и передавались безопасно. Ведь если токен с авторизацией перехватит злоумышленник, то он сможет выдать себя за пользователя.

Что делать: использовать HTTPS и самые новые версии браузеров с безопасным хранением cookies.

В принципе это всё, что нужно для базового понимания JWT. Больше деталей:
▫️ JWT Security Best Practices
▫️ Спецификация JWT

Интерфейсы, часть 1: поля и методы

Интерфейс — базовый механизм джавы для поддержки ООП, а также главный герой этой недели🦸🏼‍♂️

🔸 Какие методы можно добавить в интерфейс в разных версиях java?

Java 7 — только нестатические public методы:

interface Интерфейс {
  public void метод();
}

Классы реализуют эти методы под угрозой ошибки компиляции.

Java 8 — плюс 2 возможности:

▪️Методы по умолчанию с заданной реализацией:

default void метод() {…};

Конкретный класс переопределяет его при необходимости. Дефолтные методы уместны в трёх случаях, об этом будет статья в среду.

▪️ Статические методы с реализацией:

static void метод() {…};

Статические методы не наследуются и не переопределяются. Вызвать такой метод можно только через имя интерфейса:

Интерфейс.метод()

Зачем он нужен?

В интерфейсе определяется необходимый минимум методов. Например, в Collection это методы add(), remove() и пара других. Чем меньше методов, тем больше свободы действий у конкретных классов.

Эти базовые методы комбинируются между собой в другие полезные методы:
▪️Поиск элемента,
▪️Поиск минимального элемента
▪️Скопировать коллекцию

Каждый из этих методов — всего лишь комбинация базовых, которая не зависит от конкретного класса. Чтобы не копировать код в каждый класс, удобно вынести его в статический метод в интерфейсе:

static E copy() {…};

До java 8 статические методы часто объединяли в утилитный класс с похожим именем. Например, методы binarySearch, copy, min реализованы в классе Collections.

Java 9 — добавились private и private static методы с реализацией:

private void m() {…};
private static void m() {…};

Эти методы недоступны для классов, реализующих интерфейс.

Зачем они нужны?

Код внутри дефолтных и статических методов может дублироваться. Чтобы улучшить читаемость, можно вынести общие части в приватный метод.

🔸 С методами разобрались, а какие поля можно добавлять в интерфейс?

Только константы с модификаторами public static. Из-за того, что других вариантов нет, в Intellij IDEA public и static подсвечиваются как избыточные и вместо

public static int NUM = 1;

допустима запись:

int NUM = 1;

Такие поля компилируются в статические!

🔸 Правильный ответ на вопрос перед постом

Ошибку компиляции в последней версии java вызовут:

default int get();
private int get();
public static int get();

У приватных, статических и default методов в интерфейсах должна быть реализация.

​Вопрос 1. Что выведется на консоль?

​Вопрос 2. Что выведется в консоль?

(интерфейс В теперь расширяет интерфейс А)

Интерфейсы, часть 2: методы по умолчанию

Когда готовила материал по дефолтным методам, то перечитала почти все переписки разработчиков этой фичи. Огромное удовольствие — следить за спором опытных людей с высокой инженерной культурой и мощными теоретическими знаниями. Профессионализм завораживает🥰

Но я расскажу вам итог. В java 8 появилась новая возможность — методы с заданной реализацией:

interface Adapter {
   default int get() {…}
}

Класс, который реализует интерфейс, переопределяет такой метод при необходимости.

❓Зачем?

1️⃣ Облегчить изменения API

Во времена java 7 в интерфейсах были только определения методов:

interface Collection<Т> {
   void add(Т);
   Т get();
}

Чтобы добавить, удалить или поменять сигнатуру метода нужно одновременно поменять код и в интерфейсе, и во всех реализациях. Если всё в рамках одного проекта, то проблем нет. Но если мы пишем библиотеку, то задача усложняется. Пользователи могут столкнутся с проблемами совместимости при переходе на новую версию.

Задача дефолтных методов — сгладить этот процесс, предоставить приемлемую или временную альтернативу. В JDK основная цель дефолтных методов — поддержка Stream API в коллекциях.

2️⃣ Вспомогательные методы

Которые не входят в прямую функциональность интерфейса, но их удобно добавить сюда, а не в каждый класс реализации. Нарушается принцип Interface segregation и часто похоже на костыль. Не одобряю, но такое встречается🙂

3️⃣ Комбинации базовых методов

Мы обсуждали это в прошлом посте. В интерфейсе есть методы, которые по сути — комбинация других методов этого же интерфейса.

Для таких комбинаций можно сделать статический метод. Он вызываются через имя интерфейса и недоступен у экземпляров. Если это неудобно, метод можно сделать как метод по умолчанию.

Пример: интерфейс Comparator

Цепочка из 2 компараторов — это 2 вызова compare и объединение результатов. Логика всегда одинакова, и нет смысла дублировать её в каждом подклассе:

default Comparator thenComparing(Comparator) {…};

❓Что если класс реализует 2 интерфейса с методами по умолчанию?

Правила такие:
🔸 Если в классе переопределён метод по умолчанию — используется метод класса
🔸 Если один интерфейс наследуется от другого — используется метод наследника
🔸 В остальных случаях — ошибка компиляции

Отсюда ответы на вопросы перед постом:
1️⃣ Ошибка компиляции
2️⃣ Напечатается В

Интерфейсы, часть 3: разница с абстрактным классом

Отличия интерфейса и абстрактного класса — супер популярный вопрос на собеседовании. Во времена java 7 ответ был простой: "В интерфейсе нет реализаций".

Сейчас мир стал сложнее, и в интерфейсе есть приватные, статические и дефолтные методы с готовой реализацией. Это сближает интерфейсы с абстрактными классами.

❓В чём теперь разница интерфейса и абстрактного класса?

🛠 Функциональность

В абстрактный класс можно добавить многое:
▪️Конструктор
▪️Реализация экземплярных методов
▪️Нестатические поля
▪️private static поля
▪️Модификаторы final, synchronized, protected

Интерфейс сильно ограничен:
▪️Только статические поля
▪️Методам с реализацией недоступны экземплярные поля, поэтому их возможности слабее

✍🏻 Синтаксис

Абстрактный класс:
▫️ Ключевое слово extends
▫️ В имени часто содержится Abstract, Template, Base
▫️ Класс реализует не больше одного абстрактного класса

Интерфейс:
▫️ Ключевое слово implements
▫️ Класс может реализовать несколько интерфейсов
▫️ 5 лет назад интерфейсам было модно добавлять суффикс able: Iterable, Comparable. Норма сегодняшнего дня — называть интерфейс по тем же правилам, что и класс.

💫 Назначение

Абстрактный класс — шаблон класса. Вспомогательная структура, чтобы не дублировать код в классах одной иерархии.

Интерфейс описывает методы для верхнеуровнего взаимодействия с классом, модулем или системой.

⭐️ Репутация

Абстрактный класс сокращает объем необходимого кода, когда иерархия классов конечна или известна заранее. Большое количество абстрактных классов считается анти-паттерном, у такой системы плохая читаемость, и в неё сложно вносить изменения.

Интерфейс используется в большинстве паттернов GoF и принципах SOLID. Поддерживает инкапсуляцию.

Настоящий сеньор

Иногда в айтишных разговорах проскакивают фразы:

— Я уже полгода сеньор, но чувствую себя мидлом
— Вроде сеньор, но задачи делаю те же, что и раньше
— Мне слишком много платят за ту ерунду, которую я делаю

Это типичный синдром самозванца, и жить с ним неприятно. Что может помочь:

1️⃣ Признать текущие заслуги

"Настоящий сеньор" — это как настоящий мужчина. Как будто он делает что-то особенное, чтобы стань "настоящим".

Сеньором не делают заранее, должность выдают по факту. Будучи мидлом вы уже делали сеньорные задачи. Так что на текущем проекте вы точно на своём месте👍

2️⃣ Следить за общей ситуацией

Даже если не хотите менять работу, полезно раз в полгода-год следить за рынком:

◾️ Обновить резюме и вписать последние достижения
◾️ Посмотреть 20 вакансий HeadHunter и наметить план развития
◾️ Походить по собеседованиям и увидеть свои пробелы. Если получится оффер, то самооценка взлетит до небес🙂

В одной компании тебя зовут в СТО, в другой даже джуниором не возьмут. Все проекты разные, и требования везде разные. Расскажу своё видение, чем отличается сеньор от мидла:

Hard skills

▪️ Ориентироваться в популярных технологиях. Зачем нужны, плюсы-минусы, аналоги. Список технологий можно взять здесь. Он 2020 года, но ситуация не слишком поменялась
▪️ Настроить простой CI
▪️ Поднять систему с нуля с простой архитектурой (микросервисы, БД, очереди)
▪️ Работать с перфоманс проблемами. Знать, где посмотреть логи, что смотреть и как проверить, что проблема ушла
▪️ Целостное восприятие IT
Тут сложно дать конкретный список. Просто очень странно выглядит сеньор, который не знает, что такое DNS и как масштабировать БД.

Soft skills

▪️ Самостоятельность
Сеньор может взять любую задачу и продвинуть её решение. Прикинуть, на каком уровне решать задачу (на фронте, в бизнес-логике, поправить конфиги, исправить ошибку в БД). Разбить на подзадачи и определить приоритеты. Сформулировать вопрос, если не хватает данных или компетенций. Предложить разные решения для разных требований

▪️ Контроль джуниоров и мидлов — провести онбординг и код-ревью, понятно отвечать на вопросы и делегировать подходящие задачи

▪️ Психологическая зрелость (не знаю как ещё назвать) — принимать решения в условиях неопределённости, признавать свою неправоту и незнание. Не заметать проблемы под ковёр и понимать приоритеты. Уважительно и продуктивно общаться. Понимать, когда устал/раздражён, и не принимать серьёзных решений в этом состоянии. Спокойно удалять свой код, если он не нужен.

Но ещё раз — чётких стандартов нет. Каждый, кто уже стал сеньором, заслужил этот грейд, проделал большой путь и хорошо делал свою работу🔥

Работа с задачами в Intellij iDEA

Полезно для тех, кто часто переключается между задачами.

1️⃣ Для энтерпрайза

В IDEA можно присоединиться к JIRA или другому таск трекеру, и у каждой задачи автоматически будет свой контекст.

Контекст — это открытые вкладки и git ветка.

Переключаетесь на другую задачу — автоматически открывается её набор вкладок и меняется ветка в гите.

Есть интеграция с популярными таск трекерами: JIRA, Trello, Github, Bugzilla и тд

Как подключить:
File → Settings → Tools → Tasks → Servers → Плюсик в правом верхнем углу

2️⃣ Для личных проектов

Можно сделать свой таск трекер внутри идеи:

Tools → Tasks & Contexts → Open Task

Дальше вводите название задачи. Их список затем доступен в правом верхнем углу.

ОЧЕНЬ полезно, если вы часто переключаетесь между задачами и цените свои вкладочки🥰

У таск трекера в IDEA есть близкая фича — можно следить, сколько времени потрачено на каждую задачу:

File → Settings → Tools → Tasks → Time Tracking → Enable Time Tracking

IDEA показывает только полное время работы. Нельзя посмотреть статистику за день и внести её в корпоративный трекер, так что для рабочих проектов эта фича скорее бесполезна.

Сбой в работе Wildberries

Сегодня необычный пост — расскажу вам новости и слухи🙂

С 14 марта в работе Wildberries наблюдались сбои — главная страница открывается, но пропали данные о прошлых заказах, новые заказы не оформляются, а в личном кабинете не отображается имя пользователя. Компания пишет о технических сбоях, но в интернете ходят слухи, что это хакерская атака.

Известных деталей мало, а я не спец в кибербезопасности. Пишу свои предположения на основе слухов и похожих случаев. На самом деле может быть по-другому.

Вероятный ход событий:

1️⃣ Сотрудник в Wildberries получил письмо со ссылкой, щёлкнул по ней и скачал дроппер.

Дроппер — программа, которая устанавливает другое вредоносное ПО и по возможности нейтрализует защиту ОС. В Windows дропперы часто выключают службу, которая предупреждает о попытках внести изменения в систему.

Письмо выглядит правдоподобно — красивая разметка, официальный стиль, актуальные новости. Это самое популярное начало атаки:

🔸 В начале пандемии COVID-19 компаниям приходили "рекомендации" по безопасной работе

🔸 Руководителю одного банка пришло письмо “журналистки РБК” с просьбой об интервью. Ссылка ведёт якобы на календарь, чтобы назначить удобное время

🔸 Во время белорусских протестов компаниям-партнёрам приходила рассылка: "Мы бастуем, поэтому к вам может прийти прокуратура с проверкой. Посмотрите по ссылке список интересующих их документов"

2️⃣ Сотрудник вышел из корпоративной сети, и дроппер скачал вредоносное ПО, который настроил удалённый доступ к компьютеру сотрудника.

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

3️⃣ В продакшн внедряются маячки из Cobalt Strike

Cobalt Strike — это легальный инструмент тестирования безопасности, используется как безопасниками, так и хакерами. По статистике около 2/3 атак на крупные компании выполняется с помощью Cobalt

4️⃣ Удаляются резервные копии

5️⃣ Оставшиеся данные шифруются

6️⃣ Компании приходит письмо

"Пришлите столько-то биткоинов на этот кошелёк и получите дешифратор".

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

❓ Что с картами?

Вайдберрис пишет, что эти данные защищены по стандартам PCI DSS. Но по слухам в Даркнет утекли данные 100к российских карт за последние 3 дня. Я на всякий случай перевыпустила свою карту.

Надеюсь, в ближайшее время появится больше информации, и сама компания опишет ситуацию из первых рук. Тогда опыт Wildberries поможет другим компаниям🙏

Списки — простая структура данных и популярная тема на собеседованиях.

Просят рассказать про строение, оценить сложность операций и случаи использования. Отвечаешь, что в ArrayList быстрый доступ по индексу, а в LinkedList легко вставлять элементы в середину списка. Получаешь оффер🙂

Но это немного скучно, поэтому решила описать более жизненные кейсы и подробнее написать про строение. И самое главное — измерить время работы операций!

🔸 Часть 1: вводная. Строение списков и основные операции
🔸 Часть 2: жизненная. Что и когда использовать в коде

​Какой список в коде ниже заполняется быстрее?

​Списки, часть 1: строение и основные операции

1. Внутреннее устройство

В сердце ArrayList лежит массив:

Object[] elementData;

Размер массива задаётся в конструкторе: new ArrayList(50). Значение по умолчанию — пустой массив.

Структура LinkedList чуть сложнее. Каждый элемент оборачивается в класс:

private static class Node {
   E item;
   Node next;
   Node prev;
}

Т.е сам элемент списка + указатели на следующий и предыдущий элемент.

В объекте LinkedList хранится ссылка на первый и последний элемент списка:

Node first;
Node last;

2. Доступ по индексу: list.get(i) или list.set(i)

ArrayList просто обращается по индексу массива

LinkedList идёт долгим путём. Берёт элемент first идёт по ссылкам, пока не дойдёт до i-го элемента. Затем либо возвращает значение, либо обновляет.

Кажется, что второй подход гораздо дольше. И это правда🙂

Чтобы получить 5000-ый элемент в списке из 10к элементов ArrayList тратит 6 наносекунд, а LinkedList — 8750. Чем больше элементов, тем больше разница.

3. Вставка в середину списка

ArrayList

Допустим, для списка 🟧🟧🟧🟧 вызвали метод add(2, 🦄)

Создаётся новый массив размером +1:
⬜️⬜️⬜️⬜️⬜️

Все элементы старого списка копируются туда так, чтобы образовалось свободное место для нового элемента:
🟧🟧⬜️🟧🟧

Обновляем элемент:
🟧🟧🦄🟧🟧

LinkedList

Рассмотрим тот же метод add(2, 🦄):

▫️ Создаём элемент списка с двумя ссылками: ⬅️🦄➡️
▫️ Идём до текущего элемента 2 и получаем ссылки на элементы 1 и 3
▫️ У элемента 1 обновляем ссылку на next, у 3 — на prev

Само добавление простое, но перед ним нужно пройтись по списку. Это долго, поэтому LinkedList и здесь проигрывает по скорости.

4. Заполнение списка

(см код в вопросе перед постом)

ArrayList

▫️ Создаётся пустой массив
▫️ При первом add размер увеличивается до 10
▫️ При добавлении 11 элемента создаётся новый массив размером 15. Предыдущие элементы копируются, затем добавляется новый
▫️ И так далее: когда места не хватает, создаётся массив в 1.5 раза больше

LinkedList

У текущего tail элемента обновляется ссылка next. Новый объект записывается как tail.

Что работает быстрее?

Интуиция подсказывает, что LinkedList, так как для ArrayList нужно часто переносить элементы в новый массив. На самом деле операции копирования выполняются быстро, так как элементы лежат в памяти рядом, а у процессоров хорошая поддержка этой операции.

Бенчмарки показывают, что до 100к элементов разницы нет, а потом побеждает ArrayList. А при миллионе элементов ArrayList копируется реже и в итоге заполняется в два раза быстрее.

Внизу таблица JMH бенчмарков с моего компьютера. На других железках результаты могут отличаться.

Ответ на вопрос перед постом: для 50к элементов время почти одинаковое.