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

Я хотел получить 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: } вот источник.

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

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

  1. Далее я искал 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(); } здесь

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

Источник

3 ответа

Решение

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

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

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

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

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

Источник

Чтобы ответить на вашу путаницу, 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),

Источник

Это 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, чтобы найти источник функции.

Источник
Другие вопросы по тегам