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

我刚刚在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; 
}

来源

2012-01-04 sampath

你能发表那部分代码吗？ – 2012-01-04 21:52:10

您是否在询问包含或containsKey。包含检查以查看地图是否包含值，这需要检查所有条目。 – 2012-01-04 21:54:23

如果你关心性能，你应该考虑HashMap或ConcurrentHashMap，如果你需要它是线程安全的。 – 2012-01-04 21:58:58

Hashtable.contains()试图找到与等值的条目。它是由密钥查找，它们是散列表中的常量时间（通常情况下）。

该文档澄清这一点：

测试是否某个键映射到在该散列表中指定的值。此操作比containsKey方法更昂贵。

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

来源

2012-01-04 21:52:06

@JamesMontagne：已经在编辑:) – 2012-01-04 21:54:18

不够公平，评论编辑:) – 2012-01-04 21:55:06

Hashtable.contains（）方法的时间复杂度是多少？ – sampath 2012-01-06 18:55:26

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

回答

相关问题