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

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

散列查找

常見的散列函數(shù)

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

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

查找操作

刪除操作

查找效率分析（ASL）

平方探測法

偽隨機(jī)序列法