Chinese, Traditional subtitles

← 05x-01 Hash Tables

Get Embed Code
3 Languages

Showing Revision 3 created 01/02/2013 by Shalley Tsay.

  1. 在論壇上關於 hash table
  2. 我們有很多很棒的問題
  3. 一個例子是學生 Baracha 提問:
  4. "Python 如何決定當字典成長變大時,
  5. 要有多少'桶' (bucket) 呢?"
  6. 這是一個重要的問題
  7. 關於 hash table,還有很多、很多有趣的事情
  8. 但在第五單元我們沒有談到
  9. 如果記憶體是免費、廉價、而且同樣地快速
  10. 無論你需要多少
  11. 你寧願 hash table 愈大愈好,對嗎?
  12. 你會想要你的 hash table 裡有數十億個'桶"
  13. 然後在每個'桶'內,就不必儲存一個以上的項目
  14. 但正如我們在第三單元所見,記憶體可能很昂貴
  15. 速度愈快而且愈接近處理器的記憶體
  16. 它的費用也愈昂貴
  17. 所以你的記憶體數量非常有限
  18. 這是儘量保持 hash table 小的原因
  19. 這是一個艱難的權衡
  20. 好的 hash table 實作
  21. 嘗試為你做了權衡
  22. 讓你在性能和記憶體使用上,得到適當的平衡
  23. 他們根據負載因數 (load factor) 來做權衡
  24. 我們確實在第四單元使用它
  25. 也就是'項目的數量'除以'桶數'
  26. 我們在第五單元有一個問題, "N 除以 B"
  27. 在問題中,你看到'桶數'和'項目的數量'變化所產生的影響
  28. 當你做這件事時,你必須擔心一件事
  29. 如果你只看著'關鍵字數目'和'桶數'
  30. 這是平均的大小,但在許多應用中的問題
  31. 更重要的是'最壞的大小' (worse size),
    即使平均大小是相當小的
  32. '最壞的大小' (worse size) 可能會比這個大得多
  33. 如果對於最壞情況 (worse case) 的項目
    做查找 (lookup) 開始變得很糟
  34. 然後你會想要更多的'桶'
  35. 或是以某種方式來改變你的 hash 函式
  36. 所以,對於一個典型的 hash table 實作
  37. 通常目標是要讓負載因數 (load factor) 實際上小於 1
  38. 對於 Python 的字典實作
  39. 如果關鍵字的數量超過約 2/3
  40. 我認為它實際上剛好是表的大小的 2/3
  41. 這是表的大小重新做調整的點
  42. 表會變成兩倍大
  43. 這會改變每個字所出現的'桶'
  44. 因為我們之前看到 hash table 的結果
  45. 取決於你所擁有的'桶數'
  46. 因此必須要將資料複製到新的 hash table
  47. 新的 hash table 有更多的空間,會使得查找速度更快
  48. 也就是說,如果你在 hash table 有大約 100 萬個項目
  49. 你會期待有 150 萬個'桶'
  50. 但當你增加到 2/3 的門檻值
  51. 然後你要把'桶'的大小增為兩倍
  52. 所以你最後會有 300 萬'桶',
  53. 如果你在 2/3 的門檻值上多加一個項目
  54. 所以,如果你比較這個與我們在第五單元所做的
  55. 你可能會驚訝它的負載因數是如此之低
  56. 我們做的 hash table 範例
  57. '桶數'非常小
  58. 每'桶'有許多項目
  59. 這部分是為了更容易看出到底是怎麼回事
  60. 因為如果你看到一個 hash table 有上千個空'桶'
  61. 那將很難列印出來
  62. 但其他的原因是
  63. 我們在第五單元實作 hash table 的方式是,
    每個'桶'是一個列表
  64. 使用列表,這是一種相當昂貴的資料結構
  65. 你得建立這些空列表
  66. 才能建立你的 hash table
  67. Python 字典的實作方式
  68. 只是一個扁平的列表
  69. 這意謂著每個 hash 值只有一個空間
  70. 如果 hash 到一個特定的'桶'
  71. 只存在一個空間
  72. 也就是說,如果兩個物件 hash 到相同的'桶'
  73. 你必須去做點別的事情
  74. Python 字典實作如何處理呢
  75. 你需要另一個多餘的地方來放置它
  76. 你有方法來決定當第一個'桶'滿了時
  77. 到那裡尋找下一個
  78. 這使得查找和添加項目到表中,變得更為複雜
  79. 這就是為什麼我們沒有這樣做的原因
  80. 但這也意謂著,使用較少的記憶體
  81. 因為你不必為這些'空桶'
  82. 存放這些空列表
  83. "Beautiful Code" 這本書中有一章很棒
  84. 談的是所有關於 Python 字典的實作
  85. 所以,如果你對實際的實作感到興趣
  86. 我鼓勵你看看這一章