雜湊表

雜湊表
類型	無序關聯陣列
發明時間	1953年
時間複雜度以大O標記
演算法 平均 最差 空間 Θ(n) O(n) 搜索 Θ(1) O(n) 插入 Θ(1) O(n) 鏟走 Θ(1) O(n)

雜湊表（hash table）係一種用嚟整關聯陣列（associative array；抽象資料型別，用嚟將每件數據都掕個獨特嘅名俾佢）嘅數據結構。

一幅雜湊表會用一個雜湊函數（hash function）嚟由一個輸入（key）嗰度計出一個號碼（index），用呢個號碼嚟由一個陣列（buckets）嘅位嗰度搵出想要嗰件數據，例如想像一個用嚟記住一個組織裏面每個員工嘅名同電話號碼嘅程式，會由查緊嗰個員工嘅名（key）嗰度計出一個號碼，個號碼表示嗰個員工嘅電話號碼喺個陣列嘅邊個位，然後個程式就可以用 output = buckets[n];（攞個陣列入面對應嗰件數據）噉嘅方法攞到想要嘅數據（下圖）。