Какой алгоритм используется для преобразования 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(); } здесь .

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


java set hashmap algorithm linkedhashset
person Amit Upadhyay    schedule 22.09.2018    source источник
comment
Где ваш источник/версия для LinkedHashSet.java? Я вижу другой контент с номером строки, указанным в github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/.   -  person samabcde    schedule 22.09.2018
comment
@samabcde это   -  person Amit Upadhyay    schedule 22.09.2018
comment
@samabcde - номера строк не имеют значения. Этот аспект кода одинаков для нескольких версий. (Кроме того, Java 7 намного устарела.)   -  person Stephen C    schedule 22.09.2018
comment
add — это полиморфный метод (все методы в Java). Посмотрите здесь stackoverflow.com/questions/ 4605669/   -  person algrid    schedule 22.09.2018

Ответы (3)


arrow_upward
3
arrow_downward

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

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

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

Что вызовет (HashSet.java строка 136):

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 vs LinkedHashSet

person samabcde    schedule 22.09.2018
comment
Да: требует редактирования означает, что любой может исправить вопрос, сделав его доступным для ответа. Здесь, ОП, человек, задающий вопрос, должен добавить информацию. Тогда вам лучше поискать какую-то близкую причину. Помимо этого: я ценю быстрое и дружеское возвращение! - person GhostCat; 06.11.2018

arrow_upward
3
arrow_downward

Чтобы ответить на ваше замешательство, метод 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).

person Stephen C    schedule 22.09.2018
comment
да, этот метод добавления определен в классе HashSet, но конструктор в классе HashSet вызывает метод addAll, которого нет в HashSet, я нашел его в классе AbstractCollection, который является прародителем класса HashSet. Итак, как метод прародителя может вызвать метод дочернего класса? - person Amit Upadhyay; 22.09.2018
comment
наследование. дочерний класс наследует методы прародителя - person Jason; 22.09.2018
comment
AddAll находится в AbstractCollection. Это метод, который вызывает конструктор LinkedHashSet. Итак, краткий ответ — (как говорит Джейсон) наследование. - person Stephen C; 22.09.2018
comment
@Jason Да, вы правы, но я спросил how can a grandparent's method call child class method? Наследование даст эту возможность дочернему классу. Кроме того, я вижу подпись AbstractCollection как: public abstract class AbstractCollection<E> implements Collection<E> она не наследуется. - person Amit Upadhyay; 22.09.2018
comment
@AmitUpadhyay — наследование дает возможность вызывать (видимые) методы, объявленные во всех суперклассах. Родитель, прародитель... вплоть до java.lang.Object. (При условии, что метод не был переопределен в промежуточном классе.) Вероятно, вам приходилось знакомиться с основами наследования в Java, потому что это довольно фундаментально. - person Stephen C; 22.09.2018
comment
@AmitUpadhyay Это позднее связывание и полиморфизм - person Maxim; 22.09.2018
comment
@StephenC, спасибо, я знаю, что вы пояснили выше, но я пропустил написанный там комментарий <p>Note that this implementation will throw an * <tt>UnsupportedOperationException</tt> unless <tt>add</tt> is * overridden (assuming the specified collection is non-empty). Теперь я понял. Кроме того, я спрашивал, как дочерний метод может иметь область действия в родительском классе?.это. Благодарность! - person Amit Upadhyay; 22.09.2018

arrow_upward
2
arrow_downward

это 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;
    }

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

person kingGarfield    schedule 22.09.2018