哈希加密算法在軟件開發(fā)和Linux內(nèi)核中多次被使用，由此可以見哈希加密算法的實(shí)用性和重要性。下面就給大家簡單介紹一下哈希算法的原理和應(yīng)用，并給出了簡略的代碼實(shí)現(xiàn)，以便大家學(xué)習(xí)。

1.哈希加密的概念

哈希(hash 散列，音譯為哈希)算法將任意長度的二進(jìn)制值映射為固定長度的較小二進(jìn)制值，這個(gè)小的二進(jìn)制值稱為哈希值。

哈希值是一段數(shù)據(jù)唯一且極其緊湊的數(shù)值表示形式。如果散列一段明文而且哪怕只更改該段落的一個(gè)字母，隨后的哈希算法都將產(chǎn)生不同的值。要找到散列為同一個(gè)值的兩個(gè)不同的輸入，在計(jì)算上是不可能的，所以數(shù)據(jù)的哈希值可以檢驗(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ù) ，并且將其放到適當(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 ];

return hashVal % tableSize;

}

通過對(duì)ASCII碼總和取tableSize的余數(shù)，來確定哈希值。

這是個(gè)簡單的示例，實(shí)現(xiàn)起來很簡單而且能夠很快地算出答案。不過，如果表很大，則函數(shù)不會(huì)很好地分配鍵。由于ASCII字符的值最多為127，如果輸入的key，都是長度比較小的字符串，那么返回的鍵值（哈希值）就會(huì)集中在哈希表的頭部，這樣就會(huì)分配不均勻。好的哈希算法這部分會(huì)非常復(fù)雜，這里僅僅做個(gè)介紹。在下面的哈希算法應(yīng)用中會(huì)介紹linux內(nèi)核如何使用哈希算法管理網(wǎng)絡(luò)設(shè)備結(jié)構(gòu)。

3.沖突的解決辦法

在使用哈希算法時(shí)，除了哈希函數(shù)之外，還需要注意的是沖突（兩個(gè)鍵散列到同一個(gè)值的時(shí)候）的處理。

常用的處理方式有分離鏈接法、線性探測(cè)、平方探測(cè)。由于線性探測(cè)和平方探測(cè)涉及到一些數(shù)學(xué)問題，本文就介紹分離鏈接法。

分離鏈接法也比較簡單，其做法為將散列到同一個(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í)需要逐一比較，效率低下。

admin

收藏 海報(bào)分享