Коллекция Java (1) структура коллекции

Collection<E>

public interface Collection<E> extends Iterable<E>

Интерфейс Collection — это корневой интерфейс коллекции, представляющий набор элементов. Но Collection не волнует, повторяется ли и упорядочена ли эта группа элементов. Он только предоставляет основной метод работы с этой группой элементов, как добавлять, как удалять, как зацикливать. Все реализующие классы должны предоставлять эти методы. Некоторые методы интерфейса Collection перечислены ниже:

int size();
boolean contains(Object o);
//Returns an iterator over the elements in this collection.
Iterator<E> iterator();
//Returns an array containing all of the elements in this collection.
Object[] toArray();
//Returns an array containing all of the elements in this collection; the runtime type of the returned array is that of the specified array.
<T> T[] toArray(T[] a);
boolean add(E e);
boolean remove(Object o);
void clear();

В методах интерфейса Collection следует отметить несколько моментов.

iterator()

Iterator<E> iterator();

Метод iterator возвращает объект, реализующий интерфейс Iterator, который используется для поочередного доступа к элементам коллекции.Интерфейс Iterator содержит 3 метода:

boolean hasNext();
E next();
void remove();

Все элементы в коллекции можно обойти, вызвав метод next() несколько раз.Следует отметить, что метод hasNext() необходимо вызывать перед вызовом next(), а next() можно вызывать только тогда, когда hasNext() возвращает true, например:

private static void collectionIterator() {
    //不用关注Arrays.asList，只需要知道他能返回一个Collection<E>接口就行
    Collection<String> collection = Arrays.asList("Java", "C++", "Python");
    Iterator<String> iterator = collection.iterator();
    while (iterator.hasNext()) {
        String string = (String) iterator.next();
        System.out.println(string);
    }
}
//output:
//Java
//C++
//Python

Поскольку JDK5, «для каждого» - это более удобный способ переоценки коллекции. Пока реализован интерфейс итерапы, «для каждого» можно использовать для прохождения коллекции, а эффект совпадает с использованием итератора. ИТЕРАЛЬНЫЙ интерфейс содержит только один метод:

Iterator<E> iterator();

private static void foreachCollectionIterator() {
	Collection<String> collection = Arrays.asList("Java", "C++", "Python");
	for (String string : collection) {
		System.out.println(string);
	}
}
//output:
//Java
//C++
//Python

toArray() и toArray(T[] a)

И toArray, и toArray(T[] a) возвращают массив всех текущих элементов. toArray возвращает массив Object[], тип которого нельзя изменить. toArray(T[ ] a) возвращает текущий переданный массив типа T, с которым удобнее работать пользователям, например, нужно получить массив типа String: toArray(new String[0]).

List<E>

public interface List<E> extends Collection<E>

Наиболее важной особенностью интерфейса List является ключевое слово упорядоченной коллекции. Классы, реализующие этот интерфейс, могут обращаться к элементам по целочисленному индексу. Он может содержать повторяющиеся элементы. В дополнение ко всем методам интерфейса Collection он также включает в себя некоторые методы, связанные с индексацией:

E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
int indexOf(Object o);
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
List<E> subList(int fromIndex, int toIndex);

Одной из вещей, требующих внимания, является класс ListIterator: Интерфейс List предоставляет другой итератор ListIterator, основанный на итераторе Iterator. Давайте взглянем на определение интерфейса ListIterator:

public interface ListIterator<E> extends Iterator<E> {
    boolean hasNext();
    E next();
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void remove();
    void set(E e);
    void add(E e);
}

Интерфейс ListIterator наследуется от интерфейса Iterator, поэтому их отличия заключаются в добавленных функциях интерфейса ListIterator:

• ListIterator может выполнять итерацию назад к предыдущему()
• ListIterator может быть получен до и после индекса nextIndex()
• ListIterator может добавлять новые значения add(E e)
• ListIterator может установить новый набор значений (E e)

Set<E>

public interface Set<E> extends Collection<E>

Интерфейс Set аналогичен интерфейсу Collection в сигнатуре метода, но имеет более строгое определение в описании метода.Самая важная особенность заключается в том, что он отказывается добавлять повторяющиеся элементы и не может быть доступен через целочисленные индексы. . Метод equals класса Set определяет, что если два набора равны, они содержат одни и те же элементы, но не обязательно в одном и том же порядке. Что касается того, почему необходимо определять интерфейс с полностью повторяющимися сигнатурами методов, я понимаю, чтобы сделать структуру фреймворка более четкой, изменив коллекцию с тех, которые могут добавлять повторяющиеся элементы, и тех, которые нельзя добавить, на те, к которым можно получить доступ через целое число индексы и те, к которым нельзя получить доступ через целочисленные индексы.Точки различаются, чтобы, когда программистам нужно реализовать свои собственные коллекции, они могли более точно наследовать соответствующие интерфейсы.

Map<K,V>

public interface Map<K,V>

Описание API для Map очень краткое: объект, который сопоставляет ключи со значениями, ключи не могут повторяться, и каждый ключ сопоставляется не более чем с одним значением. Из того, что ключ нельзя повторить, легко додуматься реализовать ключ через Set.Это доказывает и его интерфейсный метод SetkeySet().Некоторые типовые методы в Map интерфейс выбран ниже. :

int size();
boolean containsKey(Object key);
V get(Object key);
V put(K key, V value);
V remove(Object key);
void clear();
//Returns a Set view of the keys contained in this map.
Set<K> keySet();
Returns a Collection view of the values contained in this map.
Collection<V> values();
//Returns a Set view of the mappings contained in this map.
Set<Map.Entry<K, V>> entrySet();
boolean equals(Object o);
int hashCode();

java Set<K> keySet()Возвращает представление набора ключей, содержащегося в карте, которое представляет собой Set, указывающее, что ключи в карте не повторяются.java Collection<V> values()Возвращает представление коллекции значений, содержащихся в карте, Collection, указывающее, что значения в карте повторяемы.java Set<Map.Entry<K,V>> entrySet()Возвращает вид на сбору карты, включенный в карту, этот вид представляет собой набор , который определяется его набором ключа. Whenset () Возвращает набор типов map.centry и интерфейс map.centry определяет способ получения значения ключа, значение настройки, определяется следующим образом:

interface Entry<K,V> {
    K getKey();
    V getValue();
    V setValue(V value);
    boolean equals(Object o);
    int hashCode();
}

каркас класса

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

абстрактный класс

Несколько ключевых абстрактных классов, на которые следует обратить внимание, включают AbstractCollection;, AbstractMap, AbstractList и AbstractSet. Из названия видно, что они реализуют Collection , интерфейсы Map, List и Set. Ключевое различие между каждым набором заключается в структуре данных и алгоритме, используемом каждым набором, поэтому на уровне абстрактного класса нет конкретной структуры данных и алгоритма, а есть только базовая реализация методов работы с этими структурами данных.

AbstractCollection<E>

public abstract class AbstractCollection<E> implements Collection<E>

AbstractCollection в основном реализует все методы Collection, за исключением следующих методов:

public abstract Iterator<E> iterator();

public abstract int size();

public boolean add(E e) {
    throw new UnsupportedOperationException();
}

Если вам нужно реализовать немодифицируемую коллекцию, вам нужно реализовать только методы iterator() и size().Если вам нужно реализовать модифицируемую коллекцию, вы должны переопределить метод add(E e). В методах, уже реализованных AbstractCollection, можно обнаружить, что все методы, реализованные AbstractCollection, работают через Iterator.

public boolean contains(Object o) {
    //获取迭代器
    Iterator<E> it = iterator();
    if (o==null) {
        while (it.hasNext())
            if (it.next()==null)
                return true;
    } else {
        while (it.hasNext())
            if (o.equals(it.next()))
                return true;
    }
    return false;
}

AbstractList<E>

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>

Абстрактный класс AbstractList добавляет некоторые методы, характерные для интерфейса List, на основе абстрактного класса AbstractCollection, но большинство методов являются пустыми методами без конкретной реализации.

abstract public E get(int index);

public E set(int index, E element) {
    throw new UnsupportedOperationException();
}

public void add(int index, E element) {
    throw new UnsupportedOperationException();
}

public E remove(int index) {
    throw new UnsupportedOperationException();
}

public Iterator<E> iterator() {
    return new Itr();
}

public ListIterator<E> listIterator() {
    return listIterator(0);
}

public ListIterator<E> listIterator(final int index) {
    rangeCheckForAdd(index);

    return new ListItr(index);
}

Причина, по которой он не реализован, заключается в том, что AbstractList является абстрактным классом и не определяет конкретную структуру данных.Когда структура данных не определена, следует ли использовать целочисленный индекс напрямую или через цикл итератора для поиска Конкретное расположение более удобно и неопределенно, поэтому конкретная реализация определяется его подклассами. Стоит отметить, что AbstractList реализует два типа итераторов: Iterator и ListIterator, что значительно облегчает расширение подклассов:

private class Itr implements Iterator<E> {
//......
    public E next() {
        checkForComodification();
        try {
            int i = cursor;
            //向后遍历集合，通过get(i)获取当前索引的元素，每次调用之后cursor = i + 1，get(i)为抽象方法
            E next = get(i);
            lastRet = i;
            cursor = i + 1;
            return next;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }

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

        try {
            //通过AbstractList<E>类的remove方法来删除元素，AbstractList<E>中remove(int index)是一个空方法，需要子类来实现
            AbstractList.this.remove(lastRet);
            if (lastRet < cursor)
                cursor--;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException e) {
            throw new ConcurrentModificationException();
        }
    }
}
//......

private class ListItr extends Itr implements ListIterator<E> {
//......
    public E previous() {
        checkForComodification();
        try {
            int i = cursor - 1;
            //向前遍历集合，通过get(i)获取当前索引的元素，每次调用之前cursor - 1，get(i)为抽象方法
            E previous = get(i);
            lastRet = cursor = i;
            return previous;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }
//......
}

AbstractSet<E>

public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E>

Абстрактный класс AbstractSet очень прост в реализации, только методы equal и hashCode реализованы на основе абстрактного класса AbstractCollection, но о конкретной реализации все равно нужно судить по методу contains(), т.к. Интерфейс Тип не учитывает порядок элементов, поэтому, если два набора AbstractSet содержат одни и те же элементы, они считаются равными, и порядок элементов не обязательно должен быть одинаковым. в то время как AbstractList должен быть в том же порядке.

//AbstractSet<E> 中的 equals
public boolean equals(Object o) {
    if (o == this)
        return true;

    if (!(o instanceof Set))
        return false;
    Collection<?> c = (Collection<?>) o;
    if (c.size() != size())
        return false;
    try {
        //containsAll在AbstractCollection<E>中已经实现，只要包含所有元素就可以
        return containsAll(c);
    } catch (ClassCastException unused)   {
        return false;
    } catch (NullPointerException unused) {
        return false;
    }
}

//AbstractCollection<E> 中的containsAll
public boolean containsAll(Collection<?> c) {
    for (Object e : c)
        if (!contains(e))
            return false;
    return true;
}

//AbstractList<E> 中的equals
public boolean equals(Object o) {
    if (o == this)
        return true;
    if (!(o instanceof List))
        return false;

    ListIterator<E> e1 = listIterator();
    ListIterator<?> e2 = ((List<?>) o).listIterator();
    //需要两个集合中的元素以及元素顺序都相同才返回true
    while (e1.hasNext() && e2.hasNext()) {
        E o1 = e1.next();
        Object o2 = e2.next();
        if (!(o1==null ? o2==null : o1.equals(o2)))
            return false;
    }
    return !(e1.hasNext() || e2.hasNext());
}

AbstractMap<K,V>

public abstract class AbstractMap<K,V> implements Map<K,V>

Абстрактный класс AbstractMap реализует все основные методы, кроме метода entrySet(), среди которых Set keySet(), возвращающий набор ключей, и Collection values(), возвращающий набор значений, очень важно в реализации. Интересно, что из возвращаемого значения создается новая коллекция, но фактическая реализация заключается в возврате объекта класса, который реализует Set или Collection. Все операции над объектом класса основаны на исходном таблица сопоставления.Такая интересная операция называется просмотром, и во фреймворке java.util есть много приложений. Преимущество использования представлений здесь заключается в том, что в абстрактном классе вам не нужно определять, каков конкретный класс реализации возвращаемого Set или Collection, поэтому вы можете максимизировать абстракцию, когда абстрактный класс не решить, какую структуру данных использовать. Функции класса повышают удобство расширения. Исходный код keySet():

public Set<K> keySet() {
    Set<K> ks = keySet;
    if (ks == null) {
        ks = new AbstractSet<K>() {
            public Iterator<K> iterator() {
                return new Iterator<K>() {
                    //获取原映射表的迭代器来实现自己的迭代器
                    private Iterator<Entry<K,V>> i = entrySet().iterator();

                    public boolean hasNext() {
                        return i.hasNext();
                    }

                    public K next() {
                        return i.next().getKey();
                    }

                    public void remove() {
                        i.remove();
                    }
                };
            }

            public int size() {
                //直接操作原映射表的size()方法
                return AbstractMap.this.size();
            }

            public boolean isEmpty() {
                return AbstractMap.this.isEmpty();
            }

            public void clear() {
                AbstractMap.this.clear();
            }

            public boolean contains(Object k) {
                return AbstractMap.this.containsKey(k);
            }
        };
        keySet = ks;
    }
    return ks;
}

Суммировать

Структура Java.UTIL Armorce по-прежнему очень понятна, из классификации интерфейса абстрактный класс реализует каждый интерфейс, обеспечивая очень хорошую структуру растяжения, обеспечиваю большое удобство для последующих реализации и настраиваемых расширений. В дополнение к абстрактным классам и интерфейсам Java.util Framework также обеспечивает ряд других структур, он не слишком высок в частоте использования, таких как очередь , DECE и тому подобное. В более поздних главах подробно объясним реализацию нескольких ключевых коллекций, анализ лучше от всех аспектов структур данных, алгоритмов и производительности.