列表（Hash Table），又稱哈希表，是一種數(shù)據(jù)結構，特點是：數(shù)據(jù)元素的關鍵字與其存儲地址直接相關
例：有一堆數(shù)據(jù)元素，關鍵字分別為｛19，14，23，1，68，20，84，27，55，11，10，79｝，散列函數(shù)H(key)=key%13
若不同的關鍵字通過散列函數(shù)映射到同一個值，則稱它們?yōu)椤巴x詞”
通過散列函數(shù)確定的位置已經(jīng)存放了其他元素，則稱這種情況為“沖突”

用拉鏈法（又稱鏈接法、鏈地址法）解決‘沖突’：把所有“同義詞”存儲在一個鏈表中

散列查找

常見的散列函數(shù)

設計目標–讓不同關鍵字的沖突盡可能地少
除留余數(shù)法—H(key)=key%p
散列表表長為m，取一個不大于m但最接近或等于m的質數(shù)p
質數(shù)又稱素數(shù)。指除了1和此整數(shù)自身外，不能被其他自然數(shù)整除的數(shù)

處理沖突的方法–開放定址法

查找操作

刪除操作

查找效率分析（ASL）

平方探測法

偽隨機序列法