数据结构，一切结构都来自于两个基础:数组与链表02

上文分析了最简单的ArrayList与LinkedList，数组与链表01。

这边咱们接着分析

List<String> list3 = new Stack<>();

public class Stack<E> extends Vector<E> {}
public class Vector<E> extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}

可以看到Stack类继承自Vector，Vector类继承了AbstractList并实现了三个接口

那么Vector实现运用了什么呢？可以看到依然是一个数组。

public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    /**
     * The array buffer into which the components of the vector are
     * stored. The capacity of the vector is the length of this array buffer,
     * and is at least large enough to contain all the vector's elements.
     *
     * <p>Any array elements following the last element in the Vector are null.
     *
     * @serial
     */
    protected Object[] elementData;
}

Map中最常用的为HashMap

Map<String,String> map1 = new HashMap<>();

可以看到HashMap中，用到的是一个链表

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

增加一个元素时，可以看到是增加一个Node()，也就是增加了一个链表的节点。

高并发容器，大名鼎鼎的ConcurrentHashMap，就是数组和链表的结合体

Map<String,String> map5 = new ConcurrentHashMap<>();

    /**
     * The array of bins. Lazily initialized upon first insertion.
     * Size is always a power of two. Accessed directly by iterators.
     */
    transient volatile Node<K,V>[] table;

如上图代码，核心结构就是一个Node数组。

最后我们可以再看一个java中的TreeMap

Map<String,String> map6 = new TreeMap<>();

    static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK;

        /**
         * Make a new cell with given key, value, and parent, and with
         * {@code null} child links, and BLACK color.
         */
        Entry(K key, V value, Entry<K,V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }
}

代码中可以看到这个一个有着三个指针的一个Entry，其实也就是一个多指针链表。

总结：

不要小看数组和链表，这是一切数据结构的基础。

int[] array = new int[10];

Node node = new Node;