來單純技術討論一下好了
其實 Visit 也不用限制一定要用 HashMap/HashSet 做
Leetcode 上很多題目的 nodes tag 都是連續的數字或英文字母
這個時候用一般的 Array 效能就會比 HashMap/HashSet 好非常多:
1. 不需動態分配記憶體(感謝一樓提醒)
2. 不需進行 Hash 運算
但也正如同大多數大大所說
一般人的想像場景不會是連續的標籤
在 nodes tag 都不連續的情況下
例如:1, 100, 10000, 1000000, 100000000
這個時候用 Array 就是低能兒了
個人淺見如上
如有錯誤還請各位大大指正
補充 peter98 與 NTHUlagka 底下關於 Hash 的討論(小弟對於 C++ 只能算是略懂,如
果錯誤就再麻煩指正了):
1. 就 C++ Standard Library 對於 HashMap/HashSet 的實作,一開始會先分配一定數量
的 buckets,後續如果超過 loading factor(預設 1.0),再動態增加(std::vecotor
的實作上
一般是加倍)。
2. 關於 Exponential Backoff 與 Bloom Filters 等其他技術,目前尚未實作於 Standa
rd Library 裡,所以有需求的話要自行實作。
3. Bloom Filters 可以解放傳統 HashSet 儲存空間帶來的限制,原理很簡單,如果不太
清楚請中文維基就可以輕鬆看懂(一般大學的分散式系統課程也都會教到)。