В течение долгого времени список данных, который чаще используется в коде, в основном список, и все они являются ArrayList. Такое ощущение, что этой вещи достаточно. ArrayList - это класс инструментов обертки, используемый для реализации динамических массивов, так что при написании кода вы можете втягивать и выходить, итерация и траверса, что довольно удобно.
Я не знаю, когда я начал медленно запускать классы инструментов, такие как Hashmap и Hashset, часто появляются в коде. Следует сказать, что HashMap встречается чаще, и это также классический вопрос интервью, поэтому я буду читать его в повседневной жизни. Когда я впервые начал использовать его, я просто понял это как таблицу соответствующей клавиш, и это удобнее использовать ключи для поиска данных. После дальнейшего расследования я узнал
У этой вещи есть некоторые секреты, особенно после новой версии JDK изменяют хэшмап на дерево, код немного сложный.
Я начал использовать набор меньше, но я случайно нашел деревья в коде. Я обнаружил, что этот класс может прийти с гладкостью. Это было довольно интересно. Я постепенно обнаружил, что это также хороший инструмент.
Если вы напишете слишком много кода, вы почувствуете важность основ, поэтому я пишу короткую статью, чтобы кратко организовать некоторые знания о коллекции.
Хорошо, давайте кратко разберем это:
• Список: то есть список, который поддерживает функции массивов и связанных списков, и, как правило, является линейным.
• Карта: это таблица отображения, которая хранит соответствующую связь между ключами и значениями.
• Установить: означает, что установка, в основном используется для сортировки данных и сортировки
Давайте сначала рассмотрим список
Список - это окно для хранения линейных данных, таких как: ArrayList для массивов и LinkedList для связанных списков.
ArrayList
Это список массивов, но он предоставляет функцию автоматического расширения для реализации интерфейса списка. Внешние операции доступны с помощью метода объявления интерфейса, который является безопасным и удобным.
Ключом к ArrayList является автоматическое расширение емкости. Начальная емкость может быть установлена при инициализировании объекта или может быть измерена емкость по умолчанию. Если размер массива не особенно ясен, начальный размер не может быть указан. Если это ясно, может быть указан размер, который уменьшает задержку, вызванную динамическим расширением. Говоря об этом, нам нужно поговорить о том, как осуществляется расширение. Посмотрите на следующий код:
private void grow (int mincapacity) {// переполненный код int oldCapacity = elementData.length; int newCapacity = OldCapacity + (OldCapacity >> 1); if (newcapacity - mincapacity <0) newcapacity = mincapacity; if (newcapacity - max_array_size> 0) newcapacity = gugecapacity (mincapacity); // mincapacity обычно близка к размеру, так что это победа: elementData = arrays.copyof (elementdata, newcapacity); }Grow - это метод, который запускает ArrayList при добавлении элементов или некоторых простых проверок. Основной процесс:
1. Получите длину массива и переместите его направо, что эквивалентно OldCapacity/2, и получите новую длину
2. Если эта длина меньше минимальной емкости, ее легко использовать напрямую.
3. Если это больше, чем максимум, возьмите максимальное значение. Здесь будет вызван метод Hugecapacity, в основном для сравнения Mincapacity с max_array_size. Если Mincapacity больше, чем max_array_size, возьмите Integer.max_value, в противном случае возьмите max_array_size. Интересно, что max_array_size принимает integer.max_value - 8; Я не знаю, что значит это делать
4. Наконец, вызовите метод копирования, чтобы скопировать существующий номер в новый массив.
Из -за этого процесса копирования, если массив относительно большой, то расширение, безусловно, вызовет отставание. Поэтому, если вы знаете максимальное значение с самого начала, и его легко вырастить до этого значения, то указать размер при запуске инициализации будет иметь определенный эффект.
LinkedList
Это класс инструментов для связанных списков. Преимущества связанных списков заключаются в том, что они добавляют и удаляют вещи быстрее, но они найдут их медленными.
Что касается кода, кажется, что нет ничего особенного, что он связан вместе строкой указателей. Конечно, Java использует объекты вместо этого для создания объекта узла. Сам узел указывает на предыдущий узел и следующий узел. Это структура связанного списка:
Частный статический класс узел <e> {e item; Узел <e> Далее; Узел <e> prev; Node (Node <e> prev, e element, node <e> Далее) {this.item = element; this.next = Далее; this.prev = prev; }}Затем используйте два узла, чтобы указать на голову и хвост, и это сделано. Следующий код:
/*** Указатель на первый узел. * Invariant: (First == null && last == null) || * (first.prev == null && first.item! = null) */ переходной узел <e> First; /*** Указатель на последний узел. * Invariant: (First == null && last == null) || * (last.next == null && last.item! = null) */ переходной узел <e> последний;
Смотрите операцию добавления:
/*** Ссылки E как последний элемент. */ void linklast (e e) {final node <e> l = last; Окончательный узел <e> newnode = new Node <> (l, e, null); последний = newNode; if (l == null) first = newnode; else l.next = newnode; размер ++; modcount ++; }Прошлое:
1. Получите последний узел и положите его в L
2. Создайте новый узел и принесите данные в этот узел. Процесс создания будет указывать на прежнюю новую узла на L, так что он будет подключен к цепочке.
3. Затем укажите последнее на этот новый узел
4. Затем определите, является ли L null. Если NULL является нулевым, это означает, что это пустой связанный список. Новый узел - первый элемент. Таким образом, первый должен также указывать на NewNode
5. Если он не пуст, укажите следующее L на NewNode
6. Счетчик накопления
Операция удаления также представляет собой передний и задний узел, указывающий на операцию перемещения этого узла.
Давайте посмотрим на карту
Карта - это применение таблицы отображения для ключей и значений. Основные классы реализации: Hashmap, Hashtable, TreeMap
Hashmap и Hashtable
HashMap-это тот, который использует хэш-алгоритм для картирования ключей. Hashtable-это безопасный класс с синхронизацией. Это основное различие между ними. Принцип похож, и все они достигаются с помощью комбинации ведра + цепи. Ведро используется для хранения ключей, и значение должно храниться в связанном списке из -за хэш -столкновения.
• Значение ведра заключается в эффективности и может быть расположена на один шаг через хэш -расчеты.
• Значение связанных списков заключается в доступе к данным повторного хэша
Конкретный принцип, который я написал, «Учебные заметки: хэштибель и хэшмап» до
Но я только что видел, что HashMap JDK1.8 изменил свою структуру хранения и принимает красную и черную структуру дерева. Это может решить эффективность связанного поиска списка? Не было проведено подробное исследование.
ТРИМАП
После прочтения кода TreeMap я обнаружил, что все еще использую структуру дерева, красные и черные деревья. Поскольку заказаны красные и черные деревья, они, естественно, имеют функцию сортировки. Конечно, вы также можете указать метод сравнения через компаратор для достижения конкретной сортировки.
Поскольку структура дерева используется для хранения, будет более хлопотно добавлять и удалять данные. Давайте посмотрим на код PUT:
public v put (k key, v value) {inpit <k, v> t = root; if (t == null) {compare (key, key); // введите (и возможный null) проверьте root = новая запись <> (ключ, значение, null); размер = 1; modcount ++; вернуть ноль; } int cmp; Вход <K, V> родитель; // разделить компаратор и сопоставимые пути компаратор <? Super k> cpr = компаратор; if (cpr! = null) {do {parent = t; cmp = cpr.compare (key, t.key); if (cmp <0) t = t.left; иначе if (cmp> 0) t = t.right; else return t.setValue (значение); } while (t! = null); } else {if (key == null) бросить новый nullpointerException (); @Suppresswarnings ("не контролировал") сопоставимо <? Super K> k = (сопоставимый <? Super K>) ключ; do {parent = t; cmp = k.compareto (t.key); if (cmp <0) t = t.left; иначе if (cmp> 0) t = t.right; else return t.setValue (значение); } while (t! = null); } Inpit <K, v> e = новая запись <> (ключ, значение, родитель); if (cmp <0) parent.left = e; else parent.right = e; fixafterinsertion (e); размер ++; modcount ++; вернуть ноль; }1. Сначала проверьте, существует ли корневой узел. Если его не существует, это означает, что это первая часть данных и непосредственно используется в качестве корня дерева.
2. Определите, есть ли компаратор. Если есть, используйте компаратор, чтобы найти место хранения данных. Если результат возврата компаратора составляет меньше 0, возьмите влево и возьмите вправо, в противном случае замените значение текущего узла напрямую.
3. Если нет компаратора, ключ напрямую сравнивается с ключом узла. Сравнение такое же, как и предыдущий метод.
4. Следующим шагом является создание детского узла на найденном родителе и положить его в левый или правый дочерний узлы.
5. FixAfterinSertion - это цветные узлы
6. Обработка аккумулятора
Это также будет немного неприятным при удалении данных. В дополнение к удалению данных, вам также необходимо перебалансировать красные и черные деревья.
Кроме того, TreeMap реализует интерфейс NavigableMap <K, V>, поэтому он также предоставляет некоторые операции возврата в наборе данных.
Наконец, посмотрите на набор
Установка в основном имеет два типа приложений: Hashset и Treesset.
Хэшсет
Литеральное значение очень ясное, используя коллекцию хэша. Характеристикой этой коллекции является использование алгоритма хэша для хранения данных, чтобы данные не дублируются, а доступ относительно быстрый. Как это было сделано?
public boolean add (e e) {return map.put (e, present) == null; }Оказывается, есть объект карты. Давайте посмотрим, что такое карта?
частная переходная Hashmap <E, Object> Map;
Это хэшмата. Те, кто знает HashMap, поймут, что такие данные не будут повторяться. Поскольку сам объект хранится в качестве ключа при отказании, в Hashmap будет существовать только одна копия.
Понимая это и другие вещи, вы очень хорошо поймете.
Деревья
Этот набор используется для сортировки набора, что означает, что в дополнение к способности сортировать тяжелые, он также может иметь свою собственную функцию сортировки. Но, посмотрев на Кодекс Treesset, я обнаружил, что он был реализован в основах TreeMap. Точнее, это должен быть полученный класс NavigableMap. Treesset основан на TreeMap без указания карты по умолчанию.
public reeset () {this (new TreeMap <E, Object> ()); }Итак, на что мы можем обратить на себя больше внимания, так это то, как reesset тяжело? Давайте посмотрим на метод добавления:
public boolean add (e e) {return m.put (e, настоящий) == null; }Он несколько похож на хэшсет, оба из которых основаны на особенностях карты для достижения тяжелой нагрузки. Это действительно просто и эффективно.
Выше приведено подробное объяснение набора, списка и карты в Java, которое редактор приносит вам. Я надеюсь, что вы сможете поддержать wulin.com больше ~