概念：
哈希表(散列表)通過將關(guān)鍵碼key映射到表中的某個(gè)位置上來存儲元素，然后根據(jù)關(guān)鍵碼來訪問元素桩盲。
常用hash函數(shù)
- 除留余數(shù)法
- 線性探測
- 二次探測
- 開鏈法寂纪，在大部分情況下基本就是用開鏈法
解決方式
開放地址法
基本思想是：當(dāng)發(fā)生地址沖突時(shí)，按照某種方法繼續(xù)探測哈希表中的其他存儲單元赌结，直到找到空位置為止捞蛋。
如：線性探測再散列、二次探測再散列再哈希法
當(dāng)發(fā)生沖突時(shí)柬姚，使用第二個(gè)襟交、第三個(gè)、哈希函數(shù)計(jì)算地址伤靠，直到無沖突時(shí)捣域。缺點(diǎn)：計(jì)算時(shí)間增加啼染。比如上面第一次按照姓首字母進(jìn)行哈希，如果產(chǎn)生沖突可以按照姓字母首字母第二位進(jìn)行哈希焕梅，再沖突迹鹅，第三位，直到不沖突為止贞言。鏈地址法
將所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈表中斜棚。建立一個(gè)公共溢出區(qū)
假設(shè)哈希函數(shù)的值域?yàn)閇0,m-1],則設(shè)向量HashTable[0..m-1]為基本表，另外設(shè)立存儲空間向量OverTable[0..v]用以存儲發(fā)生沖突的記錄该窗。
