ArrayList.contains() 是否必须遍历所有项目才能进行检查？ HashMap.containsKey() 吗？我知道 HashMap.get() 不需要，但这就是它最有效的原因吗？

最佳答案

嗯嗯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;
}

没有。通常不会。有点儿？可能是？如果真的必须这样做？

开个玩笑吧，如果你想要查找速度，这就是你找到它的地方。只有迭代处理非常罕见的哈希冲突。如果你想要那个解释看here .

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() 与 HashMap.get()

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

如果您喜欢编译的 Java 文档并且宁愿点击而不是搜索，那么试试 this .

关于java - ArrayList.contains() 对比 HashMap.containsKey() 对比 HashMap.get()，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26568789/