先説結論：

python的dict，底層是哈希表（hash table）與開放尋址方案（二次探測 + 偽隨機跳躍）

其中，

核心結構：哈希表是一個“數組”

每個 dict 底層對應一塊數組（table），數組每個槽位（slot）可能存一個 key-value。

index:   0   1   2   3   4   5   6   7
value:  [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

任何輸入的key 會被哈希（hash(key)）

d["abc"] = 123

# python會計算

h = hash("abc")   →  得到一個整數，如 918273645
slot = h % table_size   →  如 918273645 % 8 = 5

於是 key 放到 槽位 5

index:   0   1   2   3   4   5   6   7
value:  [ ] [ ] [ ] [ ] [ ] [('abc',123)] [ ] [ ]

如果計算出的槽位已經被佔用，dict 不會鏈表化存儲，而是 繼續找下一個空槽位，其中會使用 開放尋址（Open Addressing）

slot 6 空？ → 放這裏
slot 6 也有人？ → 看 slot 7

dict 會控制“負載因子”（使用率），比如如果槽位使用率超過 ~2/3，自動擴容。擴容後空間很大，衝突變少，因此 dict 的性能保持 O(1)。

擴容操作：

• table 大小擴成原來的 2 倍

• 所有 key 重新哈希並放入新 table（rehash）

看具體的應用場景：使用dict進行查找、插入操作，時間複雜度是O(1)

1. 查找過程

查找 d[key]：

1. 計算 hash(key)

2. 定位槽位 slot = hash % table_size

3. 看到槽位裏是不是這個 key

   • 是 → 找到

   • 否 → 使用開放尋址規則繼續探測

那麼影響時間長短的，就要看hash算法的底層原理了，hash函數大致是位運算+隨機化