предисловие
Структура данных - неизбежная проблема для каждого разработчика, а Java предоставляет очень зрелые реализации для различных структур данных. Эти реализации являются не только сложными моментами на собеседованиях, но и важными инструментами в работе. Вот, автор, после длительного периода анализа, я представлю его как нить и кокон, а я только подброшу сюда несколько кирпичей и нефрита, надеясь получить от вас мнение.Если вы сможете получить что-то, вы будете очень счастливы. Эта статья содержит в общей сложности 3,5 Вт слов, 25 изображений и рассчитана на 2 часа чтения. Вы можете добавить эту статью в закладки, чтобы ее нельзя было найти при использовании. Это может быть самая подробная статья, которую вы можете увидеть.Подборка вопросов для собеседования по Java 2021.
1. Каркас коллекции
Вся структура коллекций Java показана на рисунке выше (Map сюда не включен, а структура Map будет описана после коллекции) Видно, что интерфейсы верхнего уровня всех классов реализации коллекций являются Iterable и Интерфейсы коллекции, а затем коллекция делится на три разных типа: в виде интерфейсов списка, очереди и набора соответственно, а затем соответствующие различные реализации.
1.1 Интерфейс верхнего уровня
//支持lambda函数接口
import java.util.function.Consumer;
public interface Iterable<T> {
//iterator()方法
Iterator<T> iterator();
default void forEach(Consumer<? super T> action) {
Objects.requireNonNull(action);
for (T t : this) {
action.accept(t);
}
}
default Spliterator<T> spliterator() {
return Spliterators.spliteratorUnknownSize(iterator(), 0);
}
}
В интерфейсе Iterable есть только один метод интерфейса iterator().Iterator также является интерфейсом.В основном он имеет следующие два метода: hasNext() и next().
package java.util;
import java.util.function.Predicate;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;
public interface Collection<E> extends Iterable<E> {
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean removeAll(Collection<?> c);
default boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
boolean removed = false;
final Iterator<E> each = iterator();
while (each.hasNext()) {
if (filter.test(each.next())) {
each.remove();
removed = true;
}
}
return removed;
}
boolean retainAll(Collection<?> c);
void clear();
int hashCode();
@Override
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, 0);
}
default Stream<E> stream() {
return StreamSupport.stream(spliterator(), false);
}
default Stream<E> parallelStream() {
return StreamSupport.stream(spliterator(), true);
}
}
Видно, что основными методами интерфейса Collection являются:
2. Список
Список представляет собой серию упорядоченных коллекций. В отличие от интерфейса «Коллекция», «Список» подчеркивает значение упорядочения.
2.1 Интерфейс списка
package java.util;
import java.util.function.UnaryOperator;
public interface List<E> extends Collection<E> {
<T> T[] toArray(T[] a);
boolean addAll(Collection<? extends E> c);
boolean addAll(int index, Collection<? extends E> c);
default void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final ListIterator<E> li = this.listIterator();
while (li.hasNext()) {
li.set(operator.apply(li.next()));
}
}
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
boolean equals(Object o);
E get(int index);
E set(int index, E element);
void add(int index, E element);
int indexOf(Object o);
int lastIndexOf(Object o);
ListIterator<E> listIterator();
List<E> subList(int fromIndex, int toIndex);
@Override
default Spliterator<E> spliterator() {
return Spliterators.spliterator(this, Spliterator.ORDERED);
}
}
Видно, что List на самом деле имеет больше методов добавления add и методов поиска addAll, чем Collection.get,indexOf,setи так далее,И поддержка операции с индексом индекса.Разница между коллекцией и списком?А. Из вышеизложенного видно, что самая большая разница между Collection и List заключается в том, что Collectionбеспорядок, не поддерживает операции индексации, а список упорядочен. Коллекция не имеет понятия порядка. б) Итератором в списке является ListIterator. в) Список, производный от а, можно сортировать, поэтому интерфейс списка поддерживает использование метода сортировки. г. Режимы работы Spliterator двух различны. **Почему родительский интерфейс неоднократно объявляется в интерфейсе подкласса?**Официальное объяснение: Повторное объявление родительского интерфейса в подинтерфейсе делается для удобства просмотра документа. Например, в документе java doc вы также можете увидеть связанный интерфейс, объявленный Collecion в интерфейсе List.
2.2 Список реализует ArrayList
ArrayList является одним из наиболее часто используемых классов реализации интерфейса List и поддерживает некоторые операции со столбцами интерфейса List.
2.2.1 Отношение наследования ArrayList
2.2.2 Состав ArrayList
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}
//真正存放元素的数组
transient Object[] elementData; // non-private to simplify nested class access
private int size;
Обязательно запомните переходный Object[] elementData в ArrayList, который является контейнером, в котором фактически хранятся элементы.Видно, что ArrayList реализован на основе массивов.
2.2.3 Конструктор ArrayList
>public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
- Object[] elementData — это массив, в котором ArrayList фактически хранит данные.
- ArrayList поддерживает построение размера по умолчанию и пустое построение.При пустом построении Object[] elementData, в котором хранятся данные, представляет собой пустой массив {}.
2.2.4 Добавление элементов в ArrayList
>public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
Обратите внимание, что в ArrayList есть свойство modCount, которое представляет количество изменений экземпляра. (Все коллекции имеют такой атрибут, как modCount, который записывает количество модификаций), каждое добавление или добавление будет увеличивать количество модификаций в ArrayList, а описанный выше метод add(E e) предназначен для добавления новых элементов в конец массива. список.
2.2.4 Расширение списка массивов
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//DEFAULT_CAPACITY是10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
Видно, что когда инициализированный список представляет собой пустой ArrayList, он будет напрямую расширен до DEFAULT_CAPACITY, значение которого по умолчанию равно 10. Когда элементы, добавленные в ArrayList, превышают максимальное значение, которое может хранить массив, он будет расширен. Обратите внимание на эту строку кода
int newCapacity = oldCapacity + (oldCapacity >> 1);
Используется операция сдвига вправо, которая является исходной генеральной, поэтому она в 1,5 раза больше.Например, двоичное число 10 — это 1010, а после сдвига вправо оно становится 101, то есть 5.
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
2.2.5 Копия массива
Java не может выделить пространство сама по себе, это реализация лежащих в основе C и C++. Взяв за пример C, мы знаем, что массив в C является указателем на заголовок.Например, мы выделяем память для массивов в языке C. Java заключается в копировании массива с помощью собственного метода arraycopy.
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
p = (int *)malloc(len*sizeof(int));
Какая польза от этого? **Память в Java управляется jvm, а массиву выделяется непрерывная память, и arrayList не обязательно является непрерывной памятью.Конечно, jvm поможет нам в этом, а у jvm будет внутренняя оптимизация, которая будет в последующих примерах.Поясните с вопросом.
2.2.6 Почему? elementData украшен переходным процессом?
-
Эффект перехода заключается в том, что свойство не участвует в сериализации.
-
ArrayList наследует интерфейс Serializable, который отмечает сериализацию.
-
Контроль безопасности чтения и записи осуществляется в процессе сериализации arrayList. Как добиться безопасности сериализации?
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 size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// 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();
}
}
/**
* Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
* deserialize it).
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
Как вы можете видеть в методе сериализации метода writeObject(), сначала используется метод записи по умолчанию, затем записывается размер, и, наконец, элементные данные просматриваются и записываются, поскольку переменная изменяется переходным процессом, все записывается вручную, так что он также будет выписан сериализованным. Разве это не лишнее?
protected transient int modCount = 0;
Конечно нет.Есть ключ modCount,который фиксирует количество модификаций списка.После записи,если обнаружится,что количество модификаций не совпадает с тем,что было до сериализации,выбросится исключение,и сериализация завершится потерпеть поражение. Это гарантирует, что данные не изменятся в процессе сериализации, и обеспечит безопасность сериализации. (Все это реализовано в java-коллекциях)
2.3 LinkedList
Как мы все знаем, LinkedList — это структура связанного списка, так как же LinkedList реализован в Java?
2.3.1 Отношения наследования LinkedList
Видно, что LinkedList является одновременно и реализацией интерфейса List, и реализацией Queue (Deque), поэтому он поддерживает больше функций, чем ArrayList, и его можно использовать как очередь.Конечно, реализация его очереди не подчеркнуто ниже.
2.3.2 Структура LinkedList
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
LinkedList состоит из головного узла и хвостового узла, которые указывают на начало и конец связанного списка соответственно. Исходный код узла в LinkedList выглядит следующим образом: он состоит из элемента текущего значения, указателя на предыдущий узел prev и указателя на следующий узел next. И он содержит только один конструктор, который создается в порядке таких параметров, как (предыдущий, элемент, следующий).
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
Какова структура узла Node в LinkedList? LinkedList состоит из головного узла, хвостового узла и размера, который по умолчанию равен 0. Можно видеть, что это двусвязный список.
<pre style="margin: 0px; padding: 0px; max-width: 100%; background-image: none; background-position: initial; background-size: initial; background-repeat: initial; background-attachment: initial; background-origin: initial; background-clip: initial; box-sizing: border-box !important; overflow-wrap: break-word !important;">transient int size = 0;
transient Node<E> first;
transient Node<E> last;
public LinkedList() {
}
Метод вставки заголовка linkFirst и метод вставки хвоста linkLast связанного списка в структуре данных
/**
* Links e as first element. 头插法
*/
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
/**
* Links e as last element. 尾插法
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
2.3.3 Метод запроса LinkedList
Получить узел по индексу**: метод get для получения индексного узла.
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Как реализован метод node(index)? Определите, ближе ли индекс к голове или к хвосту, и какой сегмент получает значение от какого сегмента.
Node<E> node(int index) {
// assert isElementIndex(index);
//判断index更靠近头部还是尾部
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
Чтобы запросить метод модификации индекса, сначала найдите соответствующий узел и замените старое значение новым значением.
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
Это также является причиной того, что произвольный доступ к ArrayList быстрее, чем к LinkedList**, LinkedList необходимо пройти, чтобы найти позицию для изменения, а ArrayList — это внутренняя операция массива, которая будет быстрее.
2.4.3 Способ модификации LinkedList
Добавьте новый узел, вы можете видеть, что новый узел помещается в хвост методом вставки хвоста.
public boolean add(E e) {
linkLast(e);
return true;
}
2.5 Vector
Как и ArrayList, Vector также является классом реализации интерфейса List. Среди них основными классами реализации интерфейса List являются ArrayLIst, LinkedList, Vector и Stack, из которых последние два используются редко.
2.5.1 Векторная композиция
В основном то же самое, что и ArrayList.
//存放元素的数组
protected Object[] elementData;
//有效元素数量，小于等于数组长度
protected int elementCount;
//容量增加量，和扩容相关
protected int capacityIncrement;
2.5.2 Потокобезопасность Vector
vector является потокобезопасным, синхронизированным модифицированным методом работы.
2.5.3 Расширение вектора
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//扩容大小
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
Глядя на исходный код, мы видим, что когда в построении отсутствует capacityIncrement, массив расширения будет удваиваться за один раз, в противном случае емкостьIncrement будет увеличиваться каждый раз.
2.5.4 Классический пример векторного метода
удалить элемент
public synchronized E remove(int index) {
modCount++;
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);
int numMoved = elementCount - index - 1;
if (numMoved > 0)
//复制数组，假设数组移除了中间某元素，后边有效值前移1位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//引用null ，gc会处理
elementData[--elementCount] = null; // Let gc do its work
return oldValue;
}
Здесь в основном две строки кода, на которые следует обратить внимание, и у автора есть комментарии в коде. После удаления элемента из массива и его перемещения обязательно установите для исходного конца значение null и уменьшите эффективную длину на 1. В общем, векторная реализация относительно проста и груба, и используется редко, просто посмотрите на нее.
2.6 Stack
Stack также является одним из классов реализации интерфейса List.Как и Vector, из-за соображений производительности структура данных стека редко используется в процессе разработки, но стек является очень важной структурой данных в нижней части компьютера. , Изучите стек в Java.
2.6.1 Отношение наследования стека
Stack наследуется от Vector, который также является классом реализации интерфейса List. Как упоминалось ранее, Vector является потокобезопасным, поскольку все его методы синхронизированы, поэтому операции, которые Stack наследует от родительского класса Vector, также являются потокобезопасными.
2.6.2 Использование стека
Поскольку стек является реализацией стека, его основными операциями являются вставка и извлечение, а самая большая особенность стека — LIFO (последним пришел — первым вышел).
Stack<String> strings = new Stack<>();
strings.push("aaa");
strings.push("bbb");
strings.push("ccc");
System.err.println(strings.pop());
Как видно из приведенного выше кода, строка «ccc», которая была помещена в стек последней, также первой выталкивается из стека.
2.6.3 Исходный код стека
/**
* Stack源码（Jdk8）
*/
public
class Stack<E> extends Vector<E> {
public Stack() {
}
//入栈，使用的是Vector的addElement方法。
public E push(E item) {
addElement(item);
return item;
}
//出栈，找到数组最后一个元素，移除并返回。
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
public boolean empty() {
return size() == 0;
}
public synchronized int search(Object o) {
int i = lastIndexOf(o);
if (i >= 0) {
return size() - i;
}
return -1;
}
private static final long serialVersionUID = 1224463164541339165L;
}
Как видно из исходного кода Stack, в качестве метода push используется метод addElement(E e) из Vector, который помещает элемент в конец коллекции, а метод pop использует метод removeElementAt(Index x) из Vector, remove и получить хвостовой элемент коллекции, видно, что работа Stack основана на хвосте линейной таблицы.
3. Очередь
Как описано в структуре данных, очередь — это структура данных «первым пришел — первым обслужен», то есть «первым пришел — первым вышел». Очередь можно рассматривать как контейнер, в который можно класть элементы только из определенного сегмента, а брать элементы можно только с другого конца.Весь механизм показан на рисунке ниже, но следует отметить, что очередь не указать, какой конец вставляется из какого раздела.
3.1 Что такое Дек
Полное английское название Deque — двухсторонняя очередь, которая также широко известна как двусторонняя очередь. То есть для этого контейнера очереди его можно вставить из головы или хвоста, и его можно получить из головы или хвоста Механизм показан на следующем рисунке.
3.1.1 Интерфейс очереди в Java
Здесь следует отметить, что очередь в Java явно вставляется из хвоста и берется из головы, поэтому реализация очереди в Java берется из головы.
package java.util;
public interface Queue<E> extends Collection<E> {
//集合中插入元素
boolean add(E e);
//队列中插入元素
boolean offer(E e);
//移除元素，当集合为空，抛出异常
E remove();
//移除队列头部元素并返回，如果为空，返回null
E poll();
//查询集合第一个元素，如果为空，抛出异常
E element();
//查询队列中第一个元素，如果为空，返回null
E peek();
}
Методы, часто используемые очередью Java, показаны в таблице.Разница между интерфейсом в таблице и методом интерфейса вне таблицы заключается в том, что операция с очередью не вызовет исключения, поскольку очередь пуста, а операция коллекции вызовет исключение, когда очередь пуста.
3.1.2 Интерфейс дека
package java.util;
public interface Deque<E> extends Queue<E> {
//deque的操作方法
void addFirst(E e);
void addLast(E e);
boolean offerFirst(E e);
boolean offerLast(E e);
E removeFirst();
E removeLast();
E pollFirst();
E pollLast();
E getFirst();
E getLast();
E peekFirst();
E peekLast();
boolean removeFirstOccurrence(Object o);
boolean removeLastOccurrence(Object o);
// *** Queue methods ***
boolean add(E e);
boolean offer(E e);
E remove();
E poll();
E element();
E peek();
// 省略一堆stack接口方法和collection接口方法
}
Как и у метода в Queue, в имени метода больше First или Last, а метод в конце First работает с головы, а Last — с хвоста.
3.1.3 Queue, класс реализации Deque
Реализация Queue в Java в основном использует двусторонние очереди.Ведь операция более удобна и бесплатна.Реализация Queue это PriorityQueue, а Deque в основном имеет два класса реализации в java.util, ArrayDeque и LinkedList, один из которых основан на массивах. , один основан на реализации связанного списка. В предыдущей статье о LinkedList также упоминалось, что это двусвязный список, и на его основе реализован интерфейс Deque.
3.2 PriorityQueue
PriorityQueue — это единственная прямая реализация интерфейса Queue в Java, как следует из названия, приоритетной очереди, которая внутри поддерживает сортировку внутренних элементов по определенным правилам.
3.2.1 Отношения наследования PriorityQueue
Давайте сначала посмотрим на отношения наследования и реализации PriorityQueue. Видно, что это класс реализации Queue. Основной метод использования - это базовая операция очереди. Основной принцип Queue упоминался ранее, и его ядро действует принцип FIFO (First In First Out). Реализация PriorityQueue в Java также соответствует очереди, ноНемного отличается, но не по приоритету PriorityQueue. Это очередь, которая поддерживает приоритет. Когда используется ее функция приоритета, это не FIFO.
3.2.2 Использование PriorityQueue
Дело 1:
PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.add(20);queue.add(14);queue.add(21);queue.add(8);queue.add(9);
queue.add(11);queue.add(13);queue.add(10);queue.add(12);queue.add(15);
while (queue.size()>0){
Integer poll = queue.poll();
System.err.print(poll+"->");
}
Что делает приведенный выше код, так это помещает 10 значений int в очередь, а затем использует метод poll() Queue, чтобы вынимать их по очереди.Конечным результатом является то, что каждое вынимаемое значение является наименьшим значением в очереди, указывая на то, что Внутри PriorityQueue действительно существует определенное правило порядка.
Случай 2:
<pre style="margin: 0px; padding: 0px; max-width: 100%; background-image: none; background-position: // 必须实现Comparable方法，想String,数值本身即可比较
private static class Test implements Comparable<Test>{
private int a;
public Test(int a) {
this.a = a;
}
public int getA() {
return a;
}
public void setA(int a) {
this.a = a;
}
@Override
public String toString() {
return "Test{" +
"a=" + a +
'}';
}
@Override
public int compareTo(Test o) {
return 0;
}
}
public static void main(String[] args) {
PriorityQueue<Test> queue = new PriorityQueue<>();
queue.add(new Test(20));queue.add(new Test(14));queue.add(new Test(21));queue.add(new Test(8));queue.add(new Test(9));
queue.add(new Test(11));queue.add(new Test(13));queue.add(new Test(10));queue.add(new Test(12));queue.add(new Test(15));
while (queue.size()>0){
Test poll = queue.poll();
System.err.print(poll+"->");
}
}
Приведенный выше код переписывает метод compareTo так, чтобы он возвращал 0, то есть без сортировки по приоритету. откройте для себя насВозвращенный заказТест{a=20}->Тест{a=15}->Тест{a=12}->Тест{a=10}->Тест{a=13}->Тест{a=11}->Тест{ a=9}->Test{a=8}->Test{a=21}->Test{a=14}, который все же отличается от порядка вставки, поэтому необходимо обратить внимание на следующее при реализация интерфейса Comparable. Некоторые правила имеют приоритет,Исходный код будет проанализирован позже, чтобы понять, почему порядок извлечения не соответствует порядку, в котором он был вставлен.
3.2.3 Состав PriorityQueue
/**
* 默认容量大小，数组大小
*/
private static final int DEFAULT_INITIAL_CAPACITY = 11;
/**
* 存放元素的数组
*/
transient Object[] queue; // non-private to simplify nested class access
/**
* 队列中存放了多少元素
*/
private int size = 0;
/**
* 自定义的比较规则，有该规则时优先使用，否则使用元素实现的Comparable接口方法。
*/
private final Comparator<? super E> comparator;
/**
* 队列修改次数，每次存取都算一次修改
*/
transient int modCount = 0; // non-private to simplify nested class access
Вы можете видеть, что состав PriorityQueue очень прост, в основном запомните одинмассив для хранения элементов, икомпараторВот и все.
3.2.4 Метод работы PriorityQueue
метод предложения
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
size = i + 1;
//i=size，当queue为空的时候
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}
Во-первых, видно, что когда Очередь пуста, элемент, размещенный в первый раз, сразу помещается на первое место массива, затем первые 20, размещенные в приведенном выше случае 2, помещаются на первое место массива. массив. А когда очередь не пуста, снова используется метод siftUp(i, e).Входящие параметры — это количество существующих элементов в очереди и количество новых элементов, которые нужно вставить. ) что-то сделал.
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
Помните, что упомянутая выше композиция PriorityQueue состоит из массива элементов и компаратора. Это означает, что при отсутствии Comparator класс элемента используется для реализации метода compareTo для сравнения. Его смысл заключается в том, чтобы сначала использовать пользовательское правило сравнения Comparator, в противном случае использовать метод интерфейса Comparable, реализованный классом, в котором находится элемент.
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
//为什么-1， 思考数组位置0，1，2。0是1和2的父节点
int parent = (k - 1) >>> 1;
//父节点
Object e = queue[parent];
//当传入的新节点大于父节点则不做处理，否则二者交换
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
Видно, что при вставке нового элемента, когда PriorityQueue не пуста, для нового элемента будет выполняться сортировка кучей (здесь сортировка кучей описываться не будет), так что каждый раз при его поступлении элемент будет кучей sorted, что также гарантирует, что первый элемент в Queue всегда будет самым маленьким (сортировка по правилу по умолчанию).
метод пула
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];
//s = --size,即原来数组的最后一个元素
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);
return result;
}
Здесь видно, что когда значение извлекается и выполняется операция siftDown,Переданные параметры - это индекс 0 и последний элемент в очереди..
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1; // loop while a non-leaf
while (k < half) {
int child = (k << 1) + 1; // assume left child is least
Object c = queue[child];
int right = child + 1;
if (right < size &&
//c和right是parent的两个子节点，找出小的那个成为新的c。
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
if (key.compareTo((E) c) <= 0)
break;
//小的变成了新的父节点
queue[k] = c;
k = child;
}
queue[k] = key;
}
Когда компаратор отсутствует, используется метод siftDown, как указано выше, потому чтоВынуть по индексу 0, находясь в поискеДочерний узел с индексом 0 меньше, чем он, становится новым родительским узлом и рекурсивно входит в цикл.. Разве PriorityQueue не очень простой, и другие детали не будут подробно объясняться, давайте углубимся.
3.3 ArrayDeque
ArrayDeque — двусторонняя очередь, реализованная на основе массивов в Java.Реализации Deque в Java включают LinkedList и ArrayDeque.Названия указывают на их различие, LinkedList реализован на основе двусвязного списка, а ArrayDeque реализован на основе массивов. . . .
3.3.1 Отношения наследования ArrayDeque
Видно, что ArrayDeque является реализацией интерфейса Deque, в отличие от LinkedList, LinkedList является реализацией как интерфейса List, так и интерфейса Deque.
3.3.2 Использование ArrayDeque
кейс
ArrayDeque<String> deque = new ArrayDeque<>();
deque.offer("aaa");
deque.offer("bbb");
deque.offer("ccc");
deque.offer("ddd");
//peek方法只获取不移除
System.err.println(deque.peekFirst());
System.err.println(deque.peekLast());
Случай 2:
ArrayDeque<String> deque = new ArrayDeque<>();
deque.offerFirst("aaa");
deque.offerLast("bbb");
deque.offerFirst("ccc");
deque.offerLast("ddd");
String a;
while((a = deque.pollLast())!=null){
System.err.print(a+"->");
}
Вышеупомянутая программа, наконец, получает, что результаты очереди - ccc, aaa, bbb, ddd, поэтому она используется циклически.pollLast(), результат ddd, bbb, aaa, ccc, логика вставки второго случая, показанного на рисунке, следующая:
3.3.4 Внутренний состав ArrayDeque
//具体存放元素的数组，数组大小一定是2的幂次方
transient Object[] elements; // non-private to
//队列头索引
transient int head;
//队列尾索引
transient int tail;
//默认的最小初始化容量，即传入的容量小于8容量为8，而默认容量是16
private static final int MIN_INITIAL_CAPACITY = 8;
3.3.5 Длина элементов массива
Длина массива элементов здесь всегда равна степени 2. Метод реализации здесь в основном такой же, как и в hashMap, то есть двоичный файл гарантированной длины состоит из 1, а затем прибавляя 1, становится 100 ..., так что это должна быть степень 2.
private static int calculateSize(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
// Find the best power of two to hold elements.
// Tests "<=" because arrays aren't kept full.
if (numElements >= initialCapacity) {
initialCapacity = numElements;
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;
if (initialCapacity < 0) // Too many elements, must back off
initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
}
return initialCapacity;
}
3.3.6 Механизм реализации ArrayDeque
Как показано ниже:
Здесь массив следует рассматривать как связанный встык, изначально индексы начала и конца равны 0. Направление addLast — вправо, а направление addFirst — влево, поэтому середина массива может быть пустой. При встрече указателя головы и указателя хвоста массив обрабатывается. Разверните и отрегулируйте положение элементов. Исходный код:
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
Обратите внимание на строку кода ниже, указывающую, что когда head-1 больше или равен 0, head=head-1, иначе head=elements.length - 1.
head = (head - 1) & (elements.length - 1)
Другой способ записать это так: это направление движения указателя addFirst выше?
head = head-1>=0?head-1:elements.length-1
Это волшебная операция побитовой операции, потому что любое число и единица, превышающая его, все являются двоичными 1, когда выполняется операция &, она равна самой себе, например, 1010&1111 = 1010, что здесь повторяться не будет. Посмотрите еще раз на метод addLast:
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
Также обратите внимание, что есть строка магических кодов.
(tail = (tail + 1) & (elements.length - 1))
Выражение равноtail = tail+1>element-1?0:tail+1, не очень волшебный способ записи, принцип заключается в том, что двоичное число состоит из 1 и результата операции & над числом, большим, чем 0, например10000&1111 = 0. Логика метода опроса и метода добавления противоположна, поэтому я не буду здесь вдаваться в подробности.
4. Set
Если список добавить коллекцию упорядоченности, то набор - это коллекция Add Uniqueness.
4.1 Установить интерфейс
Интерфейс Set и Collection в java имеют точно такое же определение.
package java.util;
public interface Set<E> extends Collection<E> {
// Query Operations
int size();
boolean isEmpty();
Object[] toArray();
<T> T[] toArray(T[] a);
// Modification Operations
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean retainAll(Collection<?> c);
boolean removeAll(Collection<?> c);
void clear();
boolean equals(Object o);
int hashCode();
//此处和Collection接口由区别
Spliterator<E> spliterator() {
return Spliterators.spliterator(this, Spliterator.DISTINCT);
}
}
4.2 HashSet
HashSet в Java, как следует из названия, представляет собой набор реализаций Hash, а в качестве базовой структуры используется HashMap.
4.2.1 Отношения наследования HashSet
4.2.2 Исходный код HashSet
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
static final long serialVersionUID = -5024744406713321676L;
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
public Iterator<E> iterator() {
return map.keySet().iterator();
}
public int size() {
return map.size();
}
public boolean isEmpty() {
return map.isEmpty();
}
public boolean contains(Object o) {
return map.containsKey(o);
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
public void clear() {
map.clear();
}
}
Вы можете видеть, что внутри HashSet на самом деле находится HashMap.
4.2.3 Как HashSet гарантирует неповторение?
Видно, что в методе добавления HashSet вставленное значение будет использоваться как ключ HashMap, поэтому HashMap гарантирует неповторение. Метод put карты добавляет новое несуществующее значение и возвращает значение null, если оно существует, возвращает исходное значение. О том, как реализован HashMap, см. в продолжении!
4.3 LinkedHashSet
LinkedHashSet также используется меньше, он также основан на реализации Set.
4.3.1 Отношения наследования LinkedHashSet
Как и HashSet, это также класс реализации интерфейса Set и подкласс HashSet.
4.3.2 Исходный код LinkedHashSet
package java.util;
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
private static final long serialVersionUID = -2851667679971038690L;
public LinkedHashSet(int initialCapacity, float loadFactor) {
//调用HashSet的构造方法
super(initialCapacity, loadFactor, true);
}
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
public LinkedHashSet() {
super(16, .75f, true);
}
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}
@Override
public Spliterator<E> spliterator() {
return Spliterators.spliterator(this, Spliterator.DISTINCT |
Spliterator.ORDERED);
}
}
Его метод работы точно такой же, как у HashSet, так в чем же между ними разница? 1. Во-первых, LinkedHashSet является подклассом HashSet 2. LinkedHashMap используется для хранения значений в LinkedHashSet, а HashSet использует HashMap. Конструктор родительского класса, вызываемый в LinkedHashSet, может видеть, что столбец на самом деле является LinkedHashMap.
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
Реализация LinkedHashSet очень проста, для более глубокого понимания нужно посмотреть реализацию LinkedHashMap, анализ LinkedHashMap будет представлен отдельно.
5. Карта
Карта представляет собой структуру пары ключ-значение, которую часто называют структурой ключ-значение. Карта состоит из множества таких пар ключ-значение KV. Мы называем структуру KV записью. В Java карта очень полезна. более одной структуры данных. На рисунке выше показана самая основная структура семейства Map (только в java.util).Подборка вопросов для собеседования по Java 2021.
5.1 Интерфейс карты
package java.util;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.io.Serializable;
public interface Map<K,V> {
// Query Operations
int size();
boolean isEmpty();
boolean containsKey(Object key);
boolean containsValue(Object value);
V get(Object key);
// Modification Operations
V put(K key, V value);
V remove(Object key);
// Bulk Operations
void putAll(Map<? extends K, ? extends V> m);
void clear();
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();
interface Entry<K,V> {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
public static <K extends Comparable<? super K>, V> Comparator<Map.Entry<K,V>> comparingByKey() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getKey().compareTo(c2.getKey());
}
public static <K, V extends Comparable<? super V>> Comparator<Map.Entry<K,V>> comparingByValue() {
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> c1.getValue().compareTo(c2.getValue());
}
public static <K, V> Comparator<Map.Entry<K, V>> comparingByKey(Comparator<? super K> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getKey(), c2.getKey());
}
public static <K, V> Comparator<Map.Entry<K, V>> comparingByValue(Comparator<? super V> cmp) {
Objects.requireNonNull(cmp);
return (Comparator<Map.Entry<K, V>> & Serializable)
(c1, c2) -> cmp.compare(c1.getValue(), c2.getValue());
}
}
// Comparison and hashing
boolean equals(Object o);
int hashCode();
default V getOrDefault(Object key, V defaultValue) {
V v;
return (((v = get(key)) != null) || containsKey(key))
? v
: defaultValue;
}
default void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
action.accept(k, v);
}
}
default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
Objects.requireNonNull(function);
for (Map.Entry<K, V> entry : entrySet()) {
K k;
V v;
try {
k = entry.getKey();
v = entry.getValue();
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
// ise thrown from function is not a cme.
v = function.apply(k, v);
try {
entry.setValue(v);
} catch(IllegalStateException ise) {
// this usually means the entry is no longer in the map.
throw new ConcurrentModificationException(ise);
}
}
}
default V putIfAbsent(K key, V value) {
V v = get(key);
if (v == null) {
v = put(key, value);
}
return v;
}
default boolean remove(Object key, Object value) {
Object curValue = get(key);
if (!Objects.equals(curValue, value) ||
(curValue == null && !containsKey(key))) {
return false;
}
remove(key);
return true;
}
default boolean replace(K key, V oldValue, V newValue) {
Object curValue = get(key);
if (!Objects.equals(curValue, oldValue) ||
(curValue == null && !containsKey(key))) {
return false;
}
put(key, newValue);
return true;
}
default V replace(K key, V value) {
V curValue;
if (((curValue = get(key)) != null) || containsKey(key)) {
curValue = put(key, value);
}
return curValue;
}
default V computeIfAbsent(K key,
Function<? super K, ? extends V> mappingFunction) {
Objects.requireNonNull(mappingFunction);
V v;
if ((v = get(key)) == null) {
V newValue;
if ((newValue = mappingFunction.apply(key)) != null) {
put(key, newValue);
return newValue;
}
}
return v;
}
default V computeIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
V oldValue;
if ((oldValue = get(key)) != null) {
V newValue = remappingFunction.apply(key, oldValue);
if (newValue != null) {
put(key, newValue);
return newValue;
} else {
remove(key);
return null;
}
} else {
return null;
}
}
default V compute(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
V oldValue = get(key);
V newValue = remappingFunction.apply(key, oldValue);
if (newValue == null) {
// delete mapping
if (oldValue != null || containsKey(key)) {
// something to remove
remove(key);
return null;
} else {
// nothing to do. Leave things as they were.
return null;
}
} else {
// add or replace old mapping
put(key, newValue);
return newValue;
}
}
default V merge(K key, V value,
BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
Objects.requireNonNull(remappingFunction);
Objects.requireNonNull(value);
V oldValue = get(key);
V newValue = (oldValue == null) ? value :
remappingFunction.apply(oldValue, value);
if(newValue == null) {
remove(key);
} else {
put(key, newValue);
}
return newValue;
}
}
Интерфейс Map сам по себе является интерфейсом верхнего уровня, состоящим из набора собственных методов интерфейса Map и интерфейса Entry.Интерфейс Entry определяет некоторые операции, в основном связанные с самим ключом-значением, а интерфейс Map определяет некоторые свойства и некоторые свойства, связанные для поиска и модификации.метод интерфейса.
5.2 HashMap
HashMap — это наиболее часто используемый KV-контейнер в Java. Он реализован путем хеширования. HashMap хранит пары ключ-значение друг за другом, которые мы называем Entry. HashMap расширяет Entry (называемый Entry. Node), превращая его в связанный список или дерево. структуру так, чтобы она хранилась в контейнере HashMap (массиве).
5.2.1 Отношения наследования HashMap
5.2.2 Данные, хранящиеся в HashMap
В интерфейсе Map есть интерфейс Entry, который реализован в HashMap.Реализация Entry — это тип данных, хранящихся в HashMap. Реализация Entry в HashMap — это Node, Node — это структура односвязного списка, а TreeNode — его подкласс, который является типом красно-черного дерева, схема его структуры наследования выглядит следующим образом:
Какие данные хранятся в HashMap? Контейнер для хранения данных в коде выглядит следующим образом:
transient Node<K,V>[] table;
Он показывает, что контейнер состоит из одного узла за другим, и узел имеет три реализации, поэтому форма узла, хранящаяся в hashMap, может быть либо Node, либо TreeNode.
5.2.3 Состав HashMap
Ознакомившись с вышеуказанными концепциями, давайте взглянем на компоненты HashMap!
//是hashMap的最小容量16，容量就是数组的大小也就是变量，transient Node<K,V>[] table。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大数量，该数组最大值为2^31一次方。
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的加载因子，如果构造的时候不传则为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//一个位置里存放的节点转化成树的阈值，也就是8，比如数组里有一个node，这个
// node链表的长度达到该值才会转化为红黑树。
static final int TREEIFY_THRESHOLD = 8;
//当一个反树化的阈值，当这个node长度减少到该值就会从树转化成链表
static final int UNTREEIFY_THRESHOLD = 6;
//满足节点变成树的另一个条件，就是存放node的数组长度要达到64
static final int MIN_TREEIFY_CAPACITY = 64;
//具体存放数据的数组
transient Node<K,V>[] table;
//entrySet，一个存放k-v缓冲区
transient Set<Map.Entry<K,V>> entrySet;
//size是指hashMap中存放了多少个键值对
transient int size;
//对map的修改次数
transient int modCount;
//加载因子
final float loadFactor;
Здесь можно говорить о двух концепциях: таблица относится к массиву хранения данных, корзина относится к узлу в определенной позиции в таблице, а узел можно понимать как пакет/коробку данных.
5.2.4 Конструкторы в HashMap*
//只有容量，initialCapacity
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0) // 容量不能为负数
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//当容量大于2^31就取最大值1<<31;
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//当前数组table的大小，一定是是2的幂次方
// tableSizeFor保证了数组一定是是2的幂次方，是大于initialCapacity最结进的值。
this.threshold = tableSizeFor(initialCapacity);
}
Метод tableSizeFor() гарантирует, что размер массива должен быть степенью двойки. Как он реализован?
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
Этот метод превращает все цифры после первой 1 в двоичном числе в 1, а затем добавляет 1, так что двоичное число должно быть 100... Эта форма. Реализация здесь также использует аналогичный метод в реализации ArrayDeque, чтобы гарантировать, что длина массива должна быть степенью 2.
5.2.5 метод пут
Метод put, используемый разработчиками:
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
Метод put value, используемый внутри реального HashMap:
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//当hash到的位置，该位置为null的时候，存放一个新node放入
// 这儿p赋值成了table该位置的node值
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//该位置第一个就是查找到的值，将p赋给e
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果是红黑树，调用红黑树的putTreeVal方法
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//是链表，遍历，注意e = p.next这个一直将下一节点赋值给e，直到尾部，注意开头是++binCount
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//当链表长度大于等于7，插入第8位，树化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
5.2.6 Метод поиска
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//先判断表不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
//这一行是找到要查询的Key在table中的位置，table是存放HashMap中每一个Node的数组。
(first = tab[(n - 1) & hash]) != null) {
//Node可能是一个链表或者树，先判断根节点是否是要查询的key,就是根节点，方便后续遍历Node写法并且
//对于只有根节点的Node直接判断
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//有子节点
if ((e = first.next) != null) {
//红黑树查找
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
//链表查找
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
//遍历链表，当链表后续为null则推出循环
while ((e = e.next) != null);
}
}
return null;
}
5.3 HashTable
В отличие от HashMap, HashTable реализован совершенно по-другому. Это видно из отношения наследования классов между ними. Хотя и HashTable, и HashMap реализуют интерфейс Map, HashTable наследует абстрактный класс DIctionary, а HashMap наследует абстрактный класс AbstractMap.
5.3.1 Диаграмма наследования классов HashTable
HashTable
HashMap
5.3.2 Интерфейс словаря
public abstract
class Dictionary<K,V> {
public Dictionary() {
}
public abstract int size();
public abstract boolean isEmpty();
public abstract Enumeration<K> keys();
public abstract Enumeration<V> elements();
public abstract V get(Object key);
public abstract V put(K key, V value);
public abstract V remove(Object key);
}
В классе Dictionary есть такой комментарий, что при нулевом ключе будет выброшено исключение NullPointerException, которое также показывает, что HashTabel не позволяет ключу быть нулевым.
//throws NullPointerException if the {@code key} is {@code null}.</pre>
5.3.3 Состав хеш-таблицы
/**
* The hash table data.
* 真正存放数据的数组
*/
private transient Entry<?,?>[] table;
/**
* The total number of entries in the hash table.
*/
private transient int count;
/**
* The table is rehashed when its size exceeds this threshold. (The
* value of this field is (int)(capacity * loadFactor).)
* 重新hash的阈值
* @serial
*/
private int threshold;
/**
* The load factor for the hashtable.
* @serial
*/
private float loadFactor;
Элементы в HashTable существуют в таблице Entry[], которая представляет собой массив Entry, Entry — это сохраненный узел, а каждая Entry — это связанный список.
5.3.4 Запись в HashTable
final int hash;
final K key;
V value;
Entry<K,V> next;
Достаточно знать, что Entry — это односвязный список, который имеет ту же структуру, что и Node в HashMap, но есть еще TreeNode, подкласс Node, в HashMap.
5.3.5 метод пут
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
//在数组中的位置 0x7fffffff 是31位二进制1
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
//如果遍历链表找到了则替换旧值并返回
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
По сути, сначала хэш для поиска индекса, просмотр списка записей индекса, если значение хэша и ключ совпадают с введенным ключом, замените старое значение, в противном случае используйте метод addEntry для добавления нового значения в список. table, так как добавление новых элементов включает в себя изменение размера элемента, также может потребоваться расширение и т. д., подробности см. в методе addEntry ниже.
private void addEntry(int hash, K key, V value, int index) {
Entry<?,?> tab[] = table;
//如果扩容需要重新计算hash，所以index和table都会被修改
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
//插入新元素
tab[index] = new Entry<>(hash, key, value, e);
count++;
modCount++;
}
tab[index] = new Entry<>(hash, key, value, e);
Эта строка кода является реальным способом вставки новых элементов с использованием метода вставки заголовка, а односвязный список обычно использует метод вставки заголовка (быстрый).
5.3.6 метод получения
@SuppressWarnings("unchecked")
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}
Метод get намного проще: хэширует, находит индекс, проходит по связанному списку, чтобы найти соответствующее значение, и возвращает null, если нет. По сравнению с тем, что вы видели, методы в HashTable изменены с помощью synchronized, поэтому их операции являются потокобезопасными, но это повлияет на эффективность.