哈希表中包含方法的時間複雜度？

我剛剛在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

哈希表中包含方法的時間複雜度？

回答

相關問題