1.散列表
Hash表是一種支持高效的查找纯续，插入，刪除操作的數(shù)據(jù)結(jié)構(gòu)，高效的設(shè)計(jì)目標(biāo)是時(shí)間復(fù)雜度為O（1）
概念：
1. 散列函數(shù)：數(shù)據(jù)元素的關(guān)鍵字和該元素的存儲(chǔ)位置之間的對(duì)應(yīng)關(guān)系箍土。
由散列函數(shù)覺(jué)得存儲(chǔ)位置的存儲(chǔ)結(jié)構(gòu)稱為散列表。
實(shí)質(zhì)：關(guān)鍵字集合到地址集合到映射井辆。
2. 沖突： 多個(gè)關(guān)鍵字 映射到 同一個(gè)存儲(chǔ)位置借跪；
構(gòu)造散列表的關(guān)鍵：如何減少?zèng)_突 以及 如何有效處理沖突
2.散列函數(shù)
好的散列函數(shù)的標(biāo)準(zhǔn)： 使散列地址均勻的分布在散列表中，盡量避免或減少?zèng)_突愧薛。
常用散列函數(shù)：
1. 直接定址法晨炕；
2. 除數(shù)取余法；
3. 平方取中法毫炉；
4. 折疊法：把關(guān)鍵字拆成幾部分瓮栗，按照某種約定把這幾部分組合在一起；
3.沖突處理
1. 開(kāi)放定址法:
設(shè)計(jì)一個(gè)關(guān)鍵字key瞄勾，散列地址為i=hash(k),若散列表中i的位置已經(jīng)存儲(chǔ)元素费奸，則產(chǎn)生沖突，探測(cè)下一個(gè)i＋1位置是否為空进陡，若空货邓，則存儲(chǔ)該元素；否則繼續(xù)探測(cè)下一個(gè)位置i＋2四濒，以此類推换况，直到找到一個(gè)空的位置。
缺點(diǎn)：使非同義詞也產(chǎn)生沖突盗蟆，并堆積在散列表的一段區(qū)域戈二，極速降低查找效率。
2. 鏈址法
3. 線性探測(cè)再散列法
4. 二次線性再散列喳资；
參考博客：
淺談算法和數(shù)據(jù)結(jié)構(gòu): 十一 哈希表 http://www.cnblogs.com/yangecnu/p/Introduce-Hashtable.html
