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

Question

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

Answer 1

作为java资源提供了所有的实现细节，我将只公开一些最常用的 collections :

---

• java.util.ArrayList<E>

执行ArrayList在内部回退到 array的 Object .

/**
 * 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有固定大小，ArrayList在每个 add调用，重新创建，如有必要elementData通过 native 调用 System::arrayCopy .

---

• 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保留指向其下一个和 previous sibling 姐妹的指针。

A 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>>不断反射(reflect)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;

您会看到 HashSet 的正文与其他 java 相比有点有限数据结构，因为它的大部分操作只是对其内部 HashMap 的回退结构。

例如:

HashSet::add

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

HashSet::iterator

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