Почему arrayList.removeAll(set) намного быстрее, чем arrayList.removeAll(list)?

Java

введение

Мы знаем, что для коллекций существует абстрактный метод removeAll(Collection> c)!

Но знаете ли вы, что в случае большого набора данныхArrayList.removeAll(Set)скорость намного выше, чемArrayList.removeAll(List)!

Я просто протестировал его и удалил 300 000 данных из 1 миллиона данных, первое занимает 0,031 секунды, а второе — 1267 секунд!

Это не паникёр, все желающие могут сходить и протестировать.

проводить исследования

анализ структуры класса

Сначала взгляните на приблизительную диаграмму структуры класса:

Как видно из рисунка, связанные классы коллекций на рисунке (HashSet,LinkedList,ArrayList),КромеArrayListпонял это самremoveAll()Кроме метода две другие коллекции удаляются с помощью итератора Iterator родительского класса (или супер-родительского класса).

Может быть, поэтомуArrayListизremoveAll()Метод показывает «разные» причины для разных типов параметров~!

жевать код

Рассмотрим подробнее класс ArrayList.removeAll()реализация метода.

В целях экономии времени на просмотр официалов я не буду выкладывать конкретный код, а выложу псевдокод, который легче читать:

如：list.removeAll(subList);

//1.将list中不删除的元素移到数组前面（我们知道ArrayList的底层是数组实现）
int w=0; //w为不删除和要删除的分界线
for(var value in 该list的底层数组){
    if(!subList.contain(value)){
        该list的底层数组[w]=value;
        w++;
    }
}

//2.将w后面的元素全部置为null
xxx

Среди них мы можем увидеть ключевой шаг, влияющий на курс:subList.contain(value)!

Так что разница в скорости на самом деле заключается в参数集合.contain()разница в методе

HashSet.contains() vs ArrayList.contains()

  1. ArrayList.contains()

Реализация очень проста, то есть вызов indexOf() и обход поиска один за другим. Худшая временная сложностьO(总数据量).

  1. HashSet.contains()

Мы знаем, что нижний уровень HashSet — это HashMap, поэтому фактический вызов — это вызовmap.containKey()метод.

Как мы все знаем, скорость поиска HashMap очень высока!

Поэтому здесь мы также объясняем проблему заголовка. При этом я также знаю, что в случае относительно большого объема данных использоватьarrayList.removeAll(subList)можно изменить на:

  • будетsubListупаковано какHashSet:arrayList.removeAll(new HashSet(subList))
  • будетarrayListизменить наLinkedList:new LinkedList(arrayList).removeAll(subList)

Давайте снова поговорим о HashMap.containKey()

Сказав это, невозможно немного рассказать о картах.

Первая картинка:

Мы знаем, что нижний слой HashMap数组+链表. иcontainsKey()На самом деле дноgetEntry(key), а затем оцените, является ли запись нулевой для достижения цели!

В JDK1.8,getEntry()которыйgetNode(). Кроме того,get(key)Нижний слой метода также(e=getEntry(key))!=null?e.value:null.

Хватит болтать, вернемся к делу.

На графике верхняя строка представляет собой массив, а каждый столбец — связанный список.

Где должен быть размещен каждый элемент, возможно, потребуются следующие шаги:

  1. Определите, в каком индексе массива находится ключ:索引位置 = (数组.size-1) & hash(key.hashcode())
  • В предыдущей версии использовалась описанная выше битовая операция.&заменяется излишком%, эффект тот же, все для предотвращения превышения значения хэш-кода длины массива. Однако эффективность битовой операции определенно выше, чем у остальных.
  • Популярная наука:a & b = c,Такc<=min(a,b), поэтому результирующий индекс всегда меньше, чем数组.size-1, почему он меньше или равенc<=min(a,b)?
  • Например: 4 и 8 = 00000100 и 00001000, та же позиция与运算,与运算Верно и то, и другое! Итак, смотрим на наименьшее число (00000100), любое число, выполненное с ним与运算, первые 5 цифр не могут быть 1, поэтому результат может быть меньше или равен 4~
  • Также обратите внимание, что метод hash() используется выше, чтобы сохранить единообразие хеша всех ключей Зачем вы хотите это сделать?
  • Например, если вы переопределяете метод hashcode, он возвращает 1. Наконец, когда хэш-карта сохраняет такие объекты, все они помещаются в одну и ту же позицию индекса!
  1. Для входа с Entry.next=null он становится Entry.next=new Node()
  • Примечание. Если данные слишком велики, JDK1.8 автоматически переключит связанный список на реализацию красно-черного дерева.

Поэтому простоcontainsKey()Худшая временная сложность:O((总数据量/数组长度)*最长链表长度)

и это数组长度Как долго это? Какова длина связанного списка? Как они соотносятся с объемом данных?

Нам нужно кратко изучить реализацию HashMap:

На рисунке показано,数组长度Как правило, это больше, чем общий объем данных (когда коэффициент загрузки

Итак, какова длина связанного списка?

Представить,数组长度>= общий объем данных, то в лучшем случае (хэш каждого данных равномерно распределен) в связанном списке может быть один элемент, то есть временная сложность может быть O(1)!

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

Категории