Брат, посмотри мою коллекцию Java, у тебя еще есть возможность ее оценить?

Java задняя часть

Коллекция используется бесчисленное количество раз в нашей повседневной разработке,ArrayList/LinkedList/HashMap/HashSet  APIнедостаточно, если вызовAPIкогда знаешь, что у него внутри происходит, это как включить透视Просто как плагин, он проникает во все, это ощущение действительно классное, и таким образомДело не в том, какие функции предоставляет нам коллекция, а в том, какие функции мы выбираем для использования..

Обзор платформы коллекций

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

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

  1. Collections Framework предоставляет два интерфейса обхода:IteratorиListIterator, где последнее есть первое优化版, поддержка в любом положенииДвунаправленный обход вперед и назад. Примечание на картинкеCollectionдолжен быть унаследованIterableвместоIterator, что будет объяснено позжеIterableиIteratorразница
  2. Вся структура коллекции делится на две школы (вида):CollectionиMap, первый представляет собой контейнер, в котором хранится рядобъект; последний представляет собой пару ключ-значение<key, value>, в котором хранится серияпара ключ-значение
  3. В рамках системы структуры коллекций выводятся четыре конкретных типа коллекций:Map,Set,List,Queue
  4. Mapместо хранения<key,value>пара ключ-значение, которая передается при поиске элементаkeyнайтиvalue
  5. SetВнутреннее хранилище сериине повторяемыйобъект, и являетсябеспорядокКоллекция, объекты расположены в разном порядке
  6. ListВнутреннее хранилище серииповторяемыйобъект, представляет собойаккуратныйКоллекция, объекты в порядке вставки
  7. QueueЯвляетсяочередьконтейнер, свойства которого такие же, какListто же самое, но только от队头и队尾Элемент действия
  8. JDK предоставляет два служебных класса для различных операций с коллекциями.CollectionsиArrays, а затем объясним общие методы классов инструментов
  9. Существует также множество классов коллекций с различными характеристиками, полученными из четырех абстрактных типов коллекций.Используйте лучшее в разных сценариях, лучшего набора не существует

Компоненты всей системы сбора данных были поняты выше.Следующие главы будут объясняться в строгом соответствии с указанным выше порядком.Каждый шаг будет иметь承上启下роль

учитьсяSetЛучше сначала выучитьMap,так какSetОперация в принципе правильнаяMapоперация, посмотрите вниз вправо

Iterator Iterable ListIterator

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

Первый взглядIteratorинтерфейс:

public interface Iterator<E> {
    boolean hasNext();
    E next();
    void remove();
}

Предоставленный интерфейс API имеет следующие значения:

  • hasNext(): определить, есть ли следующий объект в коллекции
  • next(): возвращает следующий объект в коллекции и перемещает указатель доступа на единицу.
  • remove(): Вызывается для удаления коллекцииnext()объект, возвращаемый методом

В первые дни был только один способ обойти коллекцию, черезIteratorоперации итератора

List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
Iterator iter = list.iterator();
while (iter.hasNext()) {
    Integer next = iter.next();
    System.out.println(next);
    if (next == 2) { iter.remove(); }
}

увидеть сноваIterableинтерфейс:

public interface Iterable<T> {
    Iterator<T> iterator();
    // JDK 1.8
    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }
}

можно увидетьIterableИнтерфейс обеспечиваетIteratorинтерфейс, так реализованныйIterableНабор интерфейсов все еще можно использовать迭代器Обход и управление объектами в коллекции;

пока вJDK 1.8середина,Iterableпредлагает новый методforEach(), который позволяет перебирать объекты с помощью расширенного цикла for.

List<Integer> list = new ArrayList<>();
for (Integer num : list) {
    System.out.println(num);
}

Передаем команду:javap -cПосле декомпиляции приведенного выше кода это всего лишь Java语法糖, по сути звонитIteratorпройти.

Переведено в код, как и в началеIteratorОбход итератора в основном такой же.

Iterator iter = list.iterator();
while (iter.hasNext()) {
    Integer num = iter.next();
    System.out.println(num);
}

Существует более глубокая дискуссия: зачем проектировать два интерфейсаIterableиIterator, вместо того, чтобы сохранить один или другой.

Простое объяснение:IteratorРезервирование может отпускать подклассыРеализовать свой собственный итератор,иIterableИнтерфейсы больше ориентированы наfor-eachрасширенный синтаксис. Для получения подробной информации см.:Подробное объяснение Iterable и Iterator в Java

оIteratorиIterableОбъяснения подходят к концу, и следующее суммирует их ключевые моменты:

  1. Iteratorэто итератор, предоставляющий внутренние объекты для операций сбора, которые могутпройти, удалитьобъект и может толькоодностороннее движение
  2. IterableправдаIteratorпакет, вJDK 1.8, осуществленныйIterableМожно использовать набор интерфейсовУлучшенный цикл forОбходя объект коллекции, мы передаемдекомпилироватьПозже выяснилось, что нижний слой все еще используетсяIteratorитератор для обхода

подождите, эта глава не закончилась, есть еще однаListIterator. Он наследует интерфейс Iterator и проходитListможно собрать излюбой индекс индексаНачать обход и поддержкуДвусторонний обход.

ListIterator существует в коллекции List и может быть возвращен вызовом методаначать индексзаindexитератор

List<Integer> list = new ArrayList<>();
// 返回下标为0的迭代器
ListIterator<Integer> listIter1 = list.listIterator(); 
// 返回下标为5的迭代器
ListIterator<Integer> listIter2 = list.listIterator(5);

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

public interface ListIterator<E> extends Iterator<E> {
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void remove();
    // 替换当前下标的元素,即访问过的最后一个元素
    void set(E e);
    void add(E e);
}

Интерфейсы карт и коллекций

Интерфейс «Карта» и «Коллекция» — две основные школы системы фреймворка коллекций.Коллекция — это сам элемент хранилища, а Карта — это хранилище.<key, value>Пары «ключ-значение», в разделе «Коллекция» есть небольшое количество учеников.偷师, используя учеников секты Карта для самосовершенствования.

Вы запутались, хахаха, давайте возьмем пример, и вы поймете:HashSetдно используетсяHashMap,TreeSetдно используетсяTreeMap,LinkedHashSetдно используетсяLinkedHashMap.

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

MapИнтерфейс определяет хранимую структуру данных.<key, value>формы, в соответствии с ключом сопоставляется со значением, ключ соответствует значению, поэтомуkeyне повторяется иvalueПовторяемый.

существуетMapМетоды хранения подразделяются на разные типы по интерфейсу:

  • SortedMapИнтерфейс: Эту карту классов можно использовать для<key, value>Следуйте своим собственным правиламСортировать, конкретной реализацией является TreeMap
  • AbsractMap: немного лучше для подклассовОбщая реализация API, все определенные Карты, такие какHashMapунаследует это

иCollectionИнтерфейс предоставляет все коллекцииОсновной подход(Обратите внимание, что это не включаетMap):

  • Добавить метод:add(E e) / addAll(Collection<? extends E> var1)
  • Метод удаления:remove(Object var1) / removeAll(Collection<?> var1)
  • Как найти:contains(Object var1) / containsAll(Collection<?> var1);
  • Запросите собственную информацию коллекции:size() / isEmpty()
  • ···

существуетCollectionВ интерфейсе коллекция также подразделяется на разные категории:

  • Setинтерфейс: одинПовторяющиеся элементы не могут быть сохраненыизбеспорядокКоллекция, конкретная реализация имеетHashSet / TreeSet···
  • Listинтерфейс: одинМожет хранить повторяющиеся элементыизаккуратныйКоллекция, конкретная реализация имеетArrayList / LinkedList···
  • Queueинтерфейс: одинМожет хранить повторяющиеся элементыизочередь, конкретная реализация имеетPriorityQueue / ArrayDeque···

Подробное объяснение системы сбора карт

Mapинтерфейс сделан<key, value>набор, состоящий изkeyсопоставить сТолькоизvalue,такMapне может содержать дубликатовkey, каждый ключв большинствеСопоставьте значение. На следующем рисунке показаны основные компоненты всей системы сбора карт, я объясню их один за другим в соответствии с ежедневной частотой использования.

Я должен упомянуть концепцию дизайна карты:позиционированный элементВременная сложность оптимизирована дляO(1)

Система карт в основном делится на два типа: AbstractMap и SortedMap.

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

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

HashMap

HashMap — этосамый универсальныйИспользование хеш-таблицы для хранения набора элементов, когда элементы помещаются в HashMap,keyПреобразуйте хеш-значение в массив索引индексОпределить место хранения, при взгляде вверх, согласноkeyПреобразование хеш-адреса в массив索引индексОпределите, где искать.

Нижний слой HashMap реализован тремя структурами данных: массив + связанный список + красно-черное дерево.Не потокобезопасныйколлекция.

При отправке хэш-коллизий решение HashMap состоит в том, чтобы соединить элементы одного и того же отображаемого адреса в строку.链表, если длина связанного списка больше8, а длина массива больше64будет преобразован в红黑树структура данных.

Кратко о HashMap:

  1. Он наиболее часто используется в коллекции.MapТип коллекции, нижний слой数组 + 链表 + 红黑树сочинение
  2. HashMap не является потокобезопасным
  3. При вставке элемента путем вычисления哈希值,пройти черезфункция хэш-картыпреобразовать в数组下标; При поиске элемента индекс массива также получается через функцию отображения хэша定位元素的位置

LinkedHashMap

LinkedHashMap можно рассматривать какHashMapиLinkedListКомбинация: добавляет двусвязный список на основе HashMap,默认Сохраняет порядок вставки каждого элемента, но из-за этого двусвязного списка можно реализовать LinkedHashMapLRUСтратегия устранения кеша, потому что мы можем установить этот двусвязный список в соответствии с元素的访问次序Сортировать

LinkedHashMap является подклассом HashMap, поэтому он обладает всеми функциями HashMap, а во-вторых, поддерживает双向链表, связанный список хранитвсе элементы,默认Порядок элементов и порядок вставкипоследовательный. какaccessOrderсобственностьtrue, порядок обхода сортируется по порядку доступа к элементам.

// 头节点
transient LinkedHashMap.Entry<K, V> head;
// 尾结点
transient LinkedHashMap.Entry<K, V> tail;

Использование LinkedHashMap позволяет достичьLRUСтратегия удаления кеша, потому что она предоставляет метод:

protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {
    return false;
}

Этот метод может удалить最靠近链表头部узел , в то время какget()В методе можно увидеть следующий код, его роль заключается в перемещении позиции узла:

if (this.accessOrder) {
    this.afterNodeAccess(e);
}

просто позвониget()иaccessOrder = true, узел будет обновлен до связанного списка尾部, конкретная логика вafterNodeAccess(), кому интересно, могут посмотреть исходники, причина пробела здесь расширяться не будет.

Теперь, если вы хотите реализоватьLRUСтратегия кэширования, вам нужно сделать две вещи:

  • уточнитьaccessOrder = trueМожно установить, что связанный список упорядочен в порядке доступа, и может быть установлен через предоставленный конструкторaccessOrder 
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}
  • переписатьremoveEldestEntry()Метод, определяемый внутренней логикой, обычно определяется容量Достигнут ли верхний предел, и если да, то выполняется устранение.

Вот обязательный вопрос для большого заводского интервью:146. Механизм кэширования LRU, пока вы будете следовать моим шагам, вы сможете успешно решить эту большую заводскую задачу.

В LinkedHashMap есть два основных момента:

  1. Он поддерживает双向链表, он также не является потокобезопасным, поскольку наследует HashMap
  2. LinkedHashMap реализуетLRUСтратегия ликвидации кеша, принцип заключается в том, чтобы установитьaccessOrderзаtrueи переписатьremoveEldestEntryМетод определяет условия, которые должны выполняться при исключении элемента.

TreeMap

Карта дереваSortedMap, так и естьСортироватьФункции. это основано на红黑树Реализуется структурой данных, каждая пара ключ-значение<key, value>является узлом, по умолчанию согласноkeyЕстественная сортировка, другая настраивается путем передачиComparatorВыполните сортировку по пользовательскому правилу.

// 按照 key 自然排序，Integer 的自然排序是升序
TreeMap<Integer, Object> naturalSort = new TreeMap<>();
// 定制排序，按照 key 降序排序
TreeMap<Integer, Object> customSort = new TreeMap<>((o1, o2) -> Integer.compare(o2, o1));

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

Каждый узел красно-черного дерева на рисунке представляет собойEntry, для простоты картинки ключ и значение здесь не указаны.Обратите внимание, что эти элементы былиkeyСортировка, вся структура данных сохраняется有序статус!

о自然сортировать с定制Сортировать:

  • Естественная сортировка: требованияkeyдолжны быть реализованыComparableинтерфейс.

так какIntegerКласс реализует интерфейс Comparable в соответствии с естественными правилами упорядочения.keyСортировать от меньшего к большему.

TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(2, "TWO");
treeMap.put(1, "ONE");
System.out.print(treeMap);
// {1=ONE, 2=TWO}
  • Пользовательская сортировка: передать новую при инициализации TreeMapComparator,НетТребоватьkeyРеализовать сопоставимый интерфейс
TreeMap<Integer, String> treeMap = new TreeMap<>((o1, o2) -> Integer.compare(o2, o1));
treeMap.put(1, "ONE");
treeMap.put(2, "TWO");
treeMap.put(4, "FOUR");
treeMap.put(3, "THREE");
System.out.println(treeMap);
// {4=FOUR, 3=THREE, 2=TWO, 1=ONE}

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

compare()Существует три типа возвращаемых значений метода:0,-1,+1

(1) Если вернуться0, что означает, что два элемента равны и их не нужно менять местами

(2) Если вернуться+1, что означает, что предыдущий элемент необходимо поменять местами со следующим элементом

(3) Если вернуться-1, что означает, что предыдущий элемент не нужно менять местами со следующим элементом

и когда вернуться+1и-1, то мы определяем его сами, JDK по умолчанию используетестественный порядок, и мы можемkeyРазница заключается в том, чтобы определить порядок убывания или возрастания.

В TreeMap есть два основных момента:

  1. Нижний слой его红黑树Эта структура данных реализована, поэтому временная сложность операции всегдаO(logN)
  2. TreeMap можетkeyВыполните естественную сортировку или пользовательскую сортировку, которую необходимо передать при пользовательской сортировке.Comparator, тогда как естественный порядок требуетkeyДостигнутоComparableинтерфейс
  3. TreeMap не является потокобезопасным.

WeakHashMap

WeakHashMap относительно редко встречается в повседневной разработке, он основан на обычномMapпонял, находясь внутриEntryключ в каждом垃圾回收будет очищен, поэтому он идеально подходит длякороткий визит, только один визитэлементы, кэшированные вWeakHashMap, и утилизируйте его как можно скорее.

когдаEntryодеялоGCКогда и как WeakHashMap воспринимает переработку элемента?

Эталонная очередь поддерживается внутри WeakHashMap.queue

private final ReferenceQueue<Object> queue = new ReferenceQueue<>();

Эта очередь содержит всеGCСброшенные ключи при запуске JVMGCПосле этого, если ключ в WeakHashMap будет переработан, ключ будет помещен в очередь, а сам ключ будет храниться в очереди.expungeStaleEntries()пройти очередь вkeyВыньте его и удалите в WeakHashMap для достиженияСинхронизировать.

private void expungeStaleEntries() {
    for (Object x; (x = queue.poll()) != null; ) {
        synchronized (queue) {
            // 去 WeakHashMap 中删除该键值对
        }
    }
}

Кроме того, следует отметить, что структура данных элементов, хранящихся в базовом WeakHashMap,数组 + 链表,нет красно-черного дереваО, можно подумать об этом и с другого ракурса, если есть красно-черное дерево, то просто наследуется HashMap напрямую, а потом расширяется и готово, а вот этого не делает:

public class WeakHashMap<K, V> extends AbstractMap<K, V> implements Map<K, V> {
    
}

Поэтому схема структуры данных WeakHashMap также подготовлена ​​для вас.

Элементы, отмеченные на рисунке пунктирной линией, будут удалены при следующем доступе к WeakHashMap, а внутри WeakHashMap будет выполнен ряд корректировок, поэтому помните, что роль очереди состоит в том, чтобы пометить те, которые были удалены.GCПереработанные элементы.

В отношении WeakHashMap следует отметить две вещи:

  1. его ключслабый ключ, при размещении в WeakHashMap он будет переработан в любое время, поэтому нельзя гарантировать, что элемент доступа должен существовать.
  2. он опирается на обычныеMapРеализовано, это коллекция, не являющаяся потокобезопасной.
  3. WeakHashMap обычно используется кактайникиспользования, подходит для хранения техпросто посетите один раз,илиПросто сохраните на короткое времяпара ключ-значение

Hashtable

Базовая структура хранения Hashtable:数组 + 链表, в то время как этопотокобезопасность, но из-за этой безопасности потоков он был устранен.

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

Эта картинка выглядит знакомо, хахахаха, по сути, это базовая структура хранилища WeakHashMap. Не спрашивайте, почему WeakHashMap не наследует Hashtable.性能Очень плохой в параллельной среде, может использоваться в непараллельной средеHashMapлучше.

HashTable, по сути, является предшественником HashMap, и от него отказались в основном из-за двух слов:представление

HashTable — этопотокобезопасность, со всеми его методамиsynchronizedКлючевому слову и из-за этого ключевого слова суждено стать изгоем времени.

Нижний слой HashTable принимаетмассив + связанный списокХранить пары ключ-значение, так как он устарел, в него не было внесено никаких улучшений.

Длина HashTable по умолчанию11, коэффициент нагрузки0.75F, то есть когда количество элементов достигнет 75% от длины массива, он будет расширен один раз, и каждое расширение будет равно длине исходного массива.2раз

Все операции с HashTable потокобезопасны.

Подробная система сбора коллекции

Интерфейс верхнего уровня системы сбора Коллекции:Collection, который определяет ряд поведенческих соглашений в наборе.

Эту коллекцию можно разделить на три типа коллекций: Список, Набор и Очередь.

SetИнтерфейс определяет набор классовНе хранить дубликатыэлементы , и любая операция должна пройтикарта хэш-функцииЧтобы найти элемент внутри коллекции, элемент внутри коллекциидефолтдабеспорядокиз.

ListИнтерфейс определяет набор классовРазрешить дублирование хранилищаэлементы, а элементы внутри коллекции находятся в том порядке, в котором они были вставленыупорядоченное расположение, в состоянии пройтипоказательэлемент доступа.

QueueИнтерфейс определяет, что коллекция классов队列как структура хранения, поэтому элементы внутри коллекцииупорядоченное расположение, может работать толькоголовной узелэлемент, элемент в середине очереди недоступен.

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

Установить интерфейс

Setинтерфейс наследуетCollectionИнтерфейс, представляющий собой набор, не содержащий повторяющихся элементов, точнее, любые два элемента в наборе не появятсяo1.equals(o2), и Установитьв большинствеможет хранить только одинNULLЭлементы-значения, компоненты коллекции Set можно резюмировать на следующей диаграмме:

В системе сбора сетов нам нужно сосредоточиться на двух моментах:

  • депозитпеременный элемент, необходимо быть очень осторожным, так как изменение состояния элемента в любой момент может привести к тому, что внутри Set появятся два множестваравныйэлементы, то естьo1.equals(o2) = true, так что вообще не меняйте элементы, хранящиеся в Set, иначе он будет уничтоженequals()роль!

  • Самая большая роль Сета заключается в том, чтобы судить о весе, и самая большая роль в проекте такжетяжелый приговор!

Далее, давайте посмотрим на его класс реализации и подклассы:AbstractSetиSortedSet

Абстрактный класс AbstractSet

AbstractSetОпределенный здесь абстрактный класс, реализующий Set, может объединять все конкретные коллекции Set.такое же поведениездесь реализовано,Избегайте подклассов, содержащих много повторяющегося кода.

Все наборы также должны иметь одинаковыеhashCode()иequals()метод, поэтому после использования абстрактного класса для переопределения этого метода подклассам не нужно заботиться об этих двух методах.

public abstract class AbstractSet<E> implements Set<E> {
    // 判断两个 set 是否相等
    public boolean equals(Object o) {
        if (o == this) { // 集合本身
            return true;
        } else if (!(o instanceof Set)) { // 集合不是 set
            return false;
        } else {
            // 比较两个集合的元素是否全部相同
        }
    }
    // 计算所有元素的 hashcode 总和
    public int hashCode() { 
        int h = 0;
        Iterator i = this.iterator();
        while(i.hasNext()) {
            E obj = i.next();
            if (obj != null) {
                h += obj.hashCode();
            }
        }
        return h;
    }
}

Интерфейс SortedSet

SortedSetэто интерфейс, который расширяет Set на основеСортироватьповедение, поэтому все подклассы, которые его реализуют, будут иметь функциональность сортировки.

public interface SortedSet<E> extends Set<E> {
    // 元素的比较器,决定元素的排列顺序
    Comparator<? super E> comparator(); 
    // 获取 [var1, var2] 之间的 set
    SortedSet<E> subSet(E var1, E var2); 
    // 获取以 var1 开头的 Set
    SortedSet<E> headSet(E var1); 
    // 获取以 var1 结尾的 Set
    SortedSet<E> tailSet(E var1); 
    // 获取首个元素
    E first(); 
    // 获取最后一个元素
    E last();
}

HashSet

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

Вот почему в этой статье сначала объясняется Map, а затем Set! Сначала изучите карту, чтобы понять Set

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, Serializable {
    public HashSet() {
        this.map = new HashMap();
    }
    public HashSet(int initialCapacity, float loadFactor) {
        this.map = new HashMap(initialCapacity, loadFactor);
    }
    public HashSet(int initialCapacity) {
        this.map = new HashMap(initialCapacity);
    }
}

мы можем наблюдатьadd()Методы иremove()Метод заключается в том, как привить операции HashSet к HashMap.

private static final Object PRESENT = new Object();

public boolean add(E e) {
    return this.map.put(e, PRESENT) == null;
}
public boolean remove(Object o) {
        return this.map.remove(o) == PRESENT;
}

Мы виделиPRESENTтолько одинстатическая постоянная: Используя PRESENT в качестве значения HashMap, разработчикам, использующим HashSet, нужно толькообрати внимание набыть вставленнымkey,щитхэш-картаvalue

На рисунке выше видно, что каждыйEntryизvalueЭто все НАСТОЯЩИЕ пустые объекты, поэтому нам больше не нужно об этом заботиться.

HashSet реализован на основе HashMap, поэтому многие места можно связать с HashMap:

  • Базовая структура данных: также используется HashSet.数组 + 链表 + 红黑树выполнить
  • Безопасность потоков: поскольку HashMap реализован, а сам HashMap не является потокобезопасным, в HashSet не добавляется дополнительная стратегия синхронизации, поэтому HashSet такжепоток небезопасен
  • Состояние объекта, хранящегося в HashSetлучше не менять, потому что возможно, что после изменения состояния внутри коллекции появятся два элементаo1.equals(o2),сломанныйequals()семантика.

LinkedHashSet

Код LinkedHashSet плохой, если вы мне не верите, я вставлю его для вас

Меньше меньше, все еще не может создавать проблемы,LinkedHashSetнаследоватьHashSet, давайте проследим за конструктором родительского класса HashSet, чтобы увидеть

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    this.map = new LinkedHashMap(initialCapacity, loadFactor);
}

Обнаружено, что реализация карты в родительском классе принимаетLinkedHashMap, обратите внимание, что это неHashMap, а нижний слой LinkedHashMap реализован с помощью HashMap + двусвязный список, поэтому по сути LinkedHashSet по-прежнему реализуется с использованием HashMap.

LinkedHashSet -> LinkedHashMap -> HashMap + двусвязный список

И используется LinkedHashMapHashMapи双向链表Реализованный, этот двусвязный список сохраняет порядок вставки элементов. Таким образом, LinkedHashSet может перебирать элементы в том порядке, в котором они были вставлены, если вы знакомы сLinkedHashMap, то с LinkedHashSet проблем еще меньше.

Есть несколько замечаний по LinkedHashSet:

  • он наследуетHashSet, а HashSet использует HashMap для хранения данных по умолчанию, но LinkedHashSet вызывает конструктор родительского класса для инициализации карты, это LinkedHashMap вместо HashMap, на это следует обратить особое внимание
  • Поскольку LinkedHashMap не является потокобезопасным и в LinkedHashSet не добавляется дополнительная стратегия синхронизации, коллекция LinkedHashSetТакже не потокобезопасныйиз

TreeSet

TreeSet основан на реализации TreeMap, поэтому сохраненные элементыаккуратныйДа, основная структура данных数组 + 红黑树.

Порядок элементов2Это то же самое, что и TreeMap: естественная сортировка и пользовательская сортировка. Ниже показаны часто используемые методы построения. По умолчанию TreeSet использует естественную сортировку. Если вам нужно настроить сортировку, вам нужно передатьComparator.

public TreeSet() { 
    this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) {
    this(new TreeMap<>(comparator));
}

Существует множество сценариев применения TreeSet, например рейтинг боевой мощи игрока в игре.

public class Player implements Comparable<Integer> {
    public String name;
    public int score;
    @Override
    public int compareTo(Student o) {
        return Integer.compareTo(this.score, o.score);
    }
}
public static void main(String[] args) {
    Player s1 = new Player("张三", 100);
    Player s2 = new Player("李四", 90);
    Player s3 = new Player("王五", 80);
    TreeSet<Player> set = new TreeSet();
    set.add(s2); set.add(s1); set.add(s3);
    System.out.println(set);
}
// [Student{name='王五', score=80}, Student{name='李四', score=90}, Student{name='张三', score=100}]

Представлены основные методы реализации и сценарии применения TreeSet, и есть несколько моментов, на которые стоит обратить внимание.

  • Все операции над TreeSet преобразуются в операции над TreeMap, что требуеткрасно-черное деревоРеализация, средняя временная сложность любой операцииO(logN)
  • TreeSet — этопоток небезопасенколлекция
  • TreeSet часто используется дляНе повторяетсяЭлементыпользовательская сортировка, такие как рейтинг силы игрока

Примечание: метод TreeSet для определения повторения элементов состоит в том, чтобы определить, возвращает ли метод compareTo() 0 вместо вызова методов hashcode() и equals().Если он возвращает 0, считается, что один и тот же элемент уже существует в наборе и не будет добавлен в набор.

Интерфейс списка

Интерфейс List и интерфейс Set идут рука об руку и представляют собой тип коллекции, с которым мы соприкасаемся в нашей повседневной разработке. Компоненты всей коллекции List следующие:

ListИнтерфейс напрямую наследует интерфейс Collection, который предназначен для храненияповторениеколлекция элементов, и элементы находятся в порядке вставкиупорядоченное расположение, и можно пройти черезпоказательДоступ к элементу в указанной позиции. Общие реализации: ArrayList, LinkedList, Vector и Stack.

AbstractList и AbstractSequentialList

Абстрактный класс AbstractList реализует интерфейс List и внутренне реализует все функции, которые должны быть у List.Подклассы могут сосредоточиться на реализации своей собственной специфической логики работы.

// 查找元素 o 第一次出现的索引位置
public int indexOf(Object o)
// 查找元素 o 最后一次出现的索引位置
public int lastIndexOf(Object o)
//···

Абстрактный класс AbstractSequentialList наследует AbstractList, который ограничивает порядок доступа к элементам на исходной основе.доступ возможен только последовательно,иПроизвольный доступ не поддерживается, если вам нужно соответствовать характеристикам произвольного доступа, наследуйте AbstractList. Подкласс LinkedList реализован с использованием связанного списка, поэтому он может поддерживать толькопоследовательный доступ, Гу унаследовалAbstractSequentialListвместо абстрактного списка.

Vector

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

В эпоху JDK 1.0 ArrayList еще не родился, и все пользовались коллекциями Vector, но благодарякаждая операциявсе былоsynchronizedукрашение ключевых слов, даже если оно ориентировано на многопотоковое исполнение, по-прежнемуСделайте бессмысленную блокировку и снимите блокировку, вызывая дополнительные потери производительности и выполняя бесполезную работу.

public synchronized boolean add(E e);
public synchronized E get(int index);

В JDK 1.2 появилось семейство Collection, предоставляющее большое количествоВысокая производительность, подходит для разных случаевКоллекция , и Vector тоже один из них, но так как Vector имеет блокировку на каждый метод, его сложно оптимизировать на этой основе из-за необходимости совместимости со многими старыми проектамиVectorТак что история постепенно вычеркнула его.

сейчас напотокобезопасностьВ случае , нет необходимости использовать коллекцию Vector, вместо этогоArrayListКоллекции; в параллельной среде существуетCopyOnWriteArrayList, Vector полностью устарел.

Stack

Stackэто后入先出（LIFO）сборный контейнер типа, как показано на рисунке,大雄Он последним входит в контейнер, а верхний указатель указывает на Nobita, поэтому, когда элемент извлекается, Nobita также выталкивается первым.

Stack наследует класс Vector и обеспечивает операцию проталкивания элементов на вершину стека (push) и извлечения элементов (pop), а также метод просмотра элементов на вершине стека (peek) и т.д. но из-за наследования Вектора это так называемый неправильный босс. Хороших новостей нет, и Стек постепенно устраняется.

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

Deque<Integer> stack = new ArrayDeque<Integer>();

Структура данных ArrayDeque:数组, и предоставитьНижние индексы указателя головы и хвостаРаботает с элементами массива. В этой статье также будет рассказано об этом, пожалуйста, продолжайте читать, не волнуйтесь! :улыбка:

ArrayList

ArrayList смножествоВ качестве складской конструкции онпоток небезопасенсовокупность; имеющаяБыстрый запрос, медленное добавление или удаление в середине массива или в началефункции, поэтому его можно заменить, за исключением небезопасности потокаVector, а потокобезопасный ArrayList может использоватьCopyOnWriteArrayListвместо вектора.

Есть несколько важных замечаний относительно ArrayList:

  • имеютпроизвольный доступОсобенности,Эффективность доступа к элементамвыше, ArrayList находится вЧастая вставка и удалениеЭто более эффективно в сцене с элементами коллекции低.

  • Базовая структура данных: ArrayList использует массив в качестве структуры хранения внизу, сНаходите быстро, добавляйте и удаляйте медленноспециальность

  • Потокобезопасность: ArrayListпоток небезопасенколлекция

  • ArrayList первое расширениеДлина после10,перечислитьadd()При расчете минимальной вместимости контейнера. Вы можете видеть, что если массивelementDataПустой массив установит минимальную емкость на10, а затем длина массива будет увеличена до 10 в первый раз.

// new ArrayList 时的默认空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 默认容量
private static final int DEFAULT_CAPACITY = 10;
// 计算该容器应该满足的最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
  • коллекция изВторое расширениеВ начале длина массива будет расширена до исходной1.5раз, то есть:newLength = oldLength * 1.5

LinkedList

Нижний слой LinkedList принимает双向链表Структура данных хранит элементы, благодаря адресу памяти связанного списка非连续, поэтому он не имеет характеристик произвольного доступа, но поскольку он использует указатели для соединения элементов, для вставки и удаления элементов требуется только操作指针,ненужный移动元素, так жеБыстрое добавление и удаление, медленный запросспециальность. Это также не потокобезопасная коллекция.

Поскольку в качестве структуры данных используется двусвязный список,поток небезопасенколлекция ; каждый сохраненный узел называетсяNode, на рисунке ниже видно, что узел сохраненnextиprevуказатель,itemявляется значением этого узла. Как при вставке, так и при удалении временная сложность остается неизменной.O(1)

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

  • Преимущество: LinkedList не имеет нижнего слоя扩容机制,использовать双向链表Элементы сохраняются, поэтому эффективность вставки и удаления элементов высока, и это подходит для сценариев, в которых элементы часто манипулируются
  • Недостаток: LinkedList не имеет随机访问Характеристика нахождения элемента может быть найдена только изheadилиtailУказатели сравниваются один за другим, поэтомуОчень неэффективно при поиске элементов посередине
  • Поисковая оптимизация: LinkedList находит индексindexэлементоптимизированный,какindex > (size / 2), то изheadНайти в обратном порядке, иначе отtailНачните смотреть вперед, код выглядит следующим образом:
LinkedList.Node<E> node(int index) {
    LinkedList.Node x;
    int i;
    if (index < this.size >> 1) { // 查找的下标处于链表前半部分则从头找
        x = this.first;
        for(i = 0; i < index; ++i) { x = x.next; }
        return x;
    } else { // 查找的下标处于数组的后半部分则从尾开始找
        x = this.last;
        for(i = this.size - 1; i > index; --i) { x = x.prev; }
        return x;
    }
}
  • Двусторонняя очередь: реализована с использованием двустороннего связанного списка и реализованаDequeинтерфейс, чтобы LinkedList можно было использовать какдека. Как видно из рисунка ниже, Node — это элемент коллекции, предоставляющий указатели на предшественников и указатели на преемников, а также ряд операций.头结点и尾结点метод, который имеет характеристики двусторонней очереди.

Самое интересное в коллекции LinkedList — это ее структура связанного списка, но мы также должны отметить, что это коллекция типа deque.

Deque<Object> deque = new LinkedList<>();

Интерфейс очереди

QueueОчереди, в JDK существует два разных типа реализации коллекций:очередь в один конец(AbstractQueue) идека(Деке)

Очередь предоставляет два набора API для добавления и удаления элементов.Две разные стратегии обработки сбоев.

Методы и стратегии отказа Метод вставки метод удаления как найти
Выбросить исключение add() remove() get()
вернуть ошибку по умолчанию offer() poll() peek()

Определяющие факторы выбора метода: при сбое вставки и удаления элементов ожидайте抛出异常или вернуться布尔值

add()иoffer()В сравнении:

В сценарии, где длина очереди определена, после того, как очередь заполнена элементами, при добавлении следующего элемента add() выдастIllegalStateExceptionисключение, покаoffer()вернусьfalse.

Но они оба вставляютсякакой-то незаконный элементВыбрасываются все три одинаковых исключения.

remove()иpoll()В сравнении:

существуеточередь пустапод сценой,remove()броситNoSuchElementExceptionисключение, покаpoll()затем вернутьсяnull.

get()иpeek()В сравнении:

Когда очередь пуста,get()броситNoSuchElementExceptionисключение, покаpeek()затем вернутьсяnull.

Интерфейс дека

DequeРеализация интерфейса очень хорошо понятна: отоднонаправленныйочередь превращается вдвустороннийочередь, дополнительно предусмотрена внутриКак работать с двусторонней очередьюПросто:

Интерфейс Deque дополнительно предоставляетДля головного узла и хвостового узла очередиметод работы иМетоды вставки и удаления также предоставляют два разных набора стратегий отказа.. Кромеadd()иoffer(),remove()иpoll()Кроме того, естьget()иpeek()Появились разные стратегии

Абстрактный класс AbstractQueue

Класс AbstractQueue обеспечивает базовую реализацию каждого API и в основном обеспечивает реализацию базового метода для каждой отдельной стратегии обработки.Определенная здесь функция позволяет子类В соответствии с его方法规范(Или возникает исключение, когда операция не может вернуть значение по умолчанию) для достижения определенной бизнес-логики.

LinkedList

LinkedList был подробно объяснен выше, он реализуетDequeИнтерфейс, который обеспечивает операции для головных и хвостовых узлов, и каждый узел имеетпредшественникипреемникУказатель со всеми характеристиками двусторонней очереди.

ArrayDeque

использоватьмножествореализует deque, которыйНеограниченныйДека, минимальная емкость8(JDK 1.8). В JDK 11 видно, что емкость по умолчанию уже16.

ArrayDequeВ повседневном использовании это не так много, стоит отметить, что это связано сLinkedListСравнение:LinkedListиспользоватьсвязанный списокреализует дек, в то время какArrayDequeиспользоватьмножествоРеализуйте двустороннюю очередь.

В документации автор пишет:ArrayDeque работает лучше, чем Stack, как стек, и лучше, чем LinkedList, как очередь.

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

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

PriorityQueue

PriorityQueue основан наРеализация приоритетной кучиприоритетная очередь, в то время как куча используетсямножествовыполнить:

Описание в документации говорит нам: элементы этого массива передаются вComparatorВыполнить пользовательскую сортировку, если она не переданаComparator, то по самому элементу自然排序, но требует, чтобы элемент реализовывалComparableинтерфейс, поэтому PriorityQueueХранение элементов NULL не допускается.

Сценарий приложения PriorityQueue: сам элемент имеет приоритет и должен следоватьЭлементы приоритетной обработки

  • Например, VIP-игроки и обычные игроки в игре, чем выше VIP-уровень, тем раньше игроки устраиваются для входа на сервер для игры, что снижает потери игроков.
public static void main(String[] args) {
    Student vip1 = new Student("张三", 1);
    Student vip3 = new Student("洪七", 2);
    Student vip4 = new Student("老八", 4);
    Student vip2 = new Student("李四", 1);
    Student normal1 = new Student("王五", 0);
    Student normal2 = new Student("赵六", 0);
    // 根据玩家的 VIP 等级进行降序排序
    PriorityQueue<Student> queue = new PriorityQueue<>((o1, o2) ->  o2.getScore().compareTo(o1.getScore()));
    queue.add(vip1);queue.add(vip4);queue.add(vip3);
    queue.add(normal1);queue.add(normal2);queue.add(vip2);
    while (!queue.isEmpty()) {
        Student s1 = queue.poll();
        System.out.println(s1.getName() + "进入游戏; " + "VIP等级: " + s1.getScore());
    }
}
 public static class Student implements Comparable<Student> {
     private String name;
     private Integer score;
     public Student(String name, Integer score) {
         this.name = name;
         this.score = score;
     }
     @Override
     public int compareTo(Student o) {
         return this.score.compareTo(o.getScore());
     }
 }

Выполнение приведенного выше кода может привести к следующим интересным результатам, как вы можете видеть.氪金Делайте людей счастливыми.

Чем выше уровень VIP (выше приоритет), тем больший приоритет будет отдан входу в игру (приоритетная обработка).Таких приоритетных сценариев много, можете проявить фантазию.

Сводка PriorityQueue:

  • PriorityQueue основан наприоритетная кучареализует приоритетную очередь, в то время как куча используетсямножествоподдерживается

  • PriorityQueue подходит дляЭлементы обрабатываются по приоритетуНапример, когда пользователь запрашивает человеческое обслуживание клиентов и должен стоять в очереди в соответствии с запросом пользователя.VIP-уровеньпровести插队Обработка, чем выше уровень, тем быстрее будет организовано обслуживание клиентов.

Резюме каждой коллекции в конце главы: (в качестве примера возьмем JDK1.8)

тип данных Вставка и удаление временной сложности сложность времени запроса базовая структура данных Это потокобезопасно?
Vector O(N) O(1) множество Да (устарело)
ArrayList O(N) O(1) множество нет
LinkedList O(1) O(N) Двусвязный список нет
HashSet O(1) O(1) Массив + связанный список + красное черное дерево нет
TreeSet O(logN) O(logN) красно-черное дерево нет
LinkedHashSet O(1) O(1)~O(N) Массив + связанный список + красное черное дерево нет
ArrayDeque O(N) O(1) множество нет
PriorityQueue O(logN) O(logN) куча (реализация массива) нет
HashMap O(1) ~ O(N) O(1) ~ O(N) Массив + связанный список + красное черное дерево нет
TreeMap O(logN) O(logN) Массив + красно-черное дерево нет
HashTable O(1) / O(N) O(1) / O(N) массив + связанный список Да (устарело)

Вывод в конце статьи

В этой статье есть немного о каждой коллекции点到即止Цель этой статьи — получить относительно полное представление о всей структуре коллекций, проанализировать соответствующие характеристики наиболее часто используемых коллекций и сценарии применения некоторых специальных коллекций, таких какTreeSet,TreeMapЭта настраиваемая сортируемая коллекция.

  • CollectionИнтерфейс предоставляет всю структуру коллекцийсамый универсальныйАбстрактный метод добавления, удаления, изменения и проверки самой коллекции и предоставления подклассам реализации.

  • SetИнтерфейс определяет, что его подклассыНеупорядоченный, без повторяющихся элементовКоллекция его основных реализаций — это HashSet, TreeSet, LinkedHashSet.

    • HashSetНижний слойHashMapпонял, иTreeSetнижнее использованиеTreeMapРеализации большинство операций коллекции Set будут преобразованы в операции Map, а TreeSet сможет выполнять элементы по правилам.Сортировать.

  • ListИнтерфейс определяет, что его подклассыУпорядоченные, сохраняемые повторяющиеся элементыКоллекция, общие реализации: ArrayList, LinkedList, Vector

    • ArrayListиспользоватьмножествореализовано, в то время как LinkedList используетсвязанный списокреализации, поэтому сценарии использования двух из них практически противоположны,Частые запросысценарии используют ArrayList, ачастая вставка и удалениеСценарий лучше всего использовать LinkedList
    • LinkedListиArrayDequeможно использовать длядека,иJosh Bloch and Doug LeaсчитатьArrayDequeимеет отношениеLinkedListлучшая производительность,ArrayDequeиспользоватьмножествореализует двустороннюю очередь,LinkedListиспользоватьсвязанный списокРеализуйте двустороннюю очередь.

  • QueueИнтерфейс определяет основные операции очереди, а коллекция подклассов будет иметь характеристики очереди:первым пришел-первым вышел, основные реализации: LinkedList, ArrayDeque

    • PriorityQueueнижнее использованиедвоичная кучаподдерживает приоритетную очередь, а бинарная куча состоит измножествореализована возможность сортировки по приоритету элементов,Элементы с более высоким приоритетом помещаются в начало очереди и первыми появляются для обработки..

  • MapИнтерфейс определяет этот тип коллекции как<key,value>Он хранится в виде пар ключ-значение, а его основные реализации: HashMap, TreeMap, LinkedHashMap, Hashtable.

    • В нижний слой LinkedHashMap добавляется двусвязный список, настройкаaccessOrderзаtrueи переопределить метод для достиженияLRUтайник
    • Нижний слой TreeMap реализован массивом + красно-черным деревом, элементы в коллекции по умолчанию отсортированы естественным образом, а также могут быть переданы.Comparatorпользовательская сортировка

Это очень трудно увидеть здесь.Спасибо, что прочитали мою статью.Я надеюсь, что она может быть вам полезна.Вы можете обратиться к порядку резюме в конце статьи.Всякий раз, когда я упоминаю сборник, напоминайте о его важных знаниях точки в основном底层数据结构,线程安全性,该集合的一两个特有性质, пока вы можете дать общий ответ, я считаю, что вы можете использовать эти структуры данных позже, практика делает совершенным.

В этой статье анализируются все часто используемые классы коллекций во всей системе коллекций. Глубокого анализа внутренней реализации коллекции нет. Я хочу, чтобы вы поняли роль каждой коллекции с точки зрения макросов, сценариев применения, и простое сравнение, а затем я уделю время анализу исходного кода общих коллекций, с нетерпением жду этого, спасибо за чтение!

Напоследок хочу сказать кое-что: на написание этой статьи у меня ушло полмесяца, и она тоже имеет большое значение, спасибоcxuanБрат помогал мне писать статьи. На самом деле нелегко шаг за шагом отшлифовать хорошую статью. Другим очень трудно понять каждое слово, которое я пишу. Также очень трудно делиться знаниями с вами, и я надеюсь, продолжать совершенствоваться! Не забывайте первоначальное намерение, любите делиться, любите писать.

Категории