Вопросы для собеседования по коллекции Java (сводка наиболее полных вопросов для собеседования)

интервью

Краткое изложение интервью по Java, включая ключевые знания Java и общие платформы с открытым исходным кодом, приветствуется к прочтению. В статье возможны ошибки, т.к. личные знания ограничены, прошу указать! Статья постоянно обновляется...  

ID заглавие адрес
1 Design Patterns Interview Questions (резюме наиболее полных вопросов для интервью) nuggets.capable/post/684490…
2 Вопросы для собеседования по базовым знаниям Java (сводка наиболее полных вопросов для собеседования) nuggets.capable/post/684490…
3 Вопросы для собеседования по коллекции Java (сводка наиболее полных вопросов для собеседования) nuggets.capable/post/684490…
4 Вопросы для интервью JavaIO, BIO, NIO, AIO, Netty (резюме наиболее полных вопросов для интервью) nuggets.capable/post/684490…
5 Вопросы для собеседования по параллельному программированию на Java (сводка наиболее полных вопросов для собеседования) nuggets.capable/post/684490…
6 Вопросы для собеседования об исключении Java (сводка наиболее полных вопросов для собеседования) nuggets.capable/post/684490…
7 Вопросы для интервью с виртуальной машиной Java (JVM) (сводка наиболее полных вопросов для интервью) nuggets.capable/post/684490…
8 Весенние вопросы для интервью (резюме наиболее полных вопросов для интервью) nuggets.capable/post/684490…
9 Вопросы интервью Spring MVC (сводка наиболее полных вопросов интервью) nuggets.capable/post/684490…
10 Вопросы интервью Spring Boot (обобщите наиболее полные вопросы интервью) nuggets.capable/post/684490…
11 Вопросы интервью Spring Cloud (краткое изложение наиболее полных вопросов интервью) nuggets.capable/post/684490…
12 Вопросы интервью Redis (сводка наиболее полных вопросов интервью) nuggets.capable/post/684490…
13 Вопросы для интервью Mybatis (резюме наиболее полных вопросов для интервью) nuggets.capable/post/684490…
14 Вопросы для собеседования по MySQL (сводка наиболее полных вопросов для собеседования) nuggets.capable/post/684490…
15 TCP, UDP, Socket, HTTP вопросы для интервью (сводка наиболее полных вопросов для интервью) nuggets.capable/post/684490…
16 Вопросы для интервью с Nginx (сводка наиболее полных вопросов для интервью) nuggets.capable/post/684490…
17 ElasticSearch Вопросы на собеседовании
18 кафка вопросы интервью
19 Вопросы для интервью RabbitMQ (сводка наиболее полных вопросов для интервью) nuggets.capable/post/684490…
20 Вопросы для интервью Dubbo (краткое изложение наиболее полных вопросов для интервью) nuggets.capable/post/684490…
21 Вопросы интервью ZooKeeper (резюме наиболее полных вопросов интервью) nuggets.capable/post/684490…
22 Вопросы для интервью Netty (краткое изложение наиболее полных вопросов для интервью)
23 Вопросы для интервью с Tomcat (сводка наиболее полных вопросов для интервью) nuggets.capable/post/684490…
24 Вопросы для собеседования по Linux (сводка наиболее полных вопросов для собеседования) nuggets.capable/post/684490…
25 Вопросы для интервью, связанные с Интернетом (краткое изложение наиболее полных вопросов для интервью)
26 Вопросы для интервью по безопасности в Интернете (краткое изложение наиболее полных вопросов для интервью)

Обзор контейнера для сбора

что такое коллекция

  • Коллекция — это контейнер для данных, точнее, контейнер для ссылок на объекты данных.

  • Классы коллекций хранят ссылки на объекты, а не сами объекты

  • Существует три основных типа коллекций: set (набор), list (список) и map (карта).

Особенности коллекции

  • Две основные характеристики коллекции:

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

    • Размер объекта по сравнению с массивом не определен. Потому что коллекции имеют переменную длину. Массивы должны быть заранее измерены

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

  • Массивы имеют фиксированную длину, коллекции имеют переменную длину.

  • Массивы могут хранить примитивные типы данных, а также ссылочные типы данных; коллекции могут хранить только ссылочные типы данных.

  • Элементы, хранящиеся в массиве, должны иметь один и тот же тип данных; объекты, хранящиеся в коллекции, могут иметь разные типы данных.

Преимущества использования фреймворка коллекций

  1. саморазвитие потенциала;
  2. Предоставляет высокопроизводительные структуры данных и алгоритмы, упрощающие кодирование и улучшающие скорость и качество программы;
  3. Коллекция может быть легко расширена или переписана для улучшения повторного использования кода и удобства работы.
  4. Используя классы коллекций, поставляемые с JDK, вы можете сократить расходы на обслуживание кода и изучение новых API.

Какие обычно используются классы коллекций?

  • Интерфейсы Map и Collection являются родительскими интерфейсами всех фреймворков коллекций:
  1. Подинтерфейсы интерфейса коллекции включают в себя: интерфейс установки и интерфейс списка.
  2. Классы реализации интерфейса карты в основном включают: HashMap, TreeMap, Hashtable, ConcurrentHashMap и свойства и т. д.
  3. Классы реализации интерфейса Set в основном включают: HashSet, TreeSet, LinkedHashSet и т. д.
  4. Классы реализации интерфейса List в основном включают в себя: ArrayList, LinkedList, Stack и Vector и т. д.

В чем разница между списком, набором и картой?

在这里插入图片描述

  • Контейнеры Java делятся на две категории: Коллекция и Карта.Подинтерфейсы коллекций Коллекция включают Набор, Список и Очередь. Мы чаще используем интерфейс Set, List, Map, а не подинтерфейс коллекции.

  • Коллекция Collection в основном имеет два интерфейса: List и Set.

    • Список: упорядоченный (элементарный порядок элементов и последовательный порядок) контейнер, элементы могут повторяться, могут вставлять несколько элементов NULL, а элементы имеют индексы. Обычно реализуемые функции включают ArrayList, LinkedList и Vector.
    • Набор: неупорядоченный (порядок хранения и извлечения может быть непоследовательным) контейнер, который не может хранить повторяющиеся элементы, допускается сохранение только одного нулевого элемента, и должна быть гарантирована уникальность элементов. Обычно используемые классы реализации интерфейса Set — это HashSet, LinkedHashSet и TreeSet.

  • Карта — это набор пар ключ-значение, в котором хранятся сопоставления между ключами, значениями и . Ключ неупорядочен и уникален, значение не обязательно упорядочивать, разрешено повторение. Карта не наследуется от интерфейса Collection.При извлечении элементов из коллекции Map, если задан ключевой объект, будет возвращен соответствующий объект-значение.

    • Общие классы реализации Map: HashMap, TreeMap, HashTable, LinkedHashMap, ConcurrentHashMap.

Платформа сбора, лежащая в основе структуры данных

  • Collection

    1. List

      • Arraylist: массив объектов

      • Вектор: массив объектов

      • LinkedList: дважды круговой связанный список

    2. Set

      • HashSet (неупорядоченный, уникальный): на основе HashMap нижний слой использует HashMap для сохранения элементов.
      • LinkedHashSet: LinkedHashSet наследуется от HashSet, а его внутренняя реализация осуществляется через LinkedHashMap. Это немного похоже на LinkedHashMap, о котором мы говорили ранее, который внутренне основан на реализации Hashmap, но все же есть небольшая разница.
      • TreeSet (упорядоченное, уникальное): красно-черное дерево (самобалансирующееся отсортированное двоичное дерево).

  • Map

    • HashMap: до JDK1.8 HashMap состоит из массива и связанного списка. Массив является основным телом HashMap, а связанный список существует в основном для разрешения конфликтов хэшей («метод застежки-молнии» для разрешения конфликтов). После JDK1.8, устранены конфликты хэшей.Когда длина связанного списка превышает пороговое значение (по умолчанию 8), связанный список преобразуется в красно-черное дерево для сокращения времени поиска
    • LinkedHashMap: LinkedHashMap наследуется от HashMap, поэтому его нижний слой по-прежнему основан на хэш-структуре молнии, которая состоит из массивов и связанных списков или красно-черных деревьев. Кроме того, LinkedHashMap добавляет двусвязный список на основе приведенной выше структуры, чтобы указанная выше структура могла поддерживать порядок вставки пар ключ-значение. В то же время, выполняя соответствующие операции над связанным списком, реализуется логика, связанная с последовательностью доступа.
    • HashTable: состоит из массива + связанного списка, массив является основной частью HashMap, а связанный список существует в основном для разрешения конфликтов хэшей.
    • TreeMap: красно-черное дерево (самобалансирующееся отсортированное бинарное дерево)

Какие классы коллекций являются потокобезопасными?

  • Vector: Есть еще один синхронизированный (потокобезопасный), чем Arraylist, потому что он менее эффективен, и его не рекомендуется использовать сейчас.
  • hashTable: он более синхронизирован (потокобезопасен), чем hashMap, и его не рекомендуется использовать.
  • ConcurrentHashMap: это поточно-ориентированная реализация HashMap, поддерживающая высокий параллелизм и высокую пропускную способность в Java5. Он состоит из структуры массива Segment и структуры массива HashEntry. Массив сегментов играет роль блокировки в ConcurrentHashMap, а HashEntry используется для хранения данных пары ключ-значение. ConcurrentHashMap содержит массив сегментов. Структура Segment аналогична структуре HashMap, которая представляет собой массив и структуру связанного списка; Segment содержит массив HashEntry, и каждый HashEntry является элементом структуры связанного списка; каждый сегмент защищает массив HashEntry. При изменении данных массива HashEntry сначала должна быть получена соответствующая блокировка сегмента. (Рекомендуемое использование)
  • ...

Отказоустойчивый механизм для коллекций Java «отказоустойчивый»?

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

  • Например: предположим, что есть два потока (поток 1, поток 2), поток 1 проходит элементы в наборе A через итератор, и в какой-то момент поток 2 изменяет структуру набора A (это модификация структуры, а не простое изменение содержимого элемента коллекции), то в это время программа выдаст исключение ConcurrentModificationException, что приведет к отказоустойчивому механизму.

  • Причина: итератор напрямую обращается к содержимому коллекции при обходе и использует во время обхода переменную modCount. Если содержимое коллекции изменится во время ее обхода, значение modCount изменится. Всякий раз, когда итератор использует hashNext()/next() для перехода к следующему элементу, он проверяет, является ли переменная modCount ожидаемым значением modCount, и если да, возвращает результат обхода; в противном случае генерирует исключение и завершает обход.

  • Решение:

    1. В процессе обхода все места, участвующие в изменении modCount, добавляются синхронно.

    2. Используйте CopyOnWriteArrayList для замены ArrayList

Как гарантировать, что коллекция не может быть изменена?

  • Коллекция только для чтения может быть создана с помощью метода Collections.unmodifiedCollection(Collection c), так что любая операция, изменяющая коллекцию, вызовет исключение Java.lang.UnsupportedOperationException .

  • Пример кода выглядит следующим образом:

    List<String> list = new ArrayList<>();
list. add("x");
Collection<String> clist = Collections. unmodifiableCollection(list);
clist. add("y"); // 运行时此行报错
System. out. println(list. size());

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

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

Что такое итератор?

  • Интерфейс Iterator предоставляет интерфейс для обхода любой коллекции. Мы можем использовать методы итераторов из коллекции для получения экземпляров итераторов. Итераторы заменяют Enumeration в Java Collections Framework, а итераторы позволяют вызывающей стороне удалять элементы во время итерации.
  • Поскольку все коллекции напрямую наследуют итераторы Iterator.

在这里插入图片描述

Как используется итератор? Каковы характеристики?

  • Код для использования Iterator выглядит следующим образом:

    List<String> list = new ArrayList<>();
Iterator<String> it = list. iterator();
while(it. hasNext()){
  String obj = it. next();
  System. out. println(obj);
}

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

Как удалить элементы из коллекции во время обхода?

  • Единственный правильный способ изменить коллекцию во время ее повторения — использовать метод Iterator.remove() следующим образом:

    Iterator<Integer> it = list.iterator();
while(it.hasNext()){
   *// do something*
   it.remove();
}

один из самых распространенныхОшибкакод показывает, как показано ниже:

for(Integer i : list){
   list.remove(i)
}
  • Запуск вышеуказанного кода ошибки сообщитИсключение ConcurrentModificationException. Это связано с тем, что при использовании оператора foreach(for(Integer i : list)) автоматически создается итератор для обхода списка, но в то же время список модифицируется с помощью Iterator.remove(). Java обычно не позволяет одному потоку изменять коллекцию, пока другой поток ее проходит.

В чем разница между Iterator и ListIterator?

  • Итератор может проходить по коллекциям Set и List, а ListIterator может проходить только по спискам.
  • Iterator можно перемещать только в одном направлении, а ListIterator можно перемещать в обоих направлениях (вперед/назад).
  • ListIterator реализует интерфейс Iterator, а затем добавляет некоторые дополнительные функции, такие как добавление элемента, замена элемента, получение позиции индекса предыдущего или следующего элемента.

Каковы различные способы итерации по списку? Как работает каждый метод? Какова наилучшая практика для обхода списка в Java?

  • Методы обхода следующие:

    1. для обхода цикла на основе счетчиков. Поддерживайте счетчик вне коллекции, а затем считывайте элемент в каждой позиции по очереди, останавливаясь при чтении последнего элемента.
    2. Обход итератора, Итератор. Итератор — это объектно-ориентированный шаблон проектирования, цель которого — защитить характеристики различных коллекций данных и единообразно пройти через интерфейс коллекции. Java поддерживает шаблон Iterator в коллекциях.
    3. foreach проходит через. Foreach также реализован в виде итератора, и нет необходимости явно объявлять итератор или счетчик при его использовании. Преимущество в том, что код лаконичен, и ошибиться не так просто; недостаток в том, что можно сделать только простой обход, а сбор данных нельзя манипулировать в процессе обхода, например удалять и заменять.

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

    • Если набор данных реализует этот интерфейс, это означает, что он поддерживает произвольный доступ, а средняя временная сложность чтения элементов по положению составляет O(1), например ArrayList.

    • Если этот интерфейс не реализован, это означает, что произвольный доступ, такой как LinkedList, не поддерживается.

    • Рекомендуемая практика заключается в том, что список, который поддерживает произвольный доступ, может быть пройден циклом for, в противном случае рекомендуется использовать Iterator или foreach для прохождения.

Расскажите о преимуществах и недостатках ArrayList

  • Преимущества ArrayList заключаются в следующем:

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

  • Недостатки ArrayList следующие:

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

  • ArrayList больше подходит для сценариев последовательного добавления и произвольного доступа.

Как реализовать преобразование между массивом и списком?

  • Массив в список: используйте Arrays.asList(массив) для преобразования.
  • Список в массив: используйте метод toArray(), который поставляется со списком.

  • Пример кода:

    // list to array
List<String> list = new ArrayList<String>();
list.add("123");
list.add("456");
list.toArray();

// array to list
String[] array = new String[]{"123","456"};
Arrays.asList(array);

В чем разница между ArrayList и LinkedList?

  • Реализация структуры данных: ArrayList — это реализация структуры данных динамического массива, а LinkedList — это реализация структуры данных двусвязного списка.
  • Эффективность произвольного доступа: ArrayList более эффективен, чем LinkedList при произвольном доступе, потому что LinkedList — это линейный метод хранения данных, поэтому для поиска необходимо перемещать указатель для поиска спереди назад.
  • Эффективность добавления и удаления: LinkedList более эффективен, чем ArrayList, в неначальных и последних операциях добавления и удаления, потому что добавления и удаления ArrayList влияют на индексы других данных в массиве.
  • Занятие памяти: LinkedList занимает больше памяти, чем ArrayList, потому что в дополнение к хранению данных узлы LinkedList также хранят две ссылки, одна указывает на предыдущий элемент, а другая указывает на следующий элемент.
  • Безопасность потоков: ArrayList и LinkedList не синхронизированы, то есть безопасность потоков не гарантируется;

  • В общем, ArrayList более рекомендуется, когда вам нужно часто читать элементы в коллекции, а LinkedList более рекомендуется, когда есть много операций вставки и удаления.

  • Двусвязный список LinkedList также называется двойным связанным списком, который является своего рода связанным списком.Каждый узел данных LinkedList имеет два указателя, которые указывают на прямого преемника и прямого предшественника соответственно. Поэтому, начиная с любого узла в двусвязном списке, легко получить доступ к его узлам-предшественникам и узлам-последователям.

В чем разница между ArrayList и Vector?

  • Оба этих класса реализуют интерфейс List (интерфейс List наследует интерфейс Collection), и оба они являются отсортированными коллекциями.

    • Безопасность потоков: Vector использует Synchronized для достижения синхронизации потоков, которая является потокобезопасной, в то время как ArrayList не является потокобезопасным.
    • Производительность: ArrayList лучше, чем Vector с точки зрения производительности.
    • Расширение: и ArrayList, и Vector будут динамически регулировать емкость в соответствии с фактическими потребностями, но расширение Vector будет каждый раз удваиваться, в то время как ArrayList будет увеличиваться только на 50%.

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

  • Arraylist не синхронизируется, поэтому рекомендуется использовать Arraylist, когда не требуется потокобезопасность.

При вставке данных, что быстрее, ArrayList, LinkedList или Vector? Объясните производительность и характеристики хранилища ArrayList, Vector, LinkedList?

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

  • Методы в Vector украшены синхронизированными, поэтомуVector Это потокобезопасный контейнер, но его производительность хуже, чем у ArrayList..

  • LinkedList использует двусвязный список для хранения.Индексирование данных по серийному номеру требует прямого или обратного обхода, но при вставке данных необходимо записывать только передние и задние элементы текущего элемента, поэтомуLinkedList Более быстрая вставка.

Как использовать ArrayList в многопоточных сценариях?

  • ArrayList не является потокобезопасным.Если вы столкнулись с многопоточным сценарием, вы можете использовать метод synchronizedList Collections, чтобы преобразовать его в потокобезопасный контейнер перед использованием. Например вот так:

    List<String> synchronizedList = Collections.synchronizedList(list);
synchronizedList.add("aaa");
synchronizedList.add("bbb");

for (int i = 0; i < synchronizedList.size(); i++) {
    System.out.println(synchronizedList.get(i));
}

Почему elementData ArrayList украшен переходным процессом?

  • Массивы в ArrayList определяются следующим образом:

    private transient Object[] elementData;

  • Взгляните еще раз на определение ArrayList:

    public class ArrayList<E> extends AbstractList<E>
     implements List<E>, RandomAccess, Cloneable, java.io.Serializable

  • Вы можете видеть, что ArrayList реализует интерфейс Serializable, что означает, что ArrayList поддерживает сериализацию. Роль переходного процесса состоит в том, чтобы сказать, что вы не хотите, чтобы массив elementData был сериализован, и переопределить реализацию writeObject:

    private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
    *// Write out element count, and any hidden stuff*
        int expectedModCount = modCount;
    s.defaultWriteObject();
    *// Write out array length*
        s.writeInt(elementData.length);
    *// Write out all elements in the proper order.*
        for (int i=0; i<size; i++)
            s.writeObject(elementData[i]);
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
}

  • В каждой сериализации сначала вызовите метод defaultWriteObject() для сериализации непереходных элементов в ArrayList, затем просмотрите elementData и сериализуйте только сохраненные элементы, что не только ускоряет сериализацию, но и сокращает время после ее завершения. сериализация размер файла.

Разница между списком и набором

  • List и Set наследуются от интерфейса Collection.

  • Особенности списка: упорядоченный контейнер (порядок, в котором элементы хранятся в коллекции, совпадает с порядком их извлечения), элементы могут повторяться, можно вставлять несколько нулевых элементов, элементы имеют индексы. Обычно используемые классы реализации — ArrayList, LinkedList и Vector.

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

  • Кроме того, List поддерживает циклы for, то есть обход по нижним индексам, и также можно использовать итераторы, но set может использовать только итерацию, потому что это не по порядку, и нижние индексы нельзя использовать для получения нужного значения.

  • Сравнение набора и списка

    • Установить: эффективность извлечения элементов низкая, а эффективность удаления и вставки высока. Вставка и удаление не приводят к изменению положения элемента.
    • Список: Подобно массиву, список может динамически расти, эффективно находить элементы, неэффективно вставлять и удалять элементы, потому что это приведет к изменению положения других элементов.

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

Расскажите о принципе реализации HashSet?

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

Как HashSet проверяет наличие дубликатов? Как HashSet гарантирует, что данные не повторяются?

  • При добавлении () элементов в HashSet основой для оценки существования элемента является не только сравнение хеш-значения, но и сравнение с методом equals.

  • Метод add() в HashSet будет использовать метод put() из HashMap.

  • Ключ HashMap уникален.Из исходного кода видно, что значение, добавляемое HashSet, является ключом HashMap, и если K/V в HashMap такое же, старое V будет перезаписано новым V, и тогда будет возвращен старый V. . Таким образом, он не будет повторяться (HashMap сравнивает, равны ли ключи или нет, сначала сравнивая хэш-код, а затем сравнивая равные).

  • Следующее является частью исходного кода HashSet:

    private static final Object PRESENT = new Object();
private transient HashMap<E,Object> map;

public HashSet() {
    map = new HashMap<>();
}

public boolean add(E e) {
    // 调用HashMap的put方法,PRESENT是一个至始至终都相同的虚值
	return map.put(e, PRESENT)==null;
}

Соответствующие положения hashCode() и equals():

  1. Если два объекта равны, хэш-код также должен быть одинаковым.
    • hashCode — это значение типа int, вычисляемое jdk по адресу, строке или номеру объекта.
  2. Два объекта равны, возвращайте true для обоих методов равенства
  3. Два объекта имеют одинаковое значение хэш-кода, они не обязательно равны
  4. Подводя итог, если метод equals был переопределен, метод hashCode также должен быть переопределен.
  5. Поведение hashCode() по умолчанию заключается в создании уникальных значений для объектов в куче. Без переопределения hashCode() два объекта этого класса в любом случае не будут равны (даже если два объекта указывают на одни и те же данные).

Разница между == и равным

  1. == определяет, указывают ли две переменные или экземпляры на одно и то же пространство памяти. equals определяет, является ли значение пространства памяти, на которое указывают две переменные или экземпляры, одинаковым
  2. == относится к сравнению адресов памяти equals() сравнивает содержимое строк

Разница между HashSet и HashMap

HashMap HashSet
Реализует интерфейс карты Реализовать интерфейс набора
Хранить пары ключ-значение хранить только объекты
Вызовите put(), чтобы добавить элементы на карту. Вызовите метод add(), чтобы добавить элементы в набор.
HashMap использует ключ (Key) для вычисления Hashcode. HashSet использует объект-член для вычисления значения хэш-кода. Хэш-код может быть одинаковым для двух объектов, поэтому для оценки равенства объектов используется метод equals(). Если два объекта различаются, возвращается значение false
HashMap быстрее, чем HashSet, поскольку извлекает объекты с уникальными ключами. HashSet медленнее, чем HashMap

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

Что такое хеш-алгоритм

  • Алгоритм хеширования относится к отображению двоичного файла произвольной длины в меньшее двоичное значение фиксированной длины.Это меньшее двоичное значение называется хеш-значением.

что такое связанный список

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

  • Связанный список грубо делится на односвязный список и двусвязный список.

    1. Односвязный список: каждый узел состоит из двух частей, одна часть хранит данные переменной данных, а другая часть является следующим указателем на следующий узел.

      在这里插入图片描述

    2. Двусвязный список: в дополнение к части, содержащей односвязный список, также добавляется указатель на предыдущий узел pre

      在这里插入图片描述

  • Преимущества связанных списков

    • Быстрая вставка и удаление (поскольку следующий указатель указывает на его следующий узел, удобно добавлять и удалять элементы, изменяя точку указателя)
    • Высокое использование памяти, отсутствие потерь памяти (вы можете использовать небольшие дискретные пространства в памяти (больше, чем размер узла node) и создавать пространство, когда оно необходимо)
    • Размер не фиксирован, и расширение очень гибкое.

  • Недостатки связанных списков

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

Расскажите о принципе реализации HashMap?

  • Обзор HashMap: HashMap — это асинхронная реализация интерфейса Map на основе хеш-таблицы. Эта реализация предоставляет все необязательные операции с картами и допускает нулевые значения и нулевые ключи. Этот класс не гарантирует порядок карты, в частности не гарантирует, что порядок будет постоянным.

  • Структура данных HashMap: в языке программирования Java есть две основные структуры: одна представляет собой массив, а другая представляет собой аналоговый указатель (ссылка). Все структуры данных могут быть построены с использованием этих двух основных структур. HashMap также не является исключением. HashMap на самом деле является структурой данных «хеш связанного списка», то есть комбинацией массива и связанного списка.

  • HashMap реализован на основе алгоритма Hash.

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

    2. При сохранении, если есть ключ с таким же значением хеш-функции, возможны две ситуации.

      (1) Если ключ тот же, перезапишите исходное значение;

      (2) Если ключи разные (конфликты), поместите текущий ключ-значение в связанный список

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

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

  • Следует отметить, что реализация HashMap оптимизирована в Jdk 1.8.Когда данные узла в связанном списке превышают восемь, связанный список будет преобразован в красно-черное дерево для повышения эффективности запросов из исходного O (n) в O(logn)

В чем разница между HashMap в JDK1.7 и JDK1.8? Базовая реализация HashMap

  • В Java есть две относительно простые структуры данных для хранения данных: массивы и связанные списки.Характеристики массивов: легко адресовать, трудно вставлять и удалять, характеристики связанных списков: трудно адресовать, но легко вставлять и удалять;Итак, мы комбинируем массивы и связанные списки, пользуемся их соответствующими преимуществами и используем метод, называемыймолния методспособ разрешения хэш-коллизий.

HashMap до JDK1.8

  • Метод молнии использовался до JDK1.8.молния метод: объединяет связанный список с массивом. То есть создается массив связанных списков, и каждая ячейка в массиве представляет собой связанный список. Если возникает конфликт хэшей, просто добавьте конфликтующее значение в связанный список.

在这里插入图片描述

HashMap после JDK1.8

  • По сравнению с предыдущей версией, в jdk1.8 внесены большие изменения в разрешение коллизий хэшей: когда длина связанного списка превышает пороговое значение (по умолчанию 8), связанный список преобразуется в красно-черное дерево для уменьшения время поиска.

在这里插入图片描述

JDK1.7 VS JDK1.8 Сравнение

  • JDK1.8 в основном решает или оптимизирует следующие проблемы:
    1. Оптимизация расширения размера
    2. Красно-черное дерево введено для предотвращения влияния на эффективность запроса слишком длинного одного связанного списка.Алгоритм красно-черного дерева см.
    3. Решена проблема многопоточного бесконечного цикла, но он по-прежнему не является потокобезопасным и может вызвать проблемы с потерей данных при многопоточности.
разные JDK 1.7 JDK 1.8
структура хранения массив + связанный список Массив + связанный список + красное черное дерево
Метод инициализации Автономная функция:inflateTable() Непосредственно интегрирован в функцию расширенияresize()середина
метод расчета хэш-значения Обработка возмущений = 9 возмущений = 4 битовые операции + 5 операций XOR Обработка возмущений = 2 возмущения = 1 битовая операция + 1 операция XOR
Правила хранения данных При отсутствии конфликта сохраните массив, при конфликте сохраните связанный список Если конфликта нет, сохранить массив; длина конфликтного и связанного списка 8: дерево и сохранить красно-черное дерево
вставить данные Метод вставки заголовка (сначала переместите данные в исходной позиции на последний 1 бит, а затем вставьте данные в эту позицию) Метод вставки хвоста (вставка непосредственно в хвост связанного списка/красно-черного дерева)
Метод расчета места хранения после расширения Все рассчитываются по оригинальному методу (т.е. hashCode -> функция возмущения -> (h&length-1)) Рассчитывается по правилам после расширения (то есть позиция после расширения = исходная позиция или исходная позиция + старая емкость)

Что такое красно-черное дерево

Говоря о красно-черных деревьях, поговорим о том, что такое бинарное дерево

  • Бинарное дерево просто означает, что каждый узел может быть связан с двумя дочерними узлами.

    • 大概就是这样子：
                       a
                    /     \
                  b          c
                / \         /  \
              d    e       f    g
            /  \  / \     / \   / \
           h   i  j  k   l   m n   o

красно-черное дерево

  • Красно-черное дерево — это особый вид бинарного дерева поиска. Каждый узел красно-черного дерева имеет бит памяти для указания цвета узла, который может быть красным (Red) или черным (Black).

  • Каждый узел красно-черного дерева либо черный, либо красный. В любом случае, когда это так, его корневой узел черный. Каждый листовой узел (листовой узел представляет терминал и конечный узел) также черный [Примечание: листовой узел здесь относится к листовому узлу, который является пустым (NIL или NULL)! ].

  • Если узел красный, его потомки должны быть черными.

  • Количество черных узлов, переданных от каждого узла к конечному узлу NIL, одинаково. [Убедитесь, что ни один путь не вдвое длиннее других, поэтому красно-черное дерево относительно близко к сбалансированному бинарному дереву! ]

  • Основная операция красно-черного деревадобавить, удалить. Метод вращения используется после добавления или удаления красно-черного дерева. Зачем? Причина очень проста: после добавления или удаления узлов в красно-черном дереве структура красно-черного дерева изменилась, и три вышеуказанных свойства могут не выполняться, поэтому это уже не красно-черное дерево, а обычное дерево. А через вращение и обесцвечивание дерево можно снова сделать красно-черным. Проще говоря, цель поворота и изменения цвета — сохранить дерево красно-черным.

Конкретный процесс метода put HashMap?

  • Когда ставим, сначала вычисляемkeyизhashзначение, которое здесь называетсяhashметод,hashНа самом деле метод заключается в том, чтобы позволитьkey.hashCode()иkey.hashCode()>>>16Выполняется операция XOR, старшие 16 бит заполняются 0, а число и 0 подвергаются операции XOR без изменений, поэтому приблизительная функция хэш-функции:Старшие 16 бит остаются неизменными, а младшие 16 бит и старшие 16 бит выполняют XOR для уменьшения коллизий.. Согласно комментарию к функции, поскольку размер массива сегментов является степенью двойки, вычислите индексindex = (table.length - 1) & hash, если обработка хэша не выполняется, это эквивалентно только нескольким младшим битам, которые хэш вступает в силу.Чтобы уменьшить коллизии хеширования, разработчик всесторонне рассматривает скорость, функции и качество и использует высокие 16 бит и низкое 16-битное XOR для простой обработки Уменьшите коллизии, а JDK8 использует древовидную структуру сложности O(logn) для повышения производительности при коллизиях.

  • Блок-схема выполнения метода putVal

在这里插入图片描述

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

//实现Map.put和相关方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 步骤①：tab为空则创建 
    // table未初始化或者长度为0，进行扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 步骤②：计算index，并对null做处理  
    // (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中(此时，这个结点是放在数组中)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 桶中已经存在元素
    else {
        Node<K,V> e; K k;
        // 步骤③：节点key存在，直接覆盖value 
        // 比较桶中第一个元素(数组中的结点)的hash值相等，key相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
                // 将第一个元素赋值给e，用e来记录
                e = p;
        // 步骤④：判断该链为红黑树 
        // hash值不相等，即key不相等；为红黑树结点
        // 如果当前元素类型为TreeNode，表示为红黑树，putTreeVal返回待存放的node, e可能为null
        else if (p instanceof TreeNode)
            // 放入树中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 步骤⑤：该链为链表 
        // 为链表结点
        else {
            // 在链表最末插入结点
            for (int binCount = 0; ; ++binCount) {
                // 到达链表的尾部
                
                //判断该链表尾部指针是不是空的
                if ((e = p.next) == null) {
                    // 在尾部插入新结点
                    p.next = newNode(hash, key, value, null);
                    //判断链表的长度是否达到转化红黑树的临界值，临界值为8
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        //链表结构转树形结构
                        treeifyBin(tab, hash);
                    // 跳出循环
                    break;
                }
                // 判断链表中结点的key值与插入的元素的key值是否相等
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    // 相等，跳出循环
                    break;
                // 用于遍历桶中的链表，与前面的e = p.next组合，可以遍历链表
                p = e;
            }
        }
        //判断当前的key已经存在的情况下，再来一个相同的hash值、key值时，返回新来的value这个值
        if (e != null) { 
            // 记录e的value
            V oldValue = e.value;
            // onlyIfAbsent为false或者旧值为null
            if (!onlyIfAbsent || oldValue == null)
                //用新值替换旧值
                e.value = value;
            // 访问后回调
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    // 结构性修改
    ++modCount;
    // 步骤⑥：超过最大容量就扩容 
    // 实际大小大于阈值则扩容
    if (++size > threshold)
        resize();
    // 插入后回调
    afterNodeInsertion(evict);
    return null;
}
  1. Определите, является ли массив пар ключ-значение table[i] пустым или нулевым, в противном случае выполните resize() для расширения;
  2. Вычислите хэш-значение в соответствии с ключом значения ключа, чтобы получить вставленный индекс массива i, если таблица [i] == null, непосредственно создайте новый узел для добавления, перейдите к ⑥, если таблица [i] не пуста, перейдите к ③;
  3. Определите, совпадает ли первый элемент таблицы[i] с ключом, если он напрямую перезаписывает значение, в противном случае перейдите к ④, где то же самое относится к hashCode и равно;
  4. Определить, является ли table[i] treeNode, то есть является ли table[i] красно-черным деревом, если это красно-черное дерево, вставить пару ключ-значение прямо в дерево, иначе обратиться к 5;
  5. Просмотрите таблицу[i], чтобы определить, больше ли длина связанного списка 8. Если она больше 8, преобразуйте связанный список в красно-черное дерево и выполните операцию вставки в красно-черное дерево, в противном случае , выполнить операцию вставки связанного списка, если обнаружено, что ключ уже существует в процессе обхода, он может быть непосредственно перезаписан значением;
  6. После успешной вставки определите, превышает ли фактическое количество пар ключ-значение максимальный порог емкости, и если да, увеличьте емкость.

Как реализована операция расширения HashMap?

  1. В jdk1.8 метод изменения размера вызывает метод изменения размера для расширения, когда пара ключ-значение в хэш-карте превышает пороговое значение или когда она инициализируется;

  2. Каждый раз, когда он расширяется, он расширяется в 2 раза;

  3. После расширения позиция объекта узла находится либо в исходном положении, либо перемещается в положение в два раза превышает исходное смещение.

  • В putVal() мы видим, что в этой функции дважды используется метод resize().Метод resize() указывает, что он будет расширен при первой инициализации или когда фактический размер массива больше чем его размер Критическое значение (12 в первый раз), в это время элементы на ведре будут перераспределяться при расширении.Это тоже оптимизация версии JDK1.8.В 1.7, после расширения, это необходимо перераспределить Рассчитать его хеш-значение и распределить его в соответствии с хэш-значением, но в версии 1.8 он оценивается в соответствии с позицией того же сегмента (e.hash и oldCap) равен 0 после повторного распределения хэша , элемент Позиция либо остается в исходной позиции, либо перемещается в исходную позицию + увеличенный размер массива.

    final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;//oldTab指向hash桶数组
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {//如果oldCap不为空的话，就是hash桶数组不为空
        if (oldCap >= MAXIMUM_CAPACITY) {//如果大于最大容量了，就赋值为整数最大的阀值
            threshold = Integer.MAX_VALUE;
            return oldTab;//返回
        }//如果当前hash桶数组的长度在扩容后仍然小于最大容量 并且oldCap大于默认值16
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold 双倍扩容阀值threshold
    }
    // 旧的容量为0，但threshold大于零，代表有参构造有cap传入，threshold已经被初始化成最小2的n次幂
    // 直接将该值赋给新的容量
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // 无参构造创建的map，给出默认容量和threshold 16, 16*0.75
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 新的threshold = 新的cap * 0.75
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    // 计算出新的数组长度后赋给当前成员变量table
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//新建hash桶数组
    table = newTab;//将新数组的值复制给旧的hash桶数组
    // 如果原先的数组没有初始化，那么resize的初始化工作到此结束，否则进入扩容元素重排逻辑，使其均匀的分散
    if (oldTab != null) {
        // 遍历新数组的所有桶下标
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                // 旧数组的桶下标赋给临时变量e，并且解除旧数组中的引用，否则就数组无法被GC回收
                oldTab[j] = null;
                // 如果e.next==null，代表桶中就一个元素，不存在链表或者红黑树
                if (e.next == null)
                    // 用同样的hash映射算法把该元素加入新的数组
                    newTab[e.hash & (newCap - 1)] = e;
                // 如果e是TreeNode并且e.next!=null，那么处理树中元素的重排
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // e是链表的头并且e.next!=null，那么处理链表中元素重排
                else { // preserve order
                    // loHead,loTail 代表扩容后不用变换下标，见注1
                    Node<K,V> loHead = null, loTail = null;
                    // hiHead,hiTail 代表扩容后变换下标，见注1
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 遍历链表
                    do {             
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                // 初始化head指向链表当前元素e，e不一定是链表的第一个元素，初始化后loHead
                                // 代表下标保持不变的链表的头元素
                                loHead = e;
                            else                                
                                // loTail.next指向当前e
                                loTail.next = e;
                            // loTail指向当前的元素e
                            // 初始化后，loTail和loHead指向相同的内存，所以当loTail.next指向下一个元素时，
                            // 底层数组中的元素的next引用也相应发生变化，造成lowHead.next.next.....
                            // 跟随loTail同步，使得lowHead可以链接到所有属于该链表的元素。
                            loTail = e;                           
                        }
                        else {
                            if (hiTail == null)
                                // 初始化head指向链表当前元素e, 初始化后hiHead代表下标更改的链表头元素
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 遍历结束, 将tail指向null，并把链表头放入新数组的相应下标，形成新的映射。
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

Как HashMap разрешает коллизии хэшей?

  • A: Прежде чем решить эту проблему, нам сначала нужно знатьЧто такое хеш-коллизия, и прежде чем мы поймем хэш-коллизии, нам также нужно знатьчто такое хэшпросто сделай это;

Что такое хэш?

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

Что такое хеш-коллизия?

  • Когда два разных входных значения вычисляют одно и то же значение хеш-функции по одной и той же хеш-функции, мы называем это столкновением (hash Collision)..

Структура данных HashMap

  • В Java есть две относительно простые структуры данных для хранения данных: массивы и связанные списки.
    • Характеристики массивов: легкость адресации, сложность вставки и удаления;
    • Характеристики связанных списков: трудно адресовать, но легко вставлять и удалять;
  • Таким образом, мы объединяем массив и связанный список и пользуемся их соответствующими преимуществами, мы можем использовать два метода: метод цепного адреса и метод открытого адреса могут решить коллизию хэшей:

在这里插入图片描述

  • Метод связанного списка состоит в том, чтобы организовать объекты с одинаковым хеш-значением в связанный список и поместить их в слот, соответствующий хэш-значению;
  • Метод открытого адреса использует алгоритм обнаружения для продолжения поиска следующего доступного слота, когда слот уже занят.
  • Но по сравнению с типом int, возвращаемым hashCode, первоначальный размер емкости нашего HashMapDEFAULT_INITIAL_CAPACITY = 1 << 4(то есть 2 в четвертой степени 16) намного меньше, чем диапазон типа int, поэтому, если мы просто используем hashCode для получения соответствующего ведра, это сильно повысит вероятность коллизии хэшей, а в худшем случае, это также превратит HashMap в односвязный список, поэтому нам также нужно оптимизировать hashCode

функция хеш()

  • Упомянутая выше проблема в основном связана с тем, что если вы используете hashCode для получения остатка, то это эквивалентноВ операции участвуют только младшие биты hashCode., старший бит не играет никакой роли, поэтому наша идея состоит в том, чтобы позволить старшему биту значения hashCode также участвовать в операции, что еще больше снизит вероятность коллизии хэшей и сделает распределение данных более равномерным, мы называем такую ​​операцию каквозмущение,существуетJDK 1.8Функция hash() выглядит следующим образом:

    static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 与自己右移16位进行异或运算（高低位异或）
}

  • это больше, чемJDK 1.7, что является более кратким,По сравнению с 4-битными операциями и 5-ю операциями XOR (9 возмущений) в 1.7, в 1.8 выполняется только 1-битная операция и 1 операция XOR (2 возмущения).;

Суммировать

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

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

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

  • Если класс переопределяет метод equals(), он также должен переопределять метод hashCode().

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

  • Если класс не использует equals(), его не следует использовать в hashCode().

  • Для пользовательских классов Key рекомендуется сделать их неизменяемыми, чтобы значение hashCode() можно было кэшировать для повышения производительности. Неизменяемые классы также гарантируют, что hashCode() и equals() не изменятся в будущем, что решает проблемы, связанные с изменяемостью.

Почему классы-оболочки, такие как String и Integer в HashMap, подходят для K?

  • Ответ. Характеристики классов упаковки, таких как String и Integer, могут обеспечить неизменность и точность вычислений значений Hash, а также могут эффективно снизить вероятность коллизий Hash.
    • Все они финальные типы, то есть неизменяемость, чтобы обеспечить неизменность ключа, и не будет ситуаций, когда значение хэша отличается.
    • Внутренне переписанequals(),hashCode()и другие методы, соответствующие внутренним спецификациям HashMap (не уверен, вы можете перейти к выше, чтобы увидеть процесс putValue), и вычислить неправильное значение Hash непросто;

Что мне делать, если я использую Object в качестве ключа HashMap?

  • Ответ: переписатьhashCode()иequals()метод
    1. переписатьhashCode()Из-за необходимости рассчитать место хранения сохраненных данных, будьте осторожны и не пытайтесь повысить производительность, исключая важные части объекта из расчета хэш-кода, что может быть быстрее, но может привести к большему количеству конфликтов хэшей;
    2. переписатьequals()метод, должны соответствовать характеристикам рефлексивности, симметрии, транзитивности, непротиворечивости, и для любого ненулевого ссылочного значения x функция x.equals(null) должна возвращать false,Цель состоит в том, чтобы обеспечить уникальность ключа в хеш-таблице.;

Почему HashMap напрямую не использует хеш-значение, обработанное hashCode(), в качестве нижнего индекса таблицы?

  • отвечать:hashCode()Метод возвращает целочисленный тип int, его диапазон -(2 ^ 31)~(2 ^ 31 - 1), существует около 4 миллиардов пространств отображения, а диапазон емкости HashMap равен 16 (значение по умолчанию при инициализации) ~ 2 ^ 30. HashMap обычно не может получить максимальное значение, и трудно обеспечить столько места для хранения на устройстве, что приводит кhashCode()Вычисленное хеш-значение может не соответствовать размеру массива и, следовательно, не соответствовать месту хранения;

  • Как это решить?

    1. HashMap реализует собственныйhash()метод, посредством двух нарушений, старший и младший биты собственного хеш-значения выполняют операцию XOR сами по себе, уменьшая вероятность хеш-коллизии и делая распределение данных более равномерным;

    2. При обеспечении того, чтобы длина массива была степенью 2, используйтеhash()Значение после операции и операции (&) (длина массива - 1) сохраняется способом получения индекса массива, что более эффективно, чем операция остатка, а также потому, что только когда длина массива является степенью двойки Когда h&(length-1) эквивалентно h%length, это решает проблему «значение хеша не соответствует диапазону размеров массива»;

Почему длина HashMap является степенью двойки

  • Чтобы сделать доступ к HashMap эффективным и минимизировать коллизии, необходимо распределять данные как можно более равномерно, а каждый связанный список/красно-черное дерево имеет примерно одинаковую длину. Эта реализация представляет собой алгоритм того, в каком связанном списке/красно-черном дереве хранить данные.

  • Как должен быть построен этот алгоритм?

    • Мы можем сначала подумать об использовании %, чтобы получить остаток для достижения. Однако здесь наступает момент: «Если делитель является степенью числа 2 в операции остатка (%), это эквивалентно операции И (&) вычитания единицы из его делителя (то есть хэш%длина==хэш& (длина-1) Предпосылка состоит в том, что длина представляет собой n-ю степень числа 2;)." А использование двоичной битовой операции & по сравнению с % может повысить эффективность операции, что объясняет, почему длина HashMap является мощностью 2.

  • Так почему же два возмущения?

    • Ответ: Это сделано для того, чтобы увеличить случайность младших битов хеш-значения, сделав распределение более однородным, тем самым улучшив случайность и однородность соответствующих позиций индекса хранения массива и, наконец, уменьшив конфликты хэшей, достаточно вдвое, а высокий и достигнуты младшие биты Цель участия в операции одновременно;

В чем разница между HashMap и HashTable?

  1. потокобезопасность: HashMap не является потокобезопасным, HashTable является потокобезопасным; внутренние методы HashTable в основномsynchronizedретушь. (используйте ConcurrentHashMap, если вам нужна безопасность потоков);
  2. эффективный: из-за проблем с безопасностью потоков HashMap немного эффективнее, чем HashTable. Кроме того, HashTable практически исключен, не используйте его в коде (если хотите обеспечить потокобезопасность, используйте ConcurrentHashMap);
  3. Поддержка ключа Null и значения Null: В HashMap в качестве ключа можно использовать null, такой ключ только один, и может быть один или несколько ключей, соответствующих null. Но пока значение ключа, помещенное в HashTable, имеет нулевое значение, NullPointerException генерируется напрямую.
  4. Разница между начальным размером емкости и размером каждой емкости расширения:
    1. Если начальное значение емкости не указано при ее создании, начальный размер хеш-таблицы по умолчанию равен 11. После каждого расширения емкость становится исходной 2n+1. Размер инициализации HashMap по умолчанию равен 16. После каждого расширения вместимость удваивается.
    2. Если начальное значение емкости задано при ее создании, то Hashtable будет напрямую использовать заданный вами размер, а HashMap расширит его до степени двойки. Другими словами, HashMap всегда использует в качестве размера хеш-таблицы степень 2. Позже мы объясним, почему это степень 2.
  5. базовая структура данных: HashMap после JDK1.8 имеет большое изменение в разрешении хеш-конфликтов.Когда длина связанного списка превышает пороговое значение (по умолчанию 8), связанный список преобразуется в красно-черное дерево для сокращения времени поиска . Hashtable не имеет такого механизма.
  6. Рекомендуемое использование: Как вы можете видеть в комментарии к классу Hashtable, Hashtable является зарезервированным классом и не рекомендуется. Вместо этого рекомендуется использовать HashMap в однопоточной среде. Если требуется многопоточное использование, используйте вместо этого ConcurrentHashMap.

Что такое TreeMap Введение

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

Как решить использовать HashMap или TreeMap?

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

Разница между HashMap и ConcurrentHashMap

  1. ConcurrentHashMap делит весь массив бакетов на сегменты, а затем защищает каждый сегмент с помощью блокировок.По сравнению с синхронизированными блокировками HashTable гранулярность лучше, а производительность параллелизма лучше, а HashMap не имеет механизма блокировок и не является потокобезопасным. (После JDK1.8 ConcurrentHashMap обеспечивает новый способ реализации с использованием алгоритма CAS.)
  2. Пары ключ-значение HashMap допускают значение null, а ConCurrentHashMap — нет.

Разница между ConcurrentHashMap и Hashtable?

  • Разница между ConcurrentHashMap и Hashtable в основном отражается в способе достижения безопасности потоков.

    • базовая структура данных: нижний слой ConcurrentHashMap JDK1.7 используетсегментированный массив + связанный списокРеализация, структура данных, используемая JDK1.8, такая же, как и в HashMap1.8, массив + связанный список/красно-черное двоичное дерево. Базовая структура данных Hashtable и HashMap до JDK1.8 аналогична.массив + связанный списокВ форме массив является основной частью HashMap, а связанный список существует в основном для разрешения конфликтов хэшей;
    • Способы достижения потокобезопасности:
      1. Во времена JDK1.7 ConcurrentHashMap (блокировка сегмента)Весь массив бакетов разделен на сегменты. Каждая блокировка блокирует только часть данных в контейнере. Многопоточный доступ к данным в разных сегментах данных в контейнере предотвратит конкуренцию блокировок и повысит скорость параллельного доступа. (По умолчанию выделяется 16 сегментов, что в 16 раз эффективнее, чем Hashtable.)Ко времени JDK1.8 от концепции сегмента отказались, но она напрямую реализована со структурой данных массива узлов + связанный список + красно-черное дерево, а управление параллелизмом осуществляется с использованием синхронизированного и CAS. (После JDK1.6 было сделано много оптимизаций для синхронизированных блокировок)Все выглядит как оптимизированный и потокобезопасный HashMap.Хотя структуру данных Segment все еще можно увидеть в JDK1.8, атрибуты были упрощены только для совместимости со старыми версиями;
      2. ②Hashtable (тот же замок): Использование synchronized для обеспечения безопасности потоков очень неэффективно. Когда один поток обращается к синхронизированному методу, другие потоки также получают доступ к синхронизированному методу и могут войти в состояние блокировки или опроса, например, добавление элементов с помощью put, другой поток не может использовать put для добавления элементов или использовать get, конкуренция станет больше и больше яростнее Чем ниже эффективность.

  • Сравнительная таблица двух:

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

在这里插入图片描述

2. ConcurrentHashMap из JDK1.7:

在这里插入图片描述

3. ConcurrentHashMap из JDK1.8 (TreeBin: красно-черный узел бинарного дерева Node: узел связанного списка):

在这里插入图片描述

  • Ответ: ConcurrentHashMap сочетает в себе преимущества HashMap и HashTable. HashMap не учитывает синхронизацию, HashTable учитывает синхронизацию и использует ключевое слово synchronized, поэтому HashTable блокирует всю структуру при каждой синхронизации. Способ блокировки ConcurrentHashMap несколько детализирован.

Знаете ли вы основную конкретную реализацию ConcurrentHashMap? Каков принцип реализации?

JDK1.7

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

  • В JDK1.7 ConcurrentHashMap реализован по схеме Segment + HashEntry, структура следующая:

  • ConcurrentHashMap содержит массив сегментов. Структура Segment аналогична HashMap. Это массив и структура связанного списка. Сегмент содержит массив HashEntry. Каждый HashEntry является элементом структуры связанного списка. Каждый сегмент защищает элемент в массиве HashEntry. При изменении вы должен сначала получить блокировку соответствующего сегмента.

在这里插入图片描述

  1. Этот класс содержит два статических внутренних класса HashEntry и Segment: первый используется для инкапсуляции пары ключ-значение таблицы сопоставления, а второй используется в качестве блокировки;
  2. Сегмент — это реентерабельная блокировка.Каждый сегмент защищает элемент в массиве HashEntry.При изменении данных в массиве HashEntry сначала необходимо получить соответствующую блокировку сегмента.

JDK1.8

  • существуетВ JDK1.8 от раздутого дизайна сегмента отказались и заменили на Node + CAS + Synchronized, чтобы обеспечить безопасность параллелизма для реализации., synchronized блокирует только первый узел текущего связанного списка или красно-черного бинарного дерева, так что пока хэш не конфликтует, параллелизма не будет, а эффективность улучшится в N раз.

  • Структура выглядит следующим образом:

在这里插入图片描述

  • Дополнительный исходный код, вы можете посмотреть, если вам это нужно

  • Процесс вставки элементов (рекомендуется посмотреть исходный код):

  • Если узел в соответствующей позиции не был инициализирован, вызовите CAS для вставки соответствующих данных;

    else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
    if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
        break;                   // no lock when adding to empty bin
}

  • Если узел в соответствующей позиции не пуст и узел в данный момент не находится в состоянии перемещения, добавьте к узлу синхронизированную блокировку, если хэш узла не меньше 0, пройдите по связанному списку, чтобы обновить узел или вставить новый узел;

    if (fh >= 0) {
    binCount = 1;
    for (Node<K,V> e = f;; ++binCount) {
        K ek;
        if (e.hash == hash &&
            ((ek = e.key) == key ||
             (ek != null && key.equals(ek)))) {
            oldVal = e.val;
            if (!onlyIfAbsent)
                e.val = value;
            break;
        }
        Node<K,V> pred = e;
        if ((e = e.next) == null) {
            pred.next = new Node<K,V>(hash, key, value, null);
            break;
        }
    }
}
  1. Если узел является узлом типа TreeBin, то это означает, что это красно-черная древовидная структура, то через метод putTreeVal узел вставляется в красно-черное дерево, если binCount не равен 0, то это означает, что операция put имеет влияние на данные, если текущее количество связанных списков достигает 8, то преобразовать его в красно-черное дерево через метод treeifyBin.Если oldVal не пусто, это означает, что это операция обновления, которая не влияет на количество элементов, и старое значение возвращается напрямую;
  2. Если вставлен новый узел, выполните метод addCount(), чтобы попытаться обновить значение счетчика элементов baseCount;

Вспомогательные инструменты

В чем разница между Array и ArrayList?

  • Array может хранить основные типы данных и объекты, ArrayList может хранить только объекты.
  • Массив имеет фиксированный размер, а размер ArrayList автоматически расширяется.
  • В Array не так много встроенных методов, как в ArrayList, например, addAll, removeAll, iteration и другие методы доступны только в ArrayList.

对于基本类型数据，集合使用自动装箱来减少编码工作量。但是，当处理固定大小的基本数据类型的时候，这种方式相对比较慢。

Как реализовать преобразование между массивом и списком?

  • Массив в список: Arrays.asList(массив);
  • Список в массив: метод toArray() для List.

В чем разница между сопоставимым и компаратором?

  • Сопоставимый интерфейс на самом деле из пакета java.lang, который имеет метод compareTo(Object obj) для сортировки.
  • Интерфейс компаратора на самом деле из пакета java.util, в котором есть метод сравнения (Object obj1, Object obj2) для сортировки.
  • Как правило, когда нам нужно использовать пользовательскую сортировку для коллекции, нам нужно переписать метод compareTo или метод сравнения.Когда нам нужно реализовать два метода сортировки для определенной коллекции, например, название песни и имя исполнителя в песне объект используйте один Если есть метод сортировки, мы можем переписать метод compareTo и использовать самодельный метод Comparator или использовать два Comparator для сортировки названий песен и сортировки имен исполнителей.Второе означает, что мы можем использовать только двухпараметрический версия Collections.sort() .

В чем разница между Collectionи Collections?

  • java.util.Collection — это интерфейс коллекции (интерфейс верхнего уровня для классов коллекций). Он предоставляет общие методы интерфейса для основных операций с объектами коллекции. Интерфейс Collection имеет множество конкретных реализаций в библиотеке классов Java. Значение интерфейса Collection состоит в том, чтобы обеспечить максимально унифицированный метод работы для различных конкретных коллекций, а его интерфейсы прямого наследования включают List и Set.
  • Коллекции — это класс инструментов/вспомогательный класс класса коллекции, который предоставляет ряд статических методов для сортировки, поиска и обеспечения безопасности потоков элементов в коллекции.

Как TreeMap и TreeSet сравнивают элементы при сортировке? Как метод sort() в служебном классе Collections сравнивает элементы?

  • TreeSet требует, чтобы класс, которому принадлежит хранимый объект, реализовывал интерфейс Comparable, который предоставляет метод compareTo() для сравнения элементов.Когда элемент вставляется, метод будет вызываться обратно для сравнения размера элемента. TreeMap требует, чтобы ключи сохраненной карты пар ключ-значение реализовывали интерфейс Comparable для сортировки элементов в соответствии с ключами.

  • Метод sort служебного класса Collections имеет две перегруженные формы:

  • Первый требует, чтобы объекты, хранящиеся во входящем контейнере для сортировки, реализовывали интерфейс Comparable для сравнения элементов;

?

  • Сопоставимый интерфейс на самом деле из пакета java.lang, который имеет метод compareTo(Object obj) для сортировки.
  • Интерфейс компаратора на самом деле из пакета java.util, в котором есть метод сравнения (Object obj1, Object obj2) для сортировки.
  • Как правило, когда нам нужно использовать пользовательскую сортировку для коллекции, нам нужно переписать метод compareTo или метод сравнения.Когда нам нужно реализовать два метода сортировки для определенной коллекции, например, название песни и имя исполнителя в песне объект используйте один Если есть метод сортировки, мы можем переписать метод compareTo и использовать самодельный метод Comparator или использовать два Comparator для сортировки названий песен и сортировки имен исполнителей.Второе означает, что мы можем использовать только двухпараметрический версия Collections.sort() .

В чем разница между Collectionи Collections?

  • java.util.Collection — это интерфейс коллекции (интерфейс верхнего уровня для классов коллекций). Он предоставляет общие методы интерфейса для основных операций с объектами коллекции. Интерфейс Collection имеет множество конкретных реализаций в библиотеке классов Java. Значение интерфейса Collection состоит в том, чтобы обеспечить максимально унифицированный метод работы для различных конкретных коллекций, а его интерфейсы прямого наследования включают List и Set.
  • Коллекции — это класс инструментов/вспомогательный класс класса коллекции, который предоставляет ряд статических методов для сортировки, поиска и обеспечения безопасности потоков элементов в коллекции.

Как TreeMap и TreeSet сравнивают элементы при сортировке? Как метод sort() в служебном классе Collections сравнивает элементы?

  • TreeSet требует, чтобы класс, которому принадлежит хранимый объект, реализовывал интерфейс Comparable, который предоставляет метод compareTo() для сравнения элементов.Когда элемент вставляется, метод будет вызываться обратно для сравнения размера элемента. TreeMap требует, чтобы ключи сохраненной карты пар ключ-значение реализовывали интерфейс Comparable для сортировки элементов в соответствии с ключами.

  • Метод sort служебного класса Collections имеет две перегруженные формы:

  • Первый требует, чтобы объекты, хранящиеся во входящем контейнере для сортировки, реализовывали интерфейс Comparable для сравнения элементов;

  • Второе не обязательно, и элементы в контейнере должны быть сопоставимы, но второй параметр необходимо передать. Параметр является подтипом интерфейса Comparator (метод сравнения необходимо переписать для реализации сравнения элементов ), что эквивалентно временному определению.Сопоставление на самом деле является алгоритмом сравнения размера элементов, вводимых через интерфейс, а также является применением шаблона обратного вызова (поддержка функционального программирования в Java).

Категории