начало истории
Недавно я пообщался с некоторыми коллегами, которые только что закончили два или три года обучения, и обнаружил, что большинство студентов заняты развитием бизнеса, и им очень удобно пользоваться своими повседневными инструментами разработки и CRUD. Кроме того, он компетентен для задач разработки, указанных выше, и очень опытен на прикладном уровне, что можно назвать очень квалифицированным «CRUD BOY». Но когда дело доходит до базовых вещей, это кажется немного неуверенным и отрывистым, о чем часто говорят, что базовые навыки не являются твердыми. Столкнувшись с более сложной или даже трудной проблемой, легко почесать голову.
По моему личному опыту, инженеры-разработчики программного обеспечения эквивалентны персонажам романов о боевых искусствах.Если вы хотите достичь более могущественного состояния и стать мастером боевых искусств, то основной предпосылкой должна быть «глубокая внутренняя сила». Все технологии, используемые в разработке программного обеспечения, эквивалентны различным ходам, таким как: микросервисы, большие данные и т. д., которые являются технологиями, созданными для решения некоторых задач сцены. Поэтому, если вы хотите использовать его хорошо, он в основном неотделим от поддержки фонда. Поэтому после того, как вы проучились какое-то время, вы должны оглянуться назад на основы, Чем глубже вы освоите основы, тем глубже будет ваше понимание некоторых технологий. Например, если вы хотите эффективно использовать реестр микросервисов, вам необходимо понимать принцип обнаружения регистрации сервисов и режим связи между сервисами (RPC или HTTP). Также необходимо понимать, что такое CAP, разбираться в алгоритме выборов кластера реестра (типа: raft) и так далее.
Затем в качестве Java-разработки вам необходимо понимать: структуры данных, алгоритмы, модель памяти JVM, параллельное программирование, принципы GC и так далее. Эти базовые вещи могут не использоваться в повседневной разработке, потому что сама Java предоставила много инкапсуляции, и даже некоторые инструменты с открытым исходным кодом в Интернете уже инкапсулировали ее для вас. Но если вы хотите двигаться в направлении промежуточного и продвинутого развития, все содержание, о котором я упомянул, является для вас необходимым курсом. Вы можете выполнять задачи ежедневной разработки, и код может почти работать. Но когда вы идете на собеседование, когда вам задают эти вопросы, разве вы не можете на них ответить? Извини, ГГ. Потому что это то, о чем обязательно спросит интервьюер. Например: когда вас спрашивают о параллельном программировании, как реализуются повторные блокировки? Для чего нужна очередь CLH? Что такое КАС? Это все технологии, которые должны использоваться в параллелизме интернет-продуктов.
Недавно, просматривая это основное содержание, я написал несколько статей в качестве залога для будущих обзоров. С другой стороны, я также надеюсь, что во время рецензирования я также смогу помочь некоторым студентам, которые проигнорировали это содержание, стать квалифицированными программистами. Поэтому я придумал серию статей "Развитие внутренней силы", каждая тема разделена на две части, первая часть в основном знакомит с концепцией и понятно объясняет полезность. Следующая часть в основном связана с реализацией кода для предыдущего выпуска и практикой работы с компьютерным кодом во время обычных интервью, ведь практика приносит истинные знания. В то же время обсуждайте рост со всеми и подружитесь со всеми. В тексте есть даже неуместные вещи.Надеюсь, вы можете напрямую атаковать меня в области сообщений или добавить меня в WeChat.
введите тему
Итак, в первой статье давайте рассмотрим часто используемые линейные структуры данных: массивы, связанные списки, стеки, очереди и хеш-таблицы.
множество
❝Массив — это упорядоченный набор данных одного типа. Массивы описывают несколько данных одного типа, расположенных и объединенных в определенном порядке. Среди них каждые данные называются элементом, и каждый элемент может получить к ним доступ через индекс (индекс).
❞
Давайте сначала посмотрим на картинку (PS: все картинки нарисованы с помощью PPT, что некрасиво, сначала посмотрите на нее)
Вышеупомянутое предназначено для создания массива длиной 6, содержимое таблицы справа — это адрес памяти моделируемого jvm. Массивы обладают следующими характеристиками:
- Длина фиксированная. После создания массива его размер нельзя изменить;
- Его элементы должны быть одного типа, смешанные типы не допускаются;
- Тип массива может быть любым типом данных, включая примитивные типы и ссылочные типы;
- Элементы массива выделяются в куче памяти и размещаются непрерывно;
- Все элементы массива — это серийные номера, причем серийные номера начинаются с 0;
Затем после того, как мы инициализируем массив, мы выделяем непрерывное содержимое, Нам очень удобно получать соответствующее значение через порядковый номер массива, и мы можем свободно получать значение соответствующего элемента массива через порядковый номер. А временная сложность равна o(1), что означает, что значение элемента, соответствующее данным, может быть получено одним запросом. Далее мы рассмотрим еще одну операцию: вставку и удаление.
Когда мы хотим вставить «директор» в третью позицию массива, элемент «пациент» с исходным индексом 2 и следующие элементы должны быть перемещены и переназначены каждому элементу. То же самое относится и к удалению: когда «пациент» должен быть удален, элементы за ним должны быть перемещены, а индексы скопированы снова. Из-за этой функции вставка и удаление не так эффективны, как запросы, а временная сложность вставки и удаления составляет O (n). Таким образом, мы можем знать, что в случае частой вставки и удаления массив не так подходит, особенно в массиве с относительно большим объемом данных.
связанный список
❝Связный список представляет собой непоследовательную и непоследовательную структуру хранения с точки зрения физической структуры хранения.Логический порядок элементов данных реализуется через порядок ссылок в связанном списке.
❞
Существует два типа связанных списков: односвязный список и двусвязный список.
Односвязный список (односвязный список): Он состоит из двух частей: поля данных (Data) и поля узла (Node). Реализация этого принципа реализована через головной указатель области Node node.Каждый узел имеет указатель, причем указатель каждого узла указывает на следующий узел своего узла, а заголовок последнего узла указывает на нулевой.
Двойной связанный список (двухсвязный список): по сравнению с односвязным списком, двусвязный список имеет еще один указатель на хвост (хвост).Каждый узел двусвязного списка имеет головной указатель и хвостовой указатель. с односвязным списком двусвязный список более прост в эксплуатации.Начало первого узла узла двусвязного списка указывает на ноль, а хвост указывает на хвост следующего узла; хвостовой узел указывает на начало предыдущего узла, а хвост указывает на ноль, что является двусторонней связью;
При поиске элемента в односвязном списке поиск должен начинаться с первого элемента.Количество запросов тесно связано с количеством узлов, поэтому временная сложность запроса односвязного списка составляет O(n).В Другими словами, вам нужно только указать следующий из вновь добавленных узлов на следующий узел, а следующий из предыдущих узлов указать на новый узел;
Удаление осуществляется по тому же принципу, если указан следующий узел узла перед удаляемым узлом, следующий узел узла, подлежащего удалению, в порядке. Здесь видно, что вставка и удаление связанного списка могут быть выполнены всего за две операции, независимо от количества узлов, а временная сложность равна O(1). Таким образом, видно, что структура данных связанного списка больше подходит для сценариев с большим количеством вставок и удалений, и ее эффективность, очевидно, намного выше, чем у массивов.
стеки и очереди
❝Стек представляет собой линейную структуру данных (FILO).Характеристикой стека является то, что вставка и удаление данных могут быть достигнуты только через один конец, который называется «верхней частью стека», а соответствующий другой конец называется «дно стека».
❞
❝Очередь также является линейной структурой данных (FIFO), особенностью которой является то, что она позволяет удалять операции только на переднем конце и вставлять операции на заднем конце таблицы.Как и стек, очередь представляет собой линейную таблицу с ограниченными операциями. Конец, выполняющий операцию вставки, называется «хвостом очереди», а конец, выполняющий операцию удаления, называется «головой очереди».
❞
Стеки и очереди также являются наиболее распространенными структурами данных в нашей повседневной разработке, и многие функции могут быть реализованы с использованием их собственных характеристик. Функция стека «первым пришел — последним вышел», мы можем использовать ее в некоторых подходящих сценариях. Например: совпадающие скобки, попарные пары и т. д. Характеристики очередей «первым пришел — первым обслужен» наиболее распространены в наших очередях сообщений, многопоточных двусторонних очередях и т. д. Как и для связанных списков, сложность запроса стеков и очередей составляет O (n), а операции вставки и удаления — 0 (1).Вы можете выбрать в соответствии с подходящим сценарием.
хеш-таблица
❝Хеш-таблица (также называемая хеш-таблицей) — это структура данных, доступ к которой осуществляется напрямую в соответствии со значением ключа. То есть он обращается к записям, сопоставляя значение ключа с местоположением в таблице, чтобы ускорить поиск. Эта функция отображения называется хеш-функцией, а массив записей называется хеш-таблицей.
❞
При использовании хеш-таблицы ключ обычно хешируется первым, то есть входное значение «сжимается» и преобразуется в меньшее значение, обычно уникальное, а формат чрезвычайно компактный. Как показано на картинке (онлайн-кража изображения): ключ лежит в слове, а значение равно 20. После алгоритма хеширования суммируется ascii-код каждой буквы ключа и по модулю длины адреса памяти 30, а затем индекс вычисляется как 9, Затем поместите значение под девятым элементом. Тогда, даже если будет выполнена следующая оценка, значение можно будет получить напрямую через ключ. И временная сложность O (1).
Может показаться, что это немного сложно сказать, думаю, я приведу пример, и вы поймете, самый типичный пример — это словарь. Если я хочу найти подробную информацию о слове «донг», я обязательно посмотрю индекс пиньинь, основанный на пиньинь-дон. Во-первых, я посмотрю расположение слова «дон» в словаре и получу «дон». Этот процесс является отображением кода ключа, В формуле он должен найти f (ключ) через ключ. Среди них dong — это ключевое слово (ключ), найденный номер страницы — это хеш-значение, а значение — это подробная информация о Dong.
хэш-коллизия
Как показано на рисунке: когда ключ "чужие", хеш-значение тоже 429, то будет проблема равных хеш-значений, то есть коллизия хэшей. Решение: метод цепных адресов. Если есть конфликт в принципе метода цепных адресов, он создаст новое пространство по исходному адресу, а затем вставит его в пространство в виде узла связанного списка. Я считаю, что метод цепных адресов наиболее часто используется в отрасли. Как показано на рисунке, «враги» будут добавлены в конец связанного списка, а следующий из «лжи» указывает на узел «враги». Хеш-таблица также является наиболее часто фотографируемой структурой данных в процессе разработки Java, а в Java есть инкапсулированные HashSet, HashMap и т. д., которые могут быть быстро использованы всеми.
В конце концов
Сегодня я кратко рассмотрю распространенные в разработке структуры данных: массивы, связанные списки, стеки, очереди и хеш-таблицы. В следующей части будут представлены некоторые практические сценарии приложений, основанные на содержании этой статьи, и реализованы они с помощью кода. Надеюсь, вы и дальше будете обращать внимание и поддерживать! Давайте добиваться прогресса вместе.
специальное заявление
Данная статья является оригинальной статьей, если вам необходимо перепечатать, пожалуйста, свяжитесь со мной и укажите источник. Спасибо!
"Прошлые статьи:"
«[Развитие внутренней силы, серия 1] Линейная структура данных (Часть II 1)»
«[Внутреннее совершенствование, серия 1] Линейная структура данных (Часть 2)»