雜湊表
維基百科,自由的 encyclopedia
雜湊表(Hash table,也叫雜湊表),是根據鍵(Key)而直接查詢在記憶體儲存位置的資料結構。也就是說,它通過計算出一個鍵值的函式,將所需查詢的資料對映到表中一個位置來讓人查詢,這加快了尋找速度。這個對映函式稱做雜湊函式,存放記錄的陣列稱做雜湊表。
一個通俗的例子是,為了尋找電話簿中某人的號碼,可以建立一個按照人名首字母順序排列的表(即建立人名到首字母
的一個函式關係),在首字母為W的表中尋找「王」姓的電話號碼,顯然比直接尋找就要快得多。這裡使用人名作為關鍵字,「取首字母」是這個例子中雜湊函式的函式法則
,存放首字母的表對應雜湊表。關鍵字和函式法則理論上可以任意確定。