java中所有集合背后使用的数据结构。

Question

最近我被面试官问到，他让我给出java中所有集合背后的数据结构，例如ArrayList，Map等等，这些不是数据结构本身吗？如果不是，那么支持它们的是哪些数据结构？

Answer 1

由于java源代码提供了所有实现细节，因此我将只公开一些最常用的collections

• java.util.ArrayList<E>

ArrayList的实现在内部回退到Object的array。

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 */
transient Object[] elementData; // non-private to simplify nested class access

由于arrays具有固定大小，因此如果必要，在每次add调用时，ArrayList经由对System::arrayCopy本机调用来重新创建elementData。

• java.util.LinkedList<E>

LinkedList处理对象引用，而不是array。所有项E都存储在内部class Node<E>的实例中。

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

其中每个Node保持指向其下一个和前一个兄弟的指针。

LinkedList将只保留对其第一个和最后一个元素的引用，因此不支持随机访问：

/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;

/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

• java.util.HashMap<K,V>

它们将键和值存储到内部捆绑包类Node<K,V> extends Map.Entry<K,V>中。

通过函数调用HashMap::putVal将节点存储到节点array中

/**
 * The table, initialized on first use, and resized as
 * necessary. When allocated, length is always a power of two.
 * (We also tolerate length zero in some operations to allow
 * bootstrapping mechanics that are currently not needed.)
 */
transient Node<K,V>[] table;

此外，Hashmap使用一个EntrySet extends AbstractSet<Map.Entry<K,V>>集合，该集合不断反映table中的元素。

/**
 * Holds cached entrySet(). Note that AbstractMap fields are used
 * for keySet() and values().
 */
transient Set<Map.Entry<K,V>> entrySet;

然后，将entrySet公开为可迭代的collection

for ( Map.Entry<String, Integer> entry : this.myMap.entrySet() ) { /* ... */ }

• java.util.HashSet<E>

有趣的是，HashSet<T>使用了一个HashMap<T, Object>，正如我们已经看到的，它又是由java.util.Set<T>支持的。

private transient HashMap<E,Object> map;

您将看到，与其他java数据结构相比，HashSet的主体是有限的，因为它的大多数操作都只是对其内部HashMap结构的后备。

例如：

HashSet::add

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

HashSet::iterator

public Iterator<E> iterator() {
    return map.keySet().iterator();
}

Answer 2

ArrayList的底层数据结构是数组，LinkedList是链接对象，HashMap是LinkedList或树的数组。希望这能有所帮助。