🖥 Какая самая страшная структура данных?

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

Некоторые структуры данных в программировании:

◾️ Списки. Подходят для хранения и обработки упорядоченных данных. Полезны в управлении задачами, лентах соцсетей и корзинах интернет-магазинов.

◾️ Массивы. Упорядоченная коллекция элементов фиксированного размера. Подходят для ситуаций, где размер коллекции известен или редко меняется.

◾️ Стеки. Следуют принципу «последним пришёл — первым вышел». Используются для реализации операций отмены/повтора в текстовых редакторах или ведения истории просмотров в веб-браузерах.

◾️ Очереди. Работают по принципу «первым пришёл — первым вышел». Подходят для управления заданиями печати, отправки действий пользователя в играх на сервер или обработки сообщений в чат-приложениях.

◾️ Деревья. Организуют данные иерархически. Полезны для представления данных с естественными иерархиями или связями.

◾️ Графы. Состоят из узлов (вершин) и рёбер, соединяющих эти узлы. Используются для моделирования сетей, таких как социальные сети, транспортные сети и компьютерные сети.

◾️ Хэш-таблицы. Позволяют эффективно искать, вставлять и удалять данные. Используют хэш-функцию для сопоставления ключей с соответствующими местами хранения и обеспечивают доступ к сохранённым значениям за постоянное время.
#программирование #разработка #структуры_данных #алгоритмы #IT #computer_science

💡 Physics.Math.Code // @physics_lib

🖥 Различия в создании строк на Java

Есть два самых популярных способа создания строк:
1 — String s1 = new String("Hello");
2 — String s2 = "Hello";
Разберем отличия.

▪️ 1. Место в памяти (Самое главное отличие) — Это отличие является корнем всех остальных различий.

🔸String s1 = new String("Hello"); (Оператор new)
➖ Создает новый объект в Куче (Heap), независимо от того, какая строка там уже существует.
➖ Каждый вызов new String("Hello") гарантированно создает новый, уникальный объект в памяти.

🔸String s2 = "Hello"; (Строковый литерал)
➖ Строка создается и помещается в специальную область памяти — String Pool (Пул строк), который находится внутри кучи.
➖ Механизм String Pool: Перед созданием новой строки JVM проверяет, нет ли уже строки с таким же значением в пуле. Если есть — переменной просто присваивается ссылка на существующий объект. Если нет — тогда в пуле создается новый объект.

Наглядная аналогия:
➖ new String("Hello") — покупка нового, уникального экземпляра книги, даже если она уже есть в библиотеке.
➖ "Hello" — взятие книги из библиотеки. Если книга есть — вы получаете именно её. Если нет — библиотека сначала покупает новую, а вы её берете.

▪️ 2. Поведение при сравнении (==). Оператор == сравнивает ссылки на объекты, а не их содержимое. Из-за различий в памяти поведение будет разным.

String s1 = new String("Hello");
String s2 = "Hello";
String s3 = "Hello";

System.out.println(s1 == s2); // false
System.out.println(s2 == s3); // true

➖ s1 == s2 -> false, потому что s1 ссылается на объект в куче, а s2 — на объект в String Pool. Это два разных объекта в памяти.
➖ s2 == s3 -> true, потому что обе переменные ссылаются на один и тот же объект в String Pool.
Для сравнения содержимого строк всегда используйте метод equals():

System.out.println(s1.equals(s2)); // true (сравнивается содержимое "Hello")
System.out.println(s2.equals(s3)); // true

▪️ 3. Производительность

🔸Строковый литерал ("Hello") — более эффективен. Он избегает создания дубликатов в памяти, что экономит память и ускоряет работу, так как не нужно создавать новый объект, если он уже существует в пуле.
🔸Оператор new — менее эффективен. Он принудительно создает новый объект в куче, даже если идентичная строка уже существует. Это может привести к избыточному расходу памяти.

▪️ 4. Количество создаваемых объектов

🔸String s1 = new String("Hello"); — Может создать 1 или 2 объекта.
➖ 1. Строковый литерал "Hello" сначала ищется в String Pool. Если его нет — он создается в пуле. (Первый возможный объект).
➖ 2. Затем ключевое слово new создает новый объект String в куче. (Второй объект).
Таким образом, если строка "Hello" ранее не существовала в пуле, эта строка кода создаст два объекта.
🔸String s2 = "Hello";
➖ Создает 0 или 1 объект.
➖ JVM ищет "Hello" в String Pool. Если находит — объект не создается, переменной присваивается существующая ссылка (0 новых объектов).
➖ Если не находит — создает новый объект в String Pool (1 новый объект).

▪️Метод intern() — мостик между двумя подходами. Метод intern() позволяет вручную поместить строку из кучи в String Pool или получить ссылку на уже существующую там строку.

String s1 = new String("Hello");
String s2 = s1.intern(); // Помещаем строку в пул (или получаем ссылку из пула)
String s3 = "Hello";

System.out.println(s1 == s2); // false, т.к. s1 все еще в куче
System.out.println(s2 == s3); // true, т.к. s2 и s3 ссылаются на один объект в пуле

В этом примере s1.intern() находит строку "Hello" в пуле (которая была создана при вычислении литерала внутри конструктора) и возвращает на неё ссылку, которую мы присваиваем s2.

Практический вывод: Почти всегда следует использовать строковые литералы (String s = "value";). Этот способ более эффективен по памяти и времени, так как использует механизм пула строк. #java #задачи #программирование #собеседования #IT #структуры_данных

💡 Physics.Math.Code // @physics_lib

👩‍💻 Java: А есть ли связь между сравнением строк equals() и хешированием hashCode() ?

В Java существует важное правило (контракт):
1. Если две строки равны по equals(), то их hashCode() ДОЛЖЕН быть одинаковым
2. Обратное не обязательно верно: одинаковый hashCode() не гарантирует равенства строк

String s1 = "Hello";
String s2 = "Hello";
String s3 = new String("Hello");

System.out.println(s1.equals(s2));      // true
System.out.println(s1.hashCode() == s2.hashCode()); // true

System.out.println(s1.equals(s3));      // true  
System.out.println(s1.hashCode() == s3.hashCode()); // true

👩‍💻 Как вычисляется hashCode для String

Метод hashCode() в классе String вычисляется на основе содержимого строки:

public int hashCode() {
    int h = hash;  // кэшированное значение
    if (h == 0 && value.length > 0) {
        char val[] = value;
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

➖ Вычисляется по формуле: s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
➖ Результат кэшируется в поле hash для производительности
➖ Для одинакового содержимого всегда одинаковый hashCode, независимо от того, как была создана строка
➖ value и hash — являются полями класса String и уже существуют в объекте, когда вызывается метод hashCode().
value — массив символов, который хранит собственно содержимое строки. Он инициализируется при создании объекта. String s = "Hello"; // value = {'H', 'e', 'l', 'l', 'o'}
hash — поле для кэширования вычисленного хэш-кода. Оно инициализируется по умолчанию значением 0.

Практическое применение в коллекциях: Связь hashCode и equals критически важна для работы хэш-коллекций:

🔸 HashMap/HashSet

Map<String, Integer> map = new HashMap<>();
map.put("Hello", 1);
map.put(new String("Hello"), 2); // Затрет предыдущее значение!

System.out.println(map.size()); // 1 - потому что ключи равны по equals()

1. Сначала сравниваются hashCode() — если разные, объекты точно разные
2. Если hashCode одинаковые, тогда вызывается equals() для точной проверки

🔸 Оптимизация сравнения

String s1 = "very long string ...";
String s2 = "another very long string ...";

// Сначала проверяется hashCode - быстрая операция
if (s1.hashCode() == s2.hashCode() && s1.equals(s2)) {
    // Строки точно равны
}

▪️ 1. Коллизии хэшей — Разные строки могут иметь одинаковый hashCode (хэш-коллизия)

String a = "Aa";
String b = "BB";

System.out.println(a.hashCode()); // 2112
System.out.println(b.hashCode()); // 2112
System.out.println(a.equals(b));  // false

▪️ 2. Производительность

// Медленно - создается новый объект и вычисляется hashCode
String s1 = new String("Hello");

// Быстро - используется кэшированный hashCode из String Pool
String s2 = "Hello";

3. String Pool и hashCode

String s1 = "Hello";
String s2 = "Hello";
String s3 = new String("Hello");

// Все три имеют одинаковый hashCode, но разные способы создания
System.out.println(s1.hashCode()); // одинаковый
System.out.println(s2.hashCode()); // одинаковый  
System.out.println(s3.hashCode()); // одинаковый

🔍 Важные моменты. HashCode тесно связан со сравнением строк через:
1. Контракт Java — равные строки по equals() должны иметь одинаковый hashCode
2.. Оптимизацию сравнения — хэш используется для быстрой предварительной проверки
3. Работу коллекций — HashMap, HashSet и другие используют эту связь для эффективного хранения и поиска
#java #задачи #программирование #собеседования #IT #структуры_данных

💡 Physics.Math.Code // @physics_lib