ArrayList.contains()与HashMap.containsKey()与HashMap.get()的区别

Question

ArrayList.contains() 需要遍历所有项来进行检查吗？HashMap.containsKey() 呢？我知道 HashMap.get() 不需要，但这是为什么它是最有效的原因吗？

- Adam Johns

Answer 1

ArrayList.contains()方法是否进行了迭代操作？

/**
 * Returns <tt>true</tt> if this list contains the specified element.
 * More formally, returns <tt>true</tt> if and only if this list contains
 * at least one element <tt>e</tt> such that
 * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
 *
 * @param o element whose presence in this list is to be tested
 * @return <tt>true</tt> if this list contains the specified element
 */
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

/**
 * Returns the index of the first occurrence of the specified element
 * in this list, or -1 if this list does not contain the element.
 * More formally, returns the lowest index <tt>i</tt> such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
 * or -1 if there is no such index.
 */
public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

是的。确实如此。

---

HashMap.containsKey() 是否进行迭代？

/**
 * Returns <tt>true</tt> if this map contains a mapping for the
 * specified key.
 *
 * @param   key   The key whose presence in this map is to be tested
 * @return <tt>true</tt> if this map contains a mapping for the specified
 * key.
 */
public boolean containsKey(Object key) {
    return getEntry(key) != null;
}

/**
 * Returns the entry associated with the specified key in the
 * HashMap.  Returns null if the HashMap contains no mapping
 * for the key.
 */
final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }

    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

通常来说不会这样做。有点？也许？如果真的必须的话？

开玩笑的，如果你想要查找速度，那么这就是你要找的地方。只有当出现非常罕见的哈希冲突时，迭代才会处理。如果你想要解释，请看这里。

---

Java 8 更新:

在 Java 8 中，ArrayList.contains()... 是一样的。无聊。

但是，HashMap.containsKey() 现在使用 getNode()。漂亮。

/**
 * Returns <tt>true</tt> if this map contains a mapping for the
 * specified key.
 *
 * @param   key   The key whose presence in this map is to be tested
 * @return <tt>true</tt> if this map contains a mapping for the specified
 * key.
 */
public boolean containsKey(Object key) {
    return getNode(hash(key), key) != null;
}

/**
 * Implements Map.get and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @return the node, or null if none
 */
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

正如那个 while 循环告诉你的那样，它仍然偶尔进行迭代。但是，这种情况很少发生。

我会给出有关效率的详细信息，但这已经有一个答案了here。

---

HashMap.containsKey() vs HashMap.get()

由于它们都将大部分工作委托给相同的方法（7 中的 genEntry() 和 8 中的 getNode()），因此我认为您不太可能在它们之间看到太多性能差异。 它们的迭代行为将是相同的。

如果您喜欢编译后的 Java 文档，并且宁愿点击而不是搜索，请尝试这个链接。

- candied_orange