來單純技術討論一下好了
其實 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 儲存空間帶來的限制，原理很簡單，如果不太
清楚請中文維基就可以輕鬆看懂（一般大學的分散式系統課程也都會教到）。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 138.246.3.10 (德國)
※ 文章網址: https://www.ptt.cc/bbs/Soft_Job/M.1682195508.A.1B8.htmlplsmaop1樓通常效能的差異不在於 hash ，而是不需要一直分配新的記 04/23 06:02
→ plsmaop2樓憶體 04/23 06:02
→ previa3樓主要差異就是在整個解法能不能scale 而已 04/23 08:11
→ ku3999994樓陣列如果資料一直往後放不排序 查詢速度就是n 如果要排 04/23 08:15
→ ku3999995樓序就要移動大量資料 即使不用分配也快不到哪吧 04/23 08:17
等等 一般的做法是一個布林陣列然後 node tag 當做 index
因此找 visited node 就是 O(1)
我其實沒很仔細看 Nic 怎麼實作
還是他的實作是你說的方式！？
s06yji36樓陣列是固定size的東西。如果紀錄的東西是整數，可以直接 04/23 08:44
→ s06yji37樓把他當作陣列的index，搜尋就是O(1) 04/23 08:44
→ s06yji38樓Nic作法是O(n) XD 04/23 08:45
→ s06yji39樓但是後來換成用Set了 04/23 08:45
peter9810樓用hash不代表要一直分配新的記憶體 04/23 11:43
→ peter9811樓一直動態分配記憶體的不是hash 兩者關係並不大 04/23 11:43
s06yji312樓嚴格來說你要講HashSet才對。 04/23 12:38
→ NTHUlagka13樓樓上你hash不動態分配記憶體 那新的值進來你要怎辦 你 04/23 15:30
→ NTHUlagka14樓一開始不知道要開多大的Hash吧 04/23 15:30
→ NTHUlagka15樓還是其實C++hash背後也是vector 那就沒事了 04/23 15:43
a123456728916樓hashmap/set都會牽涉到Load factor 當現在容器裡裝 04/23 15:51
→ a123456728917樓了超過一定比例的數量就會自動擴容 但確實hash與否 04/23 15:51
→ a123456728918樓和是否動態配置記憶體是兩回事 此外本文的方法一 04/23 15:51
→ a123456728919樓也可以視為是一種hashset 04/23 15:51
→ a123456728920樓以上自動擴容我講的是現今大多數語言的實作 04/23 15:52
→ peter9821樓額 s06yji3 看來你真的不董hash用到的vector其動態配置 04/23 19:43
→ peter9822樓的做法&時機點 建議你找一本簡單的演算法課本讀一下 = = 04/23 19:43
→ peter9823樓hash會用到動態配置 但是hash如果遇到效能問題 問題根 04/23 19:44
→ peter9824樓源不是在動態配置 這是兩回事 每次都用動態配置會造成 04/23 19:45
→ peter9825樓效能問題沒錯 但問題是hash不會出現老是一直需要動態配 04/23 19:45
→ peter9826樓置 去把大三演算法課本拿出來複習一下 = = 肯定有教 04/23 19:45
→ peter9827樓靠 at錯人 是NTHUlagka可以去讀一下演算法 04/23 19:47
→ peter9828樓兩件事 loading factor + 類似exp backoff的作法 04/23 19:48
→ peter9829樓並不會讓hash有動態配置造成的效能問題 04/23 19:48
→ saladim30樓Hash還有一些簿記的overhead, 而且長的也有80分像array 04/23 20:30