Python 算法 09 -- 散列表

如果你是第一次聽說散列表，不要緊！因為你可能根本不需要自己去實現散列表，任何一門優秀的語言都提供了散列表實現。Python 提供的散列表實現為字典 ，你可使用函數 dict 來創建散列表。

前面我們學習了 2 種數據結構：

● 數組

● 鏈表

我們知道數組和鏈表各有優劣，如果我們“中西結合”呢？

比如說我們手機的通訊錄，其中每個姓名都有對應的電話號碼

如果我們要設計一個散列表（數組+鏈表的結構），需要考慮哪些因素？

我們知道 Python 中的字典是 key - value 的形式，如果我們插入 key = 'Python大星'，value = 123456

的值，如何讓後續更多的 key - value 能均勻的分配到數組上，而不是在數組某個索引值上集中，浪費空間？

1、hash算法

常用的算法是 hash 算法，index = HashCode（Key） & （Length - 1）

2、數組默認長度

一般選擇 16 或者 2 的冪次方，這是因為這個長度計算的 index 能平均分配在 Length - 1 內

3、擴容機制

為什麼需要擴容？設想當我們添加的元素越來越多時，會發生 hash 碰撞，就是說 hash 算法得出的 index 是同樣的。我們知道鏈表在查找的時候，從從頭節點開始查找，相對於數組是較慢的。這個時候我們可以在一定的閾值範圍內採取擴容機制，使添加的元素平攤到其他地方。

Python 語言：

① 創建通訊錄，新建一個散列表

② 添加新的聯繫人

③ 查找人員

---

>>>

---

---

閱讀更多 Python大星 的文章

關鍵字: 數據結構 Python 列表

---