用鑰匙直接算出位置,查找快到接近一步到位 —— Python 的 dict 和 set 就是它。
dict、set 底下就是這一套。
1. 一排桶 —— 先開一排有編號的桶子(0, 1, 2, …),資料就存在桶裡。
2. 雜湊函式算位置 —— 拿鑰匙丟進雜湊函式,吐出一個桶號:桶 = hash(鑰匙) % 桶數。
3. 存跟取都先算 —— 存:算出桶號,把資料丟進那桶。取:同一把鑰匙算出同一個桶號,直接去那桶拿。
4. 為什麼快 —— 「算位置」是固定幾步的事,不管你存了 10 筆還是 1000 萬筆,平均都是 O(1)。
O(n));雜湊表是「用算的直接跳到位置」,省掉翻找的功夫。代價是要多花一排桶的記憶體 —— 拿空間換時間。桶的數量有限,難免兩把不同的鑰匙算出同一個桶號 —— 這叫碰撞(collision)。碰撞一定會發生,重點是怎麼處理:
🔗 鏈結法(chaining) —— 最常見。每個桶掛一條 list,撞到的就接在後面串成一條鏈;要取的時候在這條短鏈裡找。上面下面那個視覺化跑的就是這招。
➡️ 開放定址(open addressing) —— 撞到就往下一個空桶塞,取的時候也照規則往下找。
關鍵 —— 只要桶夠多、雜湊夠均勻,每條鏈都很短,平均還是 O(1);最怕的是全部鑰匙都撞進同一桶,那就退化成一條長鏈,變回 O(n)。
dict/set 早就幫你把碰撞和自動擴充處理好了,平常寫程式根本不用管 —— 但面試會考、想自己刻一個要懂原理(見範例 7)。房號就是鑰匙。櫃檯不用一間間敲門找人,看房號直接算出樓層,走過去就到。
號碼牌對到固定的格子,拿牌直接開那一格,不用把所有櫃子翻一遍。
照部首或字母直接翻到那一區,不用從第一頁一路看到最後一頁。
把 7 把鑰匙(數字)一把把丟進 5 個桶,雜湊函式就是 桶 = 鑰匙 % 5。紫框是算出來該進的桶,綠色是順利入桶,紅色是碰撞後接到鏈尾。按「下一步」一步步看碰撞怎麼發生。
從 dict/set 的日常操作,到 Two Sum、分組、自己動手刻一個雜湊表、記憶化快取等經典應用。
❌ 拿 list 當鑰匙 —— dict/set 的鑰匙必須「不可變(hashable)」,用 list 當 key 會直接 TypeError。要用多個值當鑰匙,改用 tuple。
❌ 邊遍歷 dict 邊改它的大小 —— 在 for 迴圈裡 del 或新增鑰匙會 RuntimeError。先把要處理的收集起來,迴圈結束再一起動手。
❌ 直接用 d[key] 抓不確定存在的鑰匙 —— 沒這把鑰匙會 KeyError 當掉。不確定就用 d.get(key, 預設值)。
❌ 以為 dict 沒有順序 —— 舊觀念了。Python 3.7+ 保證照插入順序跑;但別靠它做排序,要排序還是用 sorted()。
桶 = 鑰匙 % 5,把 [10, 7, 15, 2, 12] 一把把丟進去,哪幾把會碰撞?最後每個桶裡各有誰?list 一個一個找是 O(n),雜湊表卻能 O(1)?雜湊表是拿什麼換到這個速度的?桶 = 0(不管什麼鑰匙都回 0),這個雜湊表會變成什麼樣子?查找複雜度掉到多少?把答案打到對話裡,我幫你對。