Бредовые Java-коллекции

Java
这次一定?
На этот раз точно?

Грубая классификация: Список, Набор, Очередь, Карта

Iterable

Интерфейс Iterable унаследован от интерфейса Collection. Этот интерфейс предназначен для каждого цикла, а метод интерфейса возвращает объект Iterator.

public interface Iterable<T> {

    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);
    }
}

Давайте посмотрим на пример, чтобы понять вышесказанное

LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);

for (Integer integer : linkedList) {
    System.out.println(integer);
}

после декомпиляции

LinkedList<Integer> linkedList = new LinkedList();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
Iterator var4 = linkedList.iterator();

while(var4.hasNext()) {
    Integer integer = (Integer)var4.next();
    System.out.println(integer);
}

Iterator

Такой итератор появляется в интерфейсе Iterable

public interface Iterator<E> {
 
    boolean hasNext();

    E next();

    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

В основном для унификации метода обхода и разделения структуры данных и метода доступа к коллекции.

Давайте взглянем на внутренние классы в наиболее распространенном классе ArrayList.

private class Itr implements Iterator<E> {
    int cursor;       // 下一次要返回的下标
    int lastRet = -1; // 这一次next 要返回的下标
    int expectedModCount = modCount; // 修改次数

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
        checkForComodification();
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

Мы все знаем, что удаление вызовет ConcurrentModificationException, когда в forEach в ArrayList

ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(1);
arrayList.add(1);

for (Integer integer : arrayList) {
    arrayList.remove(integer);
}

Exception in thread "main" java.util.ConcurrentModificationException

И у нас не будет этой проблемы, когда мы используем Iterator для удаления,

public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();

    try {
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

List

ArrayList

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

Vector

  • потокобезопасность
  • Расширение вдвое больше, чем в прошлый раз
  • modCount существует
  • Synchronized добавляется к каждому методу, работающему с массивом.

CopyOnWriteArrayList

  • Копирование при записи, блокировка
  • потребление памяти
  • Производительность в реальном времени не высока
  • ConcurrentModificationException не существует
  • Объем данных не должен быть слишком большим
  • Блокировка с помощью ReentrantLock

Collections.synchronizedList

  • синхронизированный блок
  • Блокировки объекта могут быть переданы как параметры или текущий объект
  • Необходимо передать объект List в
SynchronizedList(List<E> list) {
    super(list);
    this.list = list;
}
SynchronizedList(List<E> list, Object mutex) {
    super(list, mutex);
    this.list = list;
}

LinkedList

  • ArrayList имеет низкую эффективность добавления и удаления и высокую эффективность изменения и проверки, в то время как LinkedList как раз наоборот.
  • реализация связанного списка
  • Когда используется цикл for, порядок или обратный порядок определяется в зависимости от того, близок ли индекс к первой половине или ко второй половине.
  • ModCount будет изменен при добавлении или удалении

Map

Четыре общих класса реализации

  • HashMap
  • HashTable
  • LinkedHashMap
  • TreeMap

HashMap

HashMap реализуется массивом + связанным списком + красно-черным деревом (в JDK1.8 добавлена ​​красно-черная часть дерева), как показано ниже.

transient Node<K,V>[] table;
// 实际存储的 key-value 的数量
transient int size;
// 阈值、当存放在 table 中的 key-value 大于这个值的时候需要进行扩容
int threshold;
// 负载因子 因为 threshold = loadFactor * table.length
final float loadFactor;

Длина таблицы по умолчанию равна 16, а значение loadFactor по умолчанию равно 0,75.

Продолжайте изучать структуру данных Node.

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

Определить положение индекса массива хэш-багет 

方法一：
static final int hash(Object key) {   //jdk1.8 & jdk1.7
     int h;
     // h = key.hashCode() 为第一步 取hashCode值
     // h ^ (h >>> 16)  为第二步 高位参与运算
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
方法二：
static int indexFor(int h, int length) {  //jdk1.7的源码，jdk1.8 直接使用里面的方法体、没有定义这个方法
     return h & (length-1);  //第三步 取模运算
}

JDK 1.8 的
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;
        // 这里
      if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
.....................
....................
}

Алгоритм хеширования здесь состоит из трех шагов:Получить значение hashCode ключа,операции высокого порядка,Модульная операция

Модульная операцияh & (length - 1 ), на самом деле это эквивалентноh%length, потому что длина всегда равна 2 в энной степени. Потому что & более эффективен, чем %

(h = key.hashCode()) ^ (h >>> 16)XOR хэш-кода ключа с его старшими 16 битами

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

Тогда почему XOR? Разве нет & || для бинокулярных операций?

Ответы от Чжиху

"

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

Что касается того, почему здесь используется операция XOR, потому что в бинокулярной операции & || ^ эффект перетасовки XOR является лучшим, результат составляет 50% от двух чисел бинокулярной операции, а производительность перетасовки относительно хорошая.

https://www.zhihu.com/question/20733617/answer/111577937

https://codeday.me/bug/20170909/69679.html

О проблеме циклического связанного списка, вызванной расширением JDK 1.7

Ниже приведен код расширения для JDK 1.7.

 void resize(int newCapacity) {   //传入新的容量
 2     Entry[] oldTable = table;    //引用扩容前的Entry数组
 3     int oldCapacity = oldTable.length;         
 4     if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
 5         threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
 6         return;
 7     }
 8  
 9     Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
10     transfer(newTable);                         //！！将数据转移到新的Entry数组里
11     table = newTable;                           //HashMap的table属性引用新的Entry数组
12     threshold = (int)(newCapacity * loadFactor);//修改阈值
13 }

 void transfer(Entry[] newTable) {
 2     Entry[] src = table;                   //src引用了旧的Entry数组
 3     int newCapacity = newTable.length;
 4     for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
 5         Entry<K,V> e = src[j];             //取得旧Entry数组的每个元素
 6         if (e != null) {
 7             src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）
 8             do {
 9                 Entry<K,V> next = e.next;
10                 int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置
11                 e.next = newTable[i]; //标记[1]
12                 newTable[i] = e;      //将元素放在数组上
13                 e = next;             //访问下一个Entry链上的元素
14             } while (e != null);
15         }
16     }
17 }

Давайте посмотрим на приведенный выше пример в блоге Meituan.

В однопоточной среде расширение завершается нормально, но было ли оно найдено, перевернуто, и ключ7 стоит перед ключом3. это очень важно

Давайте рассмотрим проблему многопоточности, которая приводит к циклическим связным спискам.

На самом деле круговой связанный список возникает из-за того, что связанный список инвертируется во время расширения.

В JDK1.8 проблема кругового связанного списка возникла из-за использования двух переменных для решения инверсии связанного списка.

Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;

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

Но в любом случае, в случае параллелизма, возникнет проблема потери данных, например, приведенный выше пример потеряет ключ5

HashTable

Устаревший класс, многие функции похожи на HashMap, но он потокобезопасен, но только один поток может писать в HashTable в любой момент времени, а параллелизм не так хорош, как у ConcurrentHashMap, потому что ConcurrentHashMap использует блокировку сегмента. Не рекомендуется для использования

LinkedHashMap

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

Переопределить метод newNode HashMap

И перепишите метод afterNodeInsertion, который изначально был пустым методом в HashMap.

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

И метод removeEldestEntry возвращает false в LinkedHashMap, мы можем реализовать очередь LRU, переопределив этот метод

/**
 * The iteration ordering method for this linked hash map: <tt>true</tt>
 * for access-order, <tt>false</tt> for insertion-order.
 *
 * @serial
 */
final boolean accessOrder;

По умолчанию установлено значение false, чтобы управлять порядком при обходе.

TreeMap 

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK;

Нижний слой TreeMap реализован на основе красно-черного дерева.

Set

нечего сказать

Queue

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;
    if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);
    return true;
}

public boolean add(E e) {
    return offer(e);
}
"

Эта статья Meituan и о HashMap настоятельно рекомендуется для справки.

https://tech.meituan.com/2016/06/24/java-hashmap.html

Категории