std :: unordered_set是否爲任何對象提供分期不變的查詢時間而不考慮謂詞？

Question

在std::unordered_set中，我們提供了一個謂詞來表示兩個對象A和B是否相等。我的問題是，假設我們需要O(k)時間來確定A和B是否相等。 unordered_set::find是否仍然採用攤銷的固定時間或是否需要攤銷O(k)時間？

Answer 1

僅由std::unordered_map保證的平均不變查詢複雜度指的是地圖中元素的數量。如果該映射至少包含一個具有相同散列值*的元素，則必須至少執行一次該鍵的完整比較。如果這個比較是O（k），那麼顯然這個查找也變成了O（k），但是這隻適用於相當大的k。

*）我猜在大多數實現中它不僅僅是相同的哈希，而是如果在同一個桶中有一個元素。