哈希算法介紹參考模板

1、哈希算法簡(jiǎn)介0 / 7目錄1哈希算法概念22哈希函數(shù)33沖突的解決方法34哈希算法應(yīng)用4關(guān)鍵詞：算法、哈希、c語言摘 要：哈希算法在軟件開發(fā)和Linux內(nèi)核中多次被使用，由此可以見哈希算法的實(shí)用性和重要性。本文介紹了哈希算法的原理和應(yīng)用，并給出了簡(jiǎn)略的代碼實(shí)現(xiàn)，以便讀者理解。1哈希算法概念哈希(hash 散列，音譯為哈希)算法將任意長(zhǎng)度的二進(jìn)制值映射為固定長(zhǎng)度的較小二進(jìn)制值，這個(gè)小的二進(jìn)制值稱為哈希值。哈希值是一段數(shù)據(jù)唯一且極其緊湊的數(shù)值表示形式。如果散列一段明文而且哪怕只更改該段落的一個(gè)字母，隨后的哈希算法都將產(chǎn)生不同的值。要找到散列為同一個(gè)值的兩個(gè)不同的輸入，在計(jì)算上是不可能的，所以數(shù)據(jù)的

2、哈希值可以檢驗(yàn)數(shù)據(jù)的完整性。哈希表是根據(jù)設(shè)定的哈希函數(shù)H(key)和處理沖突方法將一組關(guān)鍵字映象到一個(gè)有限的地址區(qū)間上，并以關(guān)鍵字在地址區(qū)間中的項(xiàng)作為記錄在表中的存儲(chǔ)位置，這種表稱為哈希表，所得存儲(chǔ)位置稱為哈希地址。作為線性數(shù)據(jù)結(jié)構(gòu)與表格和隊(duì)列等相比，哈希表無疑是查找速度比較快的一種。查找一般是對(duì)項(xiàng)的摸個(gè)部分（及數(shù)據(jù)成員）進(jìn)行，這部分稱為鍵（key）。例如，項(xiàng)可以由字符串作為鍵，附帶一些數(shù)據(jù)成員。 理想的哈希表數(shù)據(jù)結(jié)構(gòu)只不過是一個(gè)包含一些項(xiàng)的具有固定大小的數(shù)組。通常的習(xí)慣是讓項(xiàng)從0到 TableSize-1之間變化。將每個(gè)鍵映射到0到TableSize-1 這個(gè)范圍中的某個(gè)數(shù) ，并且將其放到適

3、當(dāng)?shù)膯卧?，這個(gè)映射就稱為散列函數(shù)（hash funciton）。如右圖，john被散列到3，phil被散列到4，dave 被散列到6，mary被散列到7.這是哈希的基本思想。剩下的問題則是要選擇一個(gè)函數(shù)，決定當(dāng)兩個(gè)鍵散列到同一個(gè)值的時(shí)候（稱為沖突），應(yīng)該做什么。2哈希函數(shù)通常，鍵是字符串，一種選擇方法是把字符串中字符ASCII碼值加起來。unsigned int hash( const char * key, int tableSize)unsigned int hastVal = 0;for( int i = 0; i strlen(key); i+)hashVal += key i ;r

4、eturn hashVal % tableSize;通過對(duì)ASCII碼總和取tableSize的余數(shù)，來確定哈希值。這是個(gè)簡(jiǎn)單的示例，實(shí)現(xiàn)起來很簡(jiǎn)單而且能夠很快地算出答案。不過，如果表很大，則函數(shù)不會(huì)很好地分配鍵。由于ASCII字符的值最多為127，如果輸入的key，都是長(zhǎng)度比較小的字符串，那么返回的鍵值（哈希值）就會(huì)集中在哈希表的頭部，這樣就會(huì)分配不均勻。好的哈希算法這部分會(huì)非常復(fù)雜，這里僅僅做個(gè)介紹。在下面的哈希算法應(yīng)用中會(huì)介紹linux內(nèi)核如何使用哈希算法管理網(wǎng)絡(luò)設(shè)備結(jié)構(gòu)。3沖突的解決方法在使用哈希算法時(shí)，除了哈希函數(shù)之外，還需要注意的是沖突（兩個(gè)鍵散列到同一個(gè)值的時(shí)候）的處理。常用的處

5、理方式有分離鏈接法、線性探測(cè)、平方探測(cè)。由于線性探測(cè)和平方探測(cè)涉及到一些數(shù)學(xué)問題，本文就介紹分離鏈接法。分離鏈接法也比較簡(jiǎn)單，其做法為將散列到同一個(gè)值的所有元素保留到一個(gè)鏈表中。如上圖所示，所有哈希表項(xiàng)對(duì)應(yīng)一個(gè)鏈表，這樣只要將沖突項(xiàng)放入鏈表就行，當(dāng)查找時(shí)先找到鏈表，然后在比較鏈表上項(xiàng)的鍵，得到想要的項(xiàng)，這個(gè)方法比較容易實(shí)現(xiàn)，但是會(huì)增加查找的耗時(shí)，原來只需計(jì)算哈希值，現(xiàn)在增加了對(duì)鏈表項(xiàng)的比較功能。4哈希算法應(yīng)用下面看看linux內(nèi)核中網(wǎng)絡(luò)設(shè)備，是怎么樣通過設(shè)備名獲取相應(yīng)設(shè)備的net_device結(jié)構(gòu)體。在這個(gè)過程中，使用了哈希算法，并且使用了分離鏈接法解決沖突的問題。使用哈希算法可以提高查詢速度，如果使用鏈表，查詢時(shí)需要逐一比較，效率低下。dev_name_head為哈希表，保存了所有項(xiàng)的鏈表頭。1 NETDEV_HASHBITS 為表的大小。full_name_hash為哈希函數(shù)，其主要目的是為了分布均勻避免沖突，這樣可以提高查找效率。 這個(gè)應(yīng)用