→ juiz:是的,所以一般直接用 for k in dct: 03/12 19:48
→ Arton0306:keys()不就回傳所有的key而已嗎 應該O(1)吧 03/12 22:05
→ uranusjr:資料很散跟複雜度大哪有關係... 03/12 22:15
→ bin90909:我的意思是不太清楚他是如何得知Hash table內哪些位址存 03/12 22:19
→ bin90909:了資料? 因為他分配位址的時候是利用hash function指定的 03/12 22:19
→ bin90909:這樣的話他要找哪些位址有存資料的話, 照理講應該掃遍所 03/12 22:20
→ bin90909:有空間才能確定? 就算是用tree搜尋也要log(n) 03/12 22:21
推 Arton0306:對喔 那應該是 我原本想每次add用list記下 但忘了有del 03/12 22:26
→ Arton0306:orz 我搞錯了 就算只有add 也不行 冏 03/12 22:29
→ Arton0306:果然O(n) 不過我上面講錯 沒del是可以O(1) 不過不重要.. 03/12 22:42
→ bin90909:感謝A大熱心提供資料!! 不過有點不清楚keys()有沒有優化 03/12 22:45
→ bin90909:過, 不知道去哪裡查他的implement方式? 03/12 22:46
推 Arton0306:等等 它的O(n)有特別注明在Note 不是指hash後table大小 03/12 22:49
→ Arton0306:implement我也不知道 大概看source code吧 03/12 22:50
推 Arton0306:剛看了一下source code 有個 dictobject.c 03/13 01:01
→ Arton0306:裡面寫了很多註解 可以參考看看 我大概看到兩個有趣的 03/13 01:02
→ Arton0306:1. 連續的整數或字串 hash 也是非常連續的 03/13 01:02
→ Arton0306:2. 它的表大小會動態增減 所以若add的不多 表就較小 03/13 01:04
→ bin90909:謝謝A大, 裡面寫得蠻清楚的! 03/13 23:41