Эти вопросы на собеседовании по Java Collections Framework почти обязательны на собеседованиях.

Эта статья представляет собой третью неделю из серии «Сводка наиболее распространенных вопросов на собеседованиях по Java». основное содержание:

Сходства и различия между Arraylist и LinkedList

Разница между ArrayList и Vector

Базовая реализация HashMap

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

Почему длина HashMap равна степени 2?

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

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

Конкретная реализация безопасности потока ConcurrentHashMap/базовая конкретная реализация

Краткое изложение базовой структуры данных структуры сбора

Эта статья будет синхронно обновляться в моем репозитории учебных пособий по Java с открытым исходным кодом.Java-Guide(Копия охватывает основные знания, которые необходимо освоить большинству Java-программистов, и постепенно улучшается шаг за шагом, с нетерпением жду вашего участия), адрес:GitHub.com/snail Climb/…, приветственная звезда, выпуск, пр.

Сходства и различия между Arraylist и LinkedList

1. Гарантируется ли потокобезопасность:И ArrayList, и LinkedList являются асинхронными, то есть безопасность потоков не гарантируется;
2. Базовая структура данных:Нижний слой Arraylist использует массив Object, нижний слой LinkedList использует структуру данных с двойным циклическим связным списком;
3. Влияет ли на вставки и удаления положение элемента:①ArrayList использует хранилище массивов, поэтому на временную сложность вставки и удаления элементов влияет положение элемента.Например: выполнитьadd(E e)метод, ArrayList по умолчанию добавит указанный элемент в конец списка, и временная сложность в этом случае составляет O (1). Но если вы хотите вставлять и удалять элементы в указанной позиции i (add(int index, E element)) временная сложность O (n-i). Потому что, когда выполняется вышеуказанная операция, (n-i) элементов после i-го элемента и i-го элемента в коллекции требуются для выполнения однобитных операций вперед/назад. ②LinkedList хранится в связанном списке, поэтому на временную сложность вставки и удаления элементов не влияет положение элемента, которое приблизительно равно O(1), а массив приблизительно равен O(n).
4. Поддерживать ли быстрый произвольный доступ:LinkedList не поддерживает эффективный произвольный доступ к элементам, а ArrayList реализует интерфейс RandmoAccess, поэтому имеет функцию произвольного доступа. Быстрый произвольный доступ заключается в быстром получении объекта элемента по серийному номеру элемента (соответствующемуget(int index)метод).
5. Использование памяти:Пустая трата пространства ArrayList в основном отражается в том, что определенное пространство емкости зарезервировано в конце списка списка, в то время как стоимость пространства LinkedList отражается в том, что каждый его элемент должен занимать больше места, чем ArrayList (потому что ему нужно хранить прямой преемник и прямой предшественник и данные).

Дополнение: Двусвязный список на основе структуры данных

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

Разница между ArrayList и Vector

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

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

Базовая реализация HashMap

До JDK1.8

До JDK1.8 HashMap использовалсямассив + связанный списоксостоит из("Хэш связанного списка"То есть комбинация массива и связанного списка), массив является основной частью HashMap, а связанный список существует в основном для разрешения хеш-конфликтов (HashMap принимает«Метод застежки-молнии также является методом адресной цепочки»Разрешение конфликтов), если местонахождение массива не содержит связного списка (следующий из текущего входа указывает на ноль), то такие операции, как поиск и добавление, выполняются очень быстро, и нужна только одна адресация; если найденный массив содержит связанный список, для добавления Временная сложность операции по-прежнему O (1), потому что последняя запись будет вставлена в начало связанного списка, и необходимо срочно просто изменить цепочку ссылок.Для операции поиска в это время необходимо пройти по связанному списку, а затем передать ключевой объект.Метод equals сравнивает и ищет один за другим.

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

После JDK1.8

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

Нижний слой TreeMap, TreeSet и HashMap после JDK1.8 использует красно-черные деревья. Красно-черное дерево призвано устранить недостатки бинарного дерева поиска, поскольку в некоторых случаях бинарное дерево поиска вырождается в линейную структуру.

Рекомендуемое чтение:

«Переосмысление HashMap в серии Java 8»:zhuanlan.zhihu.com/p/21673805

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

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

Почему длина HashMap равна степени 2?

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

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

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

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

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

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

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

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

Источник изображения:Блог Woohoo.cn на.com/efficientness/afraid…

HashTable:

ConcurrentHashMap JDK1.7:

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

Конкретная реализация безопасности потока ConcurrentHashMap/базовая конкретная реализация

JDK1.7 (со схемой выше)

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

ConcurrentHashMap состоит из структуры массива Segment и структуры массива HahEntry..

Segment реализует ReentrantLock, поэтому Segment — это реентерабельная блокировка, которая действует как блокировка. HashEntry используется для хранения данных пары ключ-значение.

static class Segment<K,V> extends ReentrantLock implements Serializable {
}

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

JDK1.8 (со схемой выше)

ConcurrentHashMap отменяет блокировку сегмента сегмента и использует CAS и синхронизацию для обеспечения безопасности параллелизма. Структура данных аналогична HashMap1.8, массив + связанный список/красно-черное двоичное дерево.

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

Краткое изложение базовой структуры данных структуры сбора

Collection

1. List

Список массивов:Массив объектов
Вектор:Массив объектов
Связанный список:двусвязный список

2. Set

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

Map

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