Какой алгоритм используется для преобразования ArrayList <T>в LinkedHashSet <T>в JRE

Question

Я хотел получить list уникальных элементов от list с дублирующимися элементами, и порядок элементов, присутствующих в списке, должен быть сохранен.

Чтобы достичь этого, я мог бы написатьалгоритм типа:

private ArrayList<T> getUnique(ArrayList<T> list)
{
    // maintain a hashmap of numbers and a uniqueList to be returned(ArrayList<T>)
    // Add element in result list and the hashmap if the element isn't already present in the hashmap, else just add in the hashmap

    HashMap<T, Boolean> map = new HashMap<>();
    ArrayList<T> uniqueList = new ArrayList<>();

    for (T t: list)
    {
        if (map.get(t) == null)
        {
            // t wasn't present so, adding them in map as well as in the list
            map.put(t, true);
            uniqueList.add(t);
        }
    }
    return uniqueList;
}

Этот алгоритм займет O(n) времени с O(n) дополнительным пробелом (для HashMap).

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

Set<T> set = new LinkedHashSet<>(list);

Приведенный выше синтаксис в Java используется для получения set уникальных элементов из list с порядком вхождения элементов, аналогичным list.Затем преобразуйте этот набор в список.(ArrayList<T> uniqueList = new ArrayList<>(set);)

Я предполагаю, что сложность времени здесь также O(n).Я хотел знать, какой алгоритм Java использует для этого.

Я вижу, что класс называется LinkedHashSet, поэтому я подумал, что для этого они могут использовать некоторые LinkedList концепции, поэтому я посмотрел исходный код,и нашел эти вещи:

1. В LinkedHashSet.java конструктор выглядит так:

143: public LinkedHashSet(Collection<? extends T> c) 144: { 145: super(c); 146: } здесь является источником.

Итак, я посмотрел на конструктор родительского класса, т.е. HashSet, я нашел:

public HashSet(Collection<? extends E> c) { map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16)); addAll(c); }

Затем я искал метод addAll, я нашел его в классе AbstractCollection (который является прародителем класса HashSet), определение функции:

public boolean addAll(Collection<? extends E> c) { boolean modified = false; for (E e : c) if (add(e)) modified = true; return modified; }

Это вызов add, который выглядит так:

public boolean add(E e) { throw new UnsupportedOperationException(); } здесь .

Я не мог этого понять.Какой алгоритм они используют для этой задачи?

Answer 1

это LinkedHashSet конструктор:

public LinkedHashSet(Collection<? extends E> c) {
        super(Math.max(2*c.size(), 11), .75f, true);
        addAll(c);
    }

это функция addAll из java.util.AbstractCollection:

public boolean addAll(Collection<? extends E> c) {
        boolean modified = false;
        for (E e : c)
            if (add(e))
                modified = true;
        return modified;
    }

это функция добавления из java.util.HashSet:

public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

easy-peasy, если вы используете Intellij для поиска источника функции.

Answer 2

Для тех, кто ищет всю историю

Основывается на исходном коде LinkedHashSet , HashSet , LinkedHashMap .При создании LinkedHashSet, который расширяет HashSet с другой коллекцией (строка 143 LinkedHashSet.java),

public LinkedHashSet(Collection<? extends T> c)  
{  
  super(c);  
}

, которая будет вызывать (строка 136 HashSet.java):

public HashSet(Collection<? extends T> c)
{
  this(Math.max(2 * c.size(), HashMap.DEFAULT_CAPACITY));
  addAll(c);
}

и затем вызовите (строка 122 HashSet.java):

public HashSet(int initialCapacity, float loadFactor)
{
  map = init(initialCapacity, loadFactor);
}

Поскольку метод init переопределяется в LinkedHashSet

HashMap<T, String> init(int capacity, float load)
{
 return new LinkedHashMap<T, String>(capacity, load);
}

Основа map является LinkedHashMap.

В соответствии с Java-документом LinkedHashMap

Этот класс предоставляет все необязательные операции Map и разрешает нулевые элементы.Как и HashMap, он обеспечивает производительность при постоянном времени для основных операций (добавление, хранение и удаление), при условии, что хеш-функция правильно распределяет элементы между сегментами.Производительность, скорее всего, будет немного ниже производительности HashMap из-за дополнительных затрат на поддержание связанного списка, за одним исключением: для итерации по представлениям коллекций LinkedHashMap требуется время, пропорциональное размеру карты, независимо от ее емкости.,Итерация по HashMap, вероятно, будет более дорогой, требуя времени, пропорционального его емкости.

А add метод HashSet равен

public boolean add(E e) {
   return map.put(e, PRESENT)==null;
}

Следовательно, среднеевременная сложность O (n) для строительства.Для алгоритма, я думаю, вы можете прочитать код LinkedHashMap для деталей.Подробнее Чем внутренняя реализация LinkedHashMap отличается от реализации HashMap? , HashSet против LinkedHashSet

Answer 3

Чтобы ответить на вашу путаницу, метод add переопределен в HashSet следующим образом:

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

Обратите внимание, что LinkedHashSet расширяет HashSet расширяет AbstractSet расширяет AbstractCollection.

---

Таким образом, используемый алгоритм:

    for (E e : c)
        add(e);

, что составляет O(N) для LinkedHashSet, поскольку средняя сложность add для LinkedHashSet равна O(1).