哈希表的原理：
在已知key的情況下抢呆，通過哈希函數(shù)f(),在數(shù)組中去尋找具體的值f(key)睦尽。
這里面f()稱為哈希函數(shù)或者散列函數(shù)铁材。
f(key)就是記錄的存儲(chǔ)位置宇攻。
通過散列計(jì)數(shù)將記錄存儲(chǔ)在一塊連續(xù)的存儲(chǔ)空間中惫叛，這塊存儲(chǔ)空間就是哈希表。
把key通過哈希函數(shù)轉(zhuǎn)換成一個(gè)整型數(shù)字逞刷，然后將該數(shù)字對(duì)數(shù)組長(zhǎng)度進(jìn)行取余嘉涌，取余結(jié)果當(dāng)做數(shù)組的下標(biāo)妻熊，把value存儲(chǔ)在數(shù)組該下標(biāo)所在的存儲(chǔ)空間中。
使用哈希表查詢的時(shí)候仑最， 將key通過哈希函數(shù)轉(zhuǎn)換成一個(gè)數(shù)字扔役，然后算出數(shù)組下標(biāo)，從而直接取出數(shù)組中的value值警医，充分利用了數(shù)組的快速定位功能亿胸。
比較好的哈希函數(shù)是time33算法。PHP的數(shù)組就是把這個(gè)作為哈希函數(shù)预皇。
unsigned long hash(const char* key){
unsigned long hash=0;
for(int i=0;i<strlen(key);i++){
hash = hash*33+str[i];
}
return hash;
}
哈希沖突：
當(dāng)兩個(gè)key值不同侈玄，但是通過哈希函數(shù)得到的數(shù)值是一樣的。此時(shí)就產(chǎn)生了哈希沖突吟温。
即 key1≠key2,但是f(key1)=f(key2)序仙。
數(shù)組的特點(diǎn)： 查詢?nèi)≈等菀祝遣迦雱h除費(fèi)勁
鏈表的特點(diǎn)：查詢?nèi)≈蒂M(fèi)勁鲁豪，插入刪除簡(jiǎn)單潘悼。
哈希表有多種表現(xiàn)形式，其中最常用的就是拉鏈法呈昔，就是將數(shù)組和鏈表的功能相結(jié)合挥等。
使用拉鏈法可以很好的去解決哈希沖突。 當(dāng)兩個(gè)不同的key獲取了同一個(gè)數(shù)組下標(biāo)堤尾，此時(shí)就在該數(shù)組存儲(chǔ)空間中加一個(gè)指針肝劲，指向一個(gè)鏈表，然后將value存放在鏈表中郭宝。
一個(gè)好的哈希表應(yīng)該滿足兩個(gè)特點(diǎn)：
1.盡量使關(guān)鍵字對(duì)應(yīng)的記錄均勻分布在哈希表中辞槐，這樣可以在查詢?nèi)我鈹?shù)值的時(shí)候都不會(huì)有過大的復(fù)雜度。（復(fù)雜度最高的一種哈希表就是粘室，只有一個(gè)鏈表榄檬，這樣哈希表就退化成了鏈表）
2.關(guān)鍵字極小的錯(cuò)誤引起哈希表極大的變化。
哈希表的用途：
1.哈希主要用于信息加密衔统，把一些不同長(zhǎng)度的信息轉(zhuǎn)化成雜亂的128位編碼鹿榜，這些編碼值叫做hash值。
2.用于查找：之前的查找是在一堆元素中取出一個(gè)元素锦爵，然后和目標(biāo)函數(shù)比對(duì)舱殿，不匹配縮小返回繼續(xù)。現(xiàn)在使用哈希表险掀，可以直接定位到相關(guān)內(nèi)存中沪袭，大大縮短了查找耗時(shí)。
哈希表的優(yōu)缺點(diǎn)：
優(yōu)點(diǎn)：運(yùn)行速度極快樟氢。
不考慮有序遍歷數(shù)據(jù)冈绊，并且可以提前知道數(shù)據(jù)的大小侠鳄。哈希表在速度和易用性上很牛逼。
缺點(diǎn)：它是基于數(shù)組的死宣，數(shù)據(jù)創(chuàng)建后很難擴(kuò)展伟恶，并且如果哈希表被填滿后性能會(huì)下降的很快。程序員需要知道這個(gè)表的內(nèi)存上限十电，這個(gè)很重要知押。并且需要定期將哈希表中的數(shù)據(jù)轉(zhuǎn)移到比較大內(nèi)存的表中叹螟，很費(fèi)時(shí)鹃骂。
