Обмен технологиями

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Как выглядит базовая структура данных ArrayList?

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

Механизм расширения ArrayList таков: при добавлении первого элемента емкость ArrayList равна 10 каждый раз, когда добавляется новый элемент, если емкость превышена, исходная емкость будет удвоена, то есть исходная емкость * 2; , если исходная емкость равна 0, то новая емкость равна 1.

Преимущества и недостатки механизма расширения ArrayList:

преимущество:

1. Механизм расширения ArrayList прост для понимания и легко реализуется.
2. Расширенная емкость должна быть больше исходной емкости, что позволяет уменьшить количество копий массива при добавлении новых элементов и повысить эффективность добавления элементов.

недостаток:

1. Механизм расширения ArrayList приводит к пустой трате памяти и может легко стать причиной нерациональной траты памяти.
2. Если емкость велика, каждое расширение требует большого объема памяти и ресурсов ЦП, что влияет на производительность. Поэтому при использовании ArrayList необходимо установить начальную емкость соответствующим образом.

ArrayList не является потокобезопасным

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

Общие методы решения проблемы небезопасности потоков ArrayList включают в себя:

1. Используйте Vector вместо ArrayList: Vector синхронизируется, и все методы изменяются с помощью Synchronized, поэтому он является потокобезопасным;
2. Оберните ArrayList в потокобезопасность: используйте метод Collections.synchronizedList(list) для преобразования ArrayList в потокобезопасность;
3. Используйте CopyOnWriteArrayList: это потокобезопасная и эффективная коллекция. Операция записи реализуется путем копирования базового массива. Стоимость этой реализации находится в пределах приемлемого диапазона. Она подходит для параллельных сценариев с большим количеством чтения и меньшим количеством записи.
4. Используйте блокировки для обеспечения потокобезопасности. Вы можете использовать механизмы блокировки, такие как ReentrantLock, для реализации потокобезопасного ArrayList.

Разница между стеком и кучей

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

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

Нижний слой сопрограммы

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

Принцип C# GC (сборка мусора)

1. Подсчет ссылок: когда на объект ссылаются, его счетчик ссылок увеличивается на 1. Когда ссылка становится недействительной, его счетчик ссылок уменьшается на 1. Если счетчик ссылок объекта становится равным 0, объект будет утилизирован сборщиком мусора.
2. Пометить и очистить: когда сборщик мусора работает, он обходит объекты в соответствии со ссылочными отношениями, помечает доступные объекты как «живые», помечает недоступные объекты как «мертвые», а затем очищает все объекты, помеченные как «мертвые».
3. Алгоритм копирования: сборщик мусора делит доступную память на два блока и использует только один блок за раз. Когда места недостаточно, оставшиеся объекты копируются в другой блок пространства, а затем скопированные объекты удаляются из оригинала. космос.
4. Алгоритм пометки-дополнения: когда сборщик мусора работает, он сначала помечает все уцелевшие объекты, а затем перемещает все уцелевшие объекты в один конец, чтобы очистить неиспользуемые фрагменты пространства.

Разница между синхронизацией статуса и синхронизацией кадров

Государственная синхронизация Это относится к передаче статуса (например, положения, скорости, ускорения и т. д.) каждой машины в многомашинной системе другим машинам в каждом цикле управления, чтобы каждая машина оставалась синхронизированной. Синхронизация состояний может обеспечить эффективность совместного управления несколькими машинами в реальном времени, но поскольку в каждом цикле управления необходимо передавать большой объем данных, ее точность может быть относительно низкой.

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

Общие шаблоны проектирования

Шаблон Синглтон

Заводской образец

Составной узор

Шаблон прокси

Характеристики связанных списков, двоичных деревьев и хеш-таблиц

1. Связанный список:

• Это линейная структура списка, которая характеризуется тем, что каждый узел имеет указатель, указывающий на следующий узел, образуя таким образом связанный список;
• Независимо от вставки или удаления узла, вам нужно только изменить направление указателя, а временная сложность равна O(1);
• Временная сложность поиска узла равна O(n), и искать нужно по порядку, начиная с головного узла;
• Связанным спискам не нужно учитывать вопросы распределения пространства. Обычно динамическое выделение памяти используется для достижения гибкого управления памятью.

2. Бинарное дерево:

• Бинарное дерево — это древовидная структура, в которой каждый узел имеет не более двух дочерних элементов;
• Временная сложность операций поиска, вставки и удаления бинарного дерева составляет O(log2n), O(log2n) и O(log2n) соответственно;
• Поскольку каждый узел двоичного дерева не хранится непрерывно, а хранится иерархически, и у каждого узла может быть только два дочерних узла, пространство хранения можно использовать более эффективно.

3. Хэш-таблица:

• Хэш-таблица — это структура данных, которая сопоставляет ключ с местоположением в таблице для доступа к записям и ускорения поиска;
• Сложность времени поиска хеш-таблицы равна O(1), а сложность времени вставки и удаления равна O(n);
• Реализация хеш-таблицы требует дополнительного места для хранения самой хеш-таблицы, а также необходимо решить проблему хеш-коллизий.

Основной принцип HashMap

Нижний уровень HashMap реализован с использованием связанного списка массива (красно-черное дерево). Он хранит данные в соответствии со значением ключа hashCode. Он может вычислять положение данных в массиве (конфликт хеша) на основе хеша. код и использует связанный список (красно-черное дерево) для хранения конфликтов данных. HashMap В Java 8, когда длина связанного списка превышает пороговое значение (по умолчанию — 8), он преобразуется в красно-черное дерево для повышения эффективности запросов.Когда мощности недостаточно, она автоматически расширяется. Коэффициент загрузки по умолчанию составляет 0,75, а метод расширения в 2 раза превышает емкость.

Как определить, есть ли в связанном списке цикл

1. Используйте хеш-таблицу для обхода каждого узла в связанном списке и сохранения адреса узла в хеш-таблице. Если текущий узел уже существует в хеш-таблице, это означает, что связанный список имеет цикл;
2. Определите два указателя: медленный указатель перемещается на один шаг за раз, а быстрый указатель перемещается на два шага за раз. Если быстрый указатель сталкивается с медленным указателем, это означает, что связанный список имеет цикл.

Каковы сценарии использования стеков и очередей?

Функции браузера вперед и назад. Веб-страницы, посещаемые браузером, могут реализовывать функции вперед и назад через структуру данных стека.

Знаете ли вы что-нибудь о проблеме липкости TCP?

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

Способы решения проблемы липкости TCP:

1. Добавьте разделитель на отправляющей стороне: добавьте разделитель на отправляющей стороне. После того как принимающая сторона получит разделитель, она может разделить данные на основе разделителя.
2. Добавить заголовок на отправляющей стороне: передающая сторона добавляет заголовок перед отправкой данных. Заголовок содержит информацию о длине текущих данных. Принимающая сторона разделяет данные на основе информации о длине в заголовке.
3. Добавьте буфер на отправляющей стороне: перед отправкой данных отправляющая сторона сначала помещает данные в буфер и каждый раз отправляет только часть данных в буфер. После получения данных принимающая сторона определяет, отправлять ли их. данные на основе общей длины данных.

Как реализовать простой TCP с использованием UDP

Прежде всего, дейтаграммы UDP могут помочь реализовать процесс трехэтапного установления связи в протоколе TCP/IP. При первом установлении связи клиент отправляет датаграмму UDP, содержащую запрос на установление связи. Когда сервер получит это сообщение, он ответит подтверждающим сообщением, указывающим, что сервер получил запрос на установление связи от клиента и готов предоставлять услуги. При втором рукопожатии клиент снова отправит датаграмму UDP. На этот раз сообщение содержит некоторую полезную информацию, такую ​​как IP-адрес клиента, номер порта и т. д., чтобы сервер мог идентифицировать клиента. При третьем рукопожатии сервер отправит датаграмму UDP, указывающую, что соединение установлено и клиент может начать отправку данных.

Во-вторых, дейтаграммы UDP также могут помочь реализовать процесс передачи данных в протоколе TCP/IP. Когда клиенту необходимо отправить данные на сервер, данные будут инкапсулированы в дейтаграмму UDP и отправлены на сервер. После того, как сервер получит дейтаграмму UDP, он проанализирует данные, содержащиеся в сообщении, и выполнит соответствующую обработку.

Наконец, дейтаграммы UDP также могут помочь реализовать процесс завершения в протоколе TCP/IP.Когда клиенту больше не нужно связываться с сервером, он может отправить дейтаграмму UDP, чтобы указать, что клиент завершает соединение. После того, как сервер получит это сообщение, он освободит соответствующие ресурсы, тем самым завершив работу всего протокола TCP/IP. . процесс подключения

Вы использовали сопрограммы? Зачем использовать сопрограммы?Почему сопрограммы работают быстрее

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

Быстрее ли перемещаться по массиву или связанному списку одинаковой длины? Почему?

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

Давайте поговорим о виртуальных функциях. Зачем нам виртуальные функции?

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

Может ли деструктор быть виртуальной функцией? Должна ли это быть виртуальная функция? Почему? В чем проблема, если это не виртуальная функция?

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

Знакомство с конвейером рендеринга

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

Процесс конвейера рендеринга разделен на три основных этапа: этап подготовки, этап геометрии и этап освещения.

На этапе подготовки игровой движок загружает модели и текстуры игровой сцены в графический процессор (GPU) и организует данные для использования на последующих этапах.

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

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

Давайте поговорим об операциях вставки, запроса и удаления в деревьях двоичного поиска и какова временная сложность?

1. вставлять:

• Временная сложность: O(log n)
• Шаги:

1. Рассматривайте узел, который нужно вставить, как новый листовой узел, начиная с корневого узла;
2. Если значение вставляемого узла меньше текущего значения узла, перейдите к левому дочернему узлу текущего узла;
3. Если значение вставляемого узла больше текущего значения узла, перейдите к правому дочернему узлу текущего узла;
4. Если текущий узел не имеет дочерних узлов, вставляемый узел будет дочерним узлом текущего узла;
5. В противном случае повторяйте шаги со 2 по 4, пока не будет найден узел без дочерних узлов, а вставляемый узел не будет использоваться в качестве дочернего узла этого узла.

Каковы условия получения оптимального решения жадным алгоритмом?

Условиями получения оптимального решения жадным алгоритмом являются «оптимальная подструктура» и «свойство жадного выбора»:

1. Оптимальная подструктура: оптимальное решение проблемы содержит оптимальные решения подзадач проблемы;
2. Свойство жадного выбора: на каждом этапе делается локальный оптимальный выбор, а конечным результатом является глобальное оптимальное решение.