哈希表中包含方法的时间复杂度?

I just saw the code of contains method in java.util.Hashtable.java. It has a loop that scans through each entry in the Hashtable and compares it with the argument passed.

我刚刚看到java.util.Hashtable.java中包含方法的代码。它有一个循环，扫描哈希表中的每个条目，并将其与传递的参数进行比较。

I read that contains method takes constant time. How is it possible when it has a loop that scans through each entry.

我读到包含方法需要常数时间。当它有一个循环扫描每个条目时，怎么可能呢?

 public synchronized boolean contains(Object value) {
if (value == null) {
    throw new NullPointerException();
}

Entry tab[] = table;
for (int i = tab.length ; i-- > 0 ;) {
    for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {
    if (e.value.equals(value)) {
        return true;
    }
    }
}
return false;
}

1 个解决方案

#1

Hashtable.contains() tries to find an entry with an equal value. It's lookups by key which are constant time (in the usual case) in hash tables.

contains()尝试查找具有相等值的条目。它是按键查找的，在哈希表中是常数时间(通常情况下)。

The docs clarify this:

这个文档说明:

Tests if some key maps into the specified value in this hashtable. This operation is more expensive than the containsKey method.

测试某些键是否映射到此hashtable中的指定值。这个操作比containsKey方法更昂贵。

Note that this method is identical in functionality to containsValue, (which is part of the Map interface in the collections framework).

请注意，此方法在功能上与containsValue相同(它是集合框架中的Map接口的一部分)。

#1