Привет, друзья, Наггетс, я Молчаливый Ван Эр.
Сегодня давайте изучим знание структуры данных, которое очень полезно для прочных базовых навыков Java.Изучив его, вы почувствуете себя старшим братом, хе-хе. Структура данных, также известная как структура данных, представляет собой структуру для хранения данных.Существует определенная связь между данными и данными.Такая связь включает в себя логическую связь данных, связь хранения данных и операционную связь данных.
В Java структуры данных обычно можно разделить на две категории: линейные структуры данных и нелинейные структуры данных. Ха-ха, это не-слово очень душевное, правда?
Начнем с линейных структур данных.
1) Массив
Вы знаете это с первого взгляда, какString [],int []Этот вид; есть также такие, которые нужно видеть двумя глазами, чтобы видеть сквозь них (см. исходный код), например ArrayList, который инкапсулирует массив внутри.
Самым большим преимуществом структуры данных массива является то, что он может работать в соответствии с нижним индексом (или индексом), При вставке он может быть непосредственно вставлен в определенную позицию в соответствии с нижним индексом, но в то же время все последующие элементы нужно перемещать назад. , чем больше данных нужно переместить, тем больше они устают.
Предположим теперь, что у нас есть ArrayList, мы собираемся добавить элемент 55 в 4-ю позицию (индекс 3).
В этот момент элементы после 5-й позиции в ArrayList будут перемещены назад.
Готов удалить 23 из ArrayList.
В это время элементы с индексами 7, 8 и 9 перемещаются вперед.
Кратко подытожим временную сложность ArrayList, который всем удобно использовать в качестве справочного материала при изучении.
1. По подписке (т.е.get(int index)), временная сложность доступа к элементуO(1), потому что он прямой, сколько бы раз не увеличивались данные, затраты времени остаются прежними.
2. Добавьте элемент (т.е.add()) имеет временную сложностьO(1), потому что он добавляется прямо в конец.
3. Временная сложность удаления элементаO(n), потому что для обхода списка количество данных увеличивается в несколько раз, и время, затрачиваемое на это, также увеличивается в несколько раз.
4. Поиск несортированного списка имеет временную сложностьO(n), потому что список нужно пройти; временная сложность поиска отсортированного списка равнаO(log n), потому что можно использовать метод бинарного поиска, когда данные увеличиваются в n раз, затраты времени увеличиваются в logn раз (лог здесь основан на 2, и каждый поиск исключает половину возможностей).
2) Связанный список
Связанный список прерывист в физическом пространстве хранения, но каждый узел либо знает, кто его следующий узел, либо кто его предыдущий узел, как будто между нами тысячи гор и рек, но есть связь. Подобно LinkedList, это наиболее типичная структура связанного списка, связанная друг с другом по ссылке.
Каждый элемент в LinkedList можно назвать узлом, и каждый узел содержит три элемента: один — это сам элемент, другой — адрес ссылки, указывающий на следующий элемент, а третий — адрес ссылки, указывающий на адрес ссылки предыдущего элемента.
LinkedList выглядит так:
- У первого узла нет предыдущего узла, поэтому prev равен нулю;
- У последнего узла нет следующего узла, поэтому следующий равен нулю;
- Это двусвязный список, каждый узел состоит из трех частей, предыдущего узла и значения.
По сравнению с ArrayList LinkedList имеет следующие преимущества:
1. LinkedList допускает динамическое выделение памяти, что означает, что выделение памяти выполняется компилятором во время выполнения, и нам не нужно указывать размер при объявлении LinkedList.
2. LinkedList не нужно хранить элементы в последовательных позициях, потому что узлы могут указывать следующий узел или предыдущий узел по ссылке. То есть LinkedList очень дешев при вставке и удалении элементов, потому что нет необходимости перемещать другие элементы, нужно только обновить ссылочные адреса предыдущего узла и следующего узла.
3) стек
Стек — очень полезная структура данных, это как стопка тарелок, первая внизу, вторая поверх первой, третья поверх второй, а последняя сверху. Стек следует принципу «последний пришел – первым вышел», также известному как «последним пришел – первым ушел» (сокращенно ЛИФО) – последний пришел, первый ушел.
Для такой структуры данных, как стек, у него есть два общих действия:
-
push, Есть много китайских интерпретаций, я лично предпочитаю называть это "отжим", что очень ярко. Когда мы хотим поместить часть данных на вершину стека, действие вызываетсяpush. -
pop, то же, лично я предпочитаю называть его "попсовым", с очень сильным анимационным эффектом, что ли? Когда мы хотим удалить часть данных из стека, вызывается действиеpop.
4) Очередь
Очередь, разрешить добавление данных только в конец очереди и удаление из начала очереди. Очереди очень часто появляются в Java, и существуют различные классы для удовлетворения потребностей различных сценариев. Например, приоритетная очередь PriorityQueue, очередь задержки DelayQueue и так далее. Очередь следуетFirst In First Out,сокращенноFIFO, то есть первый вошел, первый вышел, первый попавший в очередь первым выходит.
Поговорим о нелинейных структурах данных.
1) дерево
Дерево — это типичная нелинейная структура, представляющая собой совокупность иерархических отношений, состоящую из n (n>0) конечных узлов. Это называется «деревом», потому что эта структура данных выглядит как перевернутое дерево с корнем наверху и листьями внизу. Древовидная структура данных имеет следующие характеристики:
- Каждый узел имеет только ограниченное количество дочерних элементов или не имеет дочерних элементов;
- Узел без родительского узла называется корневым узлом;
- Каждый некорневой узел имеет один и только один родительский узел;
- В дополнение к корневому узлу каждый дочерний узел может быть разделен на несколько непересекающихся поддеревьев.
На следующем рисунке показаны некоторые элементы дерева терминологии:
Корневой узел имеет уровень 0, его дочерние узлы — уровень 1, дочерние узлы — уровень 2 и так далее.
- Глубина: для любого узла n глубина n — это длина уникального пути от корня до n, а глубина корня равна 0.
- Высота: для любого узла n высота n — это длина самого длинного пути от n до листа, а высота всех листьев равна 0.
Деревья можно разделить на следующие категории:
1. Обычное дерево: ограничений на дочерние узлы нет.
2. Двоичное дерево: дерево с не более чем двумя дочерними узлами на узел. Бинарные деревья можно разделить на множество типов в соответствии с различными выражениями.
2.1 Обычное двоичное дерево: Двоичное дерево, в котором родительский узел каждого дочернего узла не обязательно имеет два дочерних узла.
2.2 Полное бинарное дерево: для бинарного дерева предполагается, что его глубина равна d (d>1). За исключением d-го слоя, количество узлов в других слоях достигло максимального значения, и все узлы d-го слоя непрерывно и тесно расположены слева направо.
2.3 Полное бинарное дерево: бинарное дерево с максимальным количеством узлов в каждом слое. Есть две формы выражения.Первая, как показано на рисунке ниже (каждый слой заполнен), удовлетворяет тому, что количество узлов в каждом слое достигает максимального значения 2.
3. Двоичное дерево поиска: английское название Binary Search Tree или BST, которое должно соответствовать следующим условиям:
- Левое поддерево любого узла не пусто, и значение всех узлов левого поддерева меньше значения его корневого узла;
- Правое поддерево любого узла не пусто, и значение всех узлов в правом поддереве больше, чем значение его корневого узла;
- Левое и правое поддеревья любого узла также являются бинарными деревьями поиска соответственно.
3.1. Сбалансированное бинарное дерево: бинарное дерево, если и только если разность высоты между двумя подделками любого узла не превышает 1. Высокобалансированное бинарное дерево, предложенное бывшими советскими математиками Adelse-Velskil и Landis в 1962 году, также называют деревом AVL в соответствии с английским названием ученого.
Бинарное дерево баланса также является бинарным деревом, но для того, чтобы ограничить разницу в высоте левого и правого подмножеств, избегая наклонного дерева и т.п., левый и правый сегменты каждого узла в бинарном дереве поиска. высота левого и правого подтроев является коэффициентом баланса, а абсолютное значение коэффициента баланса каждого узла в дереве не превышает 1.
Сложность балансировки бинарного дерева заключается в том, как поддерживать баланс между левым и правым с помощью левшей или правшей, когда узлы удаляются или добавляются.
Красно-черное дерево — обычное сбалансированное бинарное дерево.Узлы красные или черные.Баланс бинарного дерева поддерживается цветовыми ограничениями:
- Каждый узел может быть только красным или черным
- корневой узел черный
- Каждый листовой узел (узел NIL, пустой узел) черный.
- Если узел красный, оба его дети являются черными. То есть два соседних красных узла не могут появиться на пути.
- Все пути от любого узла к каждому его листу содержат одинаковое количество черных узлов.
4. B-дерево: Самобалансирующееся двоичное дерево поиска, которое оптимизирует операции чтения и записи, поддерживает порядок данных и имеет более двух поддеревьев.
5. Дерево B+: вариант дерева B.
TreeNode в HashMap использует красно-черное дерево, а дерево B и дерево B+ имеют типичные применения в принципе индексации базы данных.
2) Хэш-таблица
Хеш-таблица, также известная как хэш-таблица, представляет собой структуру данных, к которой можно получить прямой доступ через ключ-значение.Ее самая большая особенность заключается в том, что она может быстро выполнять поиск, вставку и удаление. Используемый алгоритм называется хэшированием, которое преобразует входные данные любой длины в выходные данные фиксированной длины, а на выходе получается хэш-значение. Алгоритмы хеширования используются как MD5 и SHA1.
Каждый объект Java будет иметь хэш-значение.По умолчанию алгоритм хеширования выполняется путем вызова собственного метода для вычисления адреса памяти объекта + значения ключа значения объекта.
Самая большая особенность массива заключается в том, что его легко искать, но трудно вставлять и удалять; наоборот, связанный список трудно искать, но легко вставлять и удалять. Хеш-таблица прекрасно сочетает в себе преимущества обоих, и HashMap в Java также добавляет преимущества дерева на этой основе.
Хеш-таблицы имеют высокую скорость запросов (постоянный уровень) и относительно высокую скорость добавления и удаления, поэтому они очень подходят для использования в средах с большими данными.
Для любых двух разных блоков данных вероятность одинакового значения хеш-функции крайне мала, то есть для данного блока данных крайне сложно найти блок данных с одинаковым значением хеш-функции. Кроме того, для блока данных, даже если изменится только один его бит, изменение его хеш-значения будет очень большим — это ценность существования хэша!
Хотя это крайне маловероятно, это все же произойдет.Если произойдет коллизия хешей, HashMap в Java добавит связанный список в ту же позицию массива.Если длина связанного списка больше 8, он будет преобразован в красно-черное дерево для обработки - это так называемый метод зиппер (массив + связанный список).
3) Рисунок
Граф представляет собой сложную нелинейную структуру, состоящую из конечного непустого множества вершин и множества ребер между вершинами, обычно выражаемую как: G(V, E), где G представляет граф, а V — граф в G. Множество вершин, E — множество ребер в графе G.
На приведенном выше рисунке 4 вершины V0, V1, V2, V3, и 5 ребер между 4 вершинами.
В линейной структуре между элементами данных выполняется уникальная линейная связь, и каждый элемент данных (кроме первого и последнего) имеет уникального «предшественника» и «последователя»;
В древовидной структуре существует очевидная иерархическая связь между элементами данных, и каждый элемент данных связан только с одним элементом (родительским узлом) на предыдущем уровне и несколькими элементами (дочерними узлами) на следующем уровне;
В структуре графа отношения между узлами произвольны, и может быть корреляция между любыми двумя элементами данных в графе.
PS: Кстати, я хотел бы порекомендовать ускоренный курс по информатике, который нравится нам с сестрой. Младшая сестра преподала его очень хорошо. Если вы хотите продвинуться дальше в информатике, вы должны взглянуть на этот курс !
Для получения более подробной информации об этом курсе, нажмите эту ссылку, чтобы просмотреть
Короче говоря, в любом случае, хотя вы молоды, узнать больше базовых знаний компьютеров все еще очень ароматно и полезно!Я молчаливый король, который любит учиться и делиться. Если статья была вам полезна, пожалуйста, поставьте лайк. Увидимся в следующем выпуске, увидимся~