哈希表和哈希函數是大學(xué)數據結構中的課程，實(shí)際開(kāi)發(fā)中我們經(jīng)常用到Hashtable這種結構，當遇到鍵-值對存儲，采用Hashtable比ArrayList查找的性能高。為什么呢？我們在享受高性能的同時(shí)，需要付出什么代價(jià)(這幾天看紅頂商人胡雪巖，經(jīng)典臺詞：在你享受這之前，必須受別人吃不了的苦，忍受別人受不了的屈辱)，那么使用Hashtable是否就是一樁無(wú)本萬(wàn)利的買(mǎi)賣(mài)呢？就此疑問(wèn)，做以下分析，希望能拋磚引玉。
1)hash它為什么對于鍵-值查找性能高
學(xué)過(guò)數據結構的，都應該曉得，線(xiàn)性表和樹(shù)中，記錄在結構中的相對位置是隨機的，記錄和關(guān)鍵字之間不存在明確的關(guān)系，因此在查找記錄的時(shí)候，需要進(jìn)行一系列的關(guān)鍵字比較，這種查找方式建立在比較的基礎之上，在.net中(Array,ArrayList,List)這些集合結構采用了上面的存儲方式。
比如，現在我們有一個(gè)班同學(xué)的數據，包括姓名，性別，年齡，學(xué)號等。假如數據有
| 姓名 | 性別 | 年齡 | 學(xué)號 |
| 張三 | 男 | 15 | 1 |
| 李四 | 女 | 14 | 2 |
| 王五 | 男 | 14 | 3 |
假如，我們按照姓名來(lái)查找，假設查找函數FindByName(string name);
1)查找“張三”
只需在第一行匹配一次。
2)查找"王五"
在第一行匹配，失敗，
在第二行匹配，失敗，
在第三行匹配，成功
上面兩種情況，分別分析了最好的情況，和最壞的情況，那么平均查找次數應該為 (1+3)/2=2次，即平均查找次數為(記錄總數+1)的1/2。
盡管有一些優(yōu)化的算法，可以使查找排序效率增高，但是復雜度會(huì )保持在log2n的范圍之內。
如何更更快的進(jìn)行查找呢？我們所期望的效果是一下子就定位到要找記錄的位置之上，這時(shí)候時(shí)間復雜度為1，查找最快。如果我們事先為每條記錄編一個(gè)序號，然后讓他們按號入位，我們又知道按照什么規則對這些記錄進(jìn)行編號的話(huà)，如果我們再次查找某個(gè)記錄的時(shí)候，只需要先通過(guò)規則計算出該記錄的編號，然后根據編號，在記錄的線(xiàn)性隊列中，就可以輕易的找到記錄了 。
注意，上述的描述包含了兩個(gè)概念，一個(gè)是用于對學(xué)生進(jìn)行編號的規則，在數據結構中，稱(chēng)之為哈希函數，另外一個(gè)是按照規則為學(xué)生排列的順序結構，稱(chēng)之為哈希表。
仍以上面的學(xué)生為例，假設學(xué)號就是規則，老師手上有一個(gè)規則表，在排座位的時(shí)候也按照這個(gè)規則來(lái)排序，查找李四，首先該教師會(huì )根據規則判斷出，李四的編號為2，就是在座位中的2號位置，直接走過(guò)去，“李四，哈哈，你小子，就是在這！”
看看大體流程:
| 0 | 1 | 2 | 3 | 4 | 5 |
| 0歲 | １歲 | ２歲 | ３歲 | ４歲 | ５歲 |
| 年 | 月 | 日 |
| ７５ | １０ | １ |
| ７５ | １２ | １０ |
| ７５ | ０２ | １４ |
分析一下，年和月的第一位數字基本相同，造成沖突的幾率非常大，而后面三位差別比較大，所以采用后三位
c)平方取中法
取關(guān)鍵字平方后的中間幾位作為哈希地址
d) 折疊法：
將關(guān)鍵字分割成位數相同的幾部分，最后一部分位數可以不相同，然后去這幾部分的疊加和（取出進(jìn)位）作為哈希地址，比如有這樣的數據20-1445-4547-3
可以
5473
+ 4454
+ 201
= 10128
取出進(jìn)位1,取0128為哈希地址
e)取余法
取關(guān)鍵字被某個(gè)不大于哈希表表長(cháng)m的數p除后所得余數為哈希地址。H(key)=key MOD p (p<=m)
f) 隨機數法
選擇一個(gè)隨機函數，取關(guān)鍵字的隨機函數值為它的哈希地址，即H(key)=random(key) ,其中random為隨機函數。通常用于關(guān)鍵字長(cháng)度不等時(shí)采用此法。
總之，哈希函數的規則是：通過(guò)某種轉換關(guān)系，使關(guān)鍵字適度的分散到指定大小的的順序結構中。越分散，則以后查找的時(shí)間復雜度越小，空間復雜度越高。
２)使用hash，我們付出了什么？
hash是一種典型以空間換時(shí)間的算法，比如原來(lái)一個(gè)長(cháng)度為100的數組，對其查找，只需要遍歷且匹配相應記錄即可，從空間復雜度上來(lái)看，假如數組存儲的是byte類(lèi)型數據，那么該數組占用100byte空間?，F在我們采用hash算法，我們前面說(shuō)的hash必須有一個(gè)規則，約束鍵與存儲位置的關(guān)系，那么就需要一個(gè)固定長(cháng)度的hash表，此時(shí)，仍然是100byte的數組，假設我們需要的100byte用來(lái)記錄鍵與位置的關(guān)系，那么總的空間為200byte,而且用于記錄規則的表大小會(huì )根據規則，大小可能是不定的，比如在lzw算法中，如果一個(gè)很長(cháng)的用于記錄像素的byte數組，用來(lái)記錄位置與鍵關(guān)系的表空間，算法推薦為一個(gè)1２bit能表述的整數大小，那么足夠長(cháng)的像素數組，如何分散到這樣定長(cháng)的表中呢，lzw算法采用的是可變長(cháng)編碼，具體會(huì )在深入介紹lzw算法的時(shí)候介紹。
注:hash表最突出的問(wèn)題在于沖突，就是兩個(gè)鍵值經(jīng)過(guò)哈希函數計算出來(lái)的索引位置很可能相同，這個(gè)問(wèn)題，下篇文章會(huì )令作闡述。
注:之所以會(huì )簡(jiǎn)單得介紹了hash，是為了更好的學(xué)習lzw算法，學(xué)習lzw算法是為了更好的研究gif文件結構，最后，我將詳細的闡述一下gif文件是如何構成的，如何高效操作此種類(lèi)型文件。
tplink：http://hi.baidu.com/gezhou/blog/item/a360baeff9c0f317fcfa3ce7.html
聯(lián)系客服
