hash_table [key] == NULL和hash_table.find（key）== hash_table.end（）之間的時間複雜度差異？

我目前正在寫一個線索樹，想知道如果有hash_table [key] == NULL和hash_table.find（key）== hash_table.end（）之間的時間複雜度差異？

hash_table [關鍵] == NULL

和

hash_table.find（鍵）== hash_table之間的任何時間複雜度差.end（）

如果鍵不在表格中。 C++ reference表示map :: find的時間複雜度爲log（n）

在此先感謝。

來源

2014-10-26 Cloud_cal

這些不等同;如果它不存在，第一個會在地圖中插入'key'。 – 2014-10-26 22:41:20

'std :: map'是一個二叉樹，而不是散列映射。你可能意思是'std :: unordered_map'。 – user657267 2014-10-26 22:42:22

感謝您糾正我，user657267 – 2014-10-26 22:49:13

這兩種情況下的時間複雜度都是相同的，但是如果您要做的只是檢查地圖中是否存在明顯有mapped_type這是一個指針，並且其中nullptr是無效值，則第一個表單將會嚴格減慢，因爲在缺席的情況下，它會先將插入地圖key的新值。所以這是你必須做的額外工作......這是最好的情況下，只有在非常嚴格的情況下才有效。

如果你想要做的是測試一個值的存在，只是做或者：

if (map.find(key) == map.end()) { 
    // absent 
}

或

if (!map.count(key)) { 

}

來源

2014-10-26 22:44:09 Barry

不完全相同：查找是恆定的時間，插入是攤銷合同，最壞的情況下，我相信。這些不一樣。 – Yakk 2014-10-26 22:57:44

@Yakk查找也可能是最壞的情況O（n）。 – Barry 2014-10-26 22:58:38

另外，如果您在同一時間插入並查找，如果您沒有找到它，那麼您已經確切地知道在哪裏插入它。 – Barry 2014-10-26 23:00:15

這兩種方法做完全不同的事情：

hash_table[key]插入一個key的元素，其默認構造值爲
hash_table.find(key)僅僅定位與在hash_table的key的元素，如果沒有找到它

在這兩種情況下返回end()中，對於一個hash_table複雜實際預期需要攤銷不變。也就是說，從複雜性的角度來看，沒有任何區別，但插入元素可能會產生不必要的成本（取決於是否插入了key;如果是這樣，保留引用可以使其更有效）。

如果hash_table恰好是一個std::map<K, V>而非std::unordered_map<K, V>兩個操作的複雜性是O(log n)其中n是在容器中的元素數。由於使用下標操作符插入元素，所以n可能更大：它可能不會改變複雜性（除非有更多的密鑰被嘗試而不是鍵），但使用find()的性能可能會更好。

來源

2014-10-26 22:46:38

hash_table [key] == NULL和hash_table.find（key）== hash_table.end（）之間的時間複雜度差異？

回答

相關問題