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

Question

我刚刚在java.util.Hashtable.java中看到了contains方法的代码.它有一个循环,它扫描Hashtable中的每个条目,并将其与传递的参数进行比较.

我读到包含方法需要恒定的时间.当它有一个扫描每个条目的循环时,它怎么可能.

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

Answer 1

Hashtable.contains()试图找到一个具有相同值的条目.它是按键查找的,它是哈希表中的常量时间(通常情况下).

文档澄清了这一点:

测试某些键是否映射到此哈希表中的指定值.此操作比containsKey方法更昂贵.

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