溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細講解有關c語言中哈希表的示例分析，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。
??當我們在一個 鏈表 或者 順序表 中 查找 一個數(shù)據(jù)元素 是否存在 的時候，唯一的方法就是遍歷整個表，這種方法稱為 線性枚舉。
??如果這時候，順序表是有序的情況下，我們可以采用折半的方式去查找，這種方法稱為 二分枚舉。
??線性枚舉 的時間復雜度為 O ( n ) O(n) O(n)。二分枚舉 的時間復雜度為 O(log2n)。是否存在更快速的查找方式呢？這就是本要介紹的一種新的數(shù)據(jù)結構 —— 哈希表。
??由于它不是順序結構，所以很多數(shù)據(jù)結構書上稱之為 散列表，下文會統(tǒng)一采用 哈希表 的形式來說明，作為讀者，只需要知道這兩者是同一種數(shù)據(jù)結構即可。
??我們把需要查找的數(shù)據(jù)，通過一個 函數(shù)映射，找到 存儲數(shù)據(jù)的位置 的過程稱為 哈希。這里涉及到幾個概念：
??a）需要 查找的數(shù)據(jù) 本身被稱為 關鍵字；
??b）通過 函數(shù)映射 將 關鍵字 變成一個 哈希值 的過程中，這里的 函數(shù) 被稱為 哈希函數(shù)；
??c）生成 哈希值 的過程過程可能產(chǎn)生沖突，需要進行 沖突解決；
??d）解決完沖突以后，實際 存儲數(shù)據(jù)的位置 被稱為 哈希地址，通俗的說，它就是一個數(shù)組下標；
??e）存儲所有這些數(shù)據(jù)的數(shù)據(jù)結構就是 哈希表，程序實現(xiàn)上一般采用數(shù)組實現(xiàn)，所以又叫 哈希數(shù)組。整個過程如下圖所示：
??為了方便下標索引，哈希表 的底層實現(xiàn)結構是一個數(shù)組，數(shù)組類型可以是任意類型，每個位置被稱為一個槽。如下圖所示，它代表的是一個長度為 8 的 哈希表，又叫 哈希數(shù)組。
??關鍵字 是哈希數(shù)組中的元素，可以是任意類型的，它可以是整型、浮點型、字符型、字符串，甚至是結構體或者類。如下的 A、C、M 都可以是關鍵字；
int A = 5;
char C[100] = "Hello World!";
struct Obj { };
Obj M;??哈希表的實現(xiàn)過程中，我們需要通過一些手段，將一個非整型的 關鍵字 轉換成 數(shù)組下標，也就是 哈希值，從而通過O(1) 的時間快速索引到它所對應的位置。
??而將一個非整型的 關鍵字 轉換成 整型 的手段就是 哈希函數(shù)。
??哈希函數(shù)可以簡單的理解為就是小學課本上那個函數(shù)，即
y = f ( x )
，這里的 f(x) 就是哈希函數(shù)，x是關鍵字，y是哈希值。好的哈希函數(shù)應該具備以下兩個特質：
??a）單射；
??b）雪崩效應：輸入值x的 1比特的變化，能夠造成輸出值y至少一半比特的變化；
??單射很容易理解，圖 ( a ) (a) (a) 中已知哈希值 y 時，鍵 x 可能有兩種情況，不是一個單射；而圖 (b) 中已知哈希值 y時，鍵 x 一定是唯一確定的，所以它是單射。由于 x 和 y 一一對應，這樣就從本原上減少了沖突。
??
雪崩效應是為了讓哈希值更加符合隨機分布的原則，哈希表中的鍵分布的越隨機，利用率越高，效率也越高。
??常用的哈希函數(shù)有：直接定址法、除留余數(shù)法、數(shù)字分析法、平方取中法、折疊法、隨機數(shù)法 等等。有關哈希函數(shù)的內容，下文會進行詳細講解。
??哈希函數(shù)在生成 哈希值 的過程中，如果產(chǎn)生 不同的關鍵字得到相同的哈希值 的情況，就被稱為 哈希沖突。
??即對于哈希函數(shù)y=f(x)，當關鍵字 x1≠x2 ，但是卻有f(x1)=f(x2)，這時候，我們需要進行沖突解決。
??沖突解決方法有很多，主要有：開放定址法、再散列函數(shù)法、鏈地址法、公共溢出區(qū)法 等等。有關解決沖突的內容，下文會進行詳細講解。
??哈希地址 就是一個 數(shù)組下標 ，即哈希數(shù)組的下標。通過下標獲得數(shù)據(jù)，被稱為 索引。通過數(shù)據(jù)獲得下標，被稱為 哈希。平時工作的時候，和同事交流時用到的一個詞 反查 就是說的 哈希。
??直接定址法 就是 關鍵字 本身就是 哈希值，表示成函數(shù)值就是
f(x)=x
??例如，我們需要統(tǒng)計一個字符串中每個字符的出現(xiàn)次數(shù)，就可以通過這種方法。任何一個字符的范圍都是 [0,255]，所以只要用一個長度為 256 的哈希數(shù)組就可以存儲每個字符對應的出現(xiàn)次數(shù)，利用一次遍歷枚舉就可以解決這個問題。C代碼實現(xiàn)如下：
int i, hash[256];
for(i = 0; str[i]; ++i) {
++hash[ str[i] ];
}??這個就是最基礎的直接定址法的實現(xiàn)。hash[c]代表字符c在這個字符串str中的出現(xiàn)次數(shù)。
??平方取中法 就是對 關鍵字 進行平方，再取中間的某幾位作為 哈希值。
??例如，對于關鍵字 1314，得到平方為1726596，取中間三位作為哈希值，即265。
??平方取中法 比較適用于 不清楚關鍵字的分布，且位數(shù)也不是很大 的情況。
??折疊法 是將關鍵字分割成位數(shù)相等的幾部分（注意最后一部分位數(shù)不夠可以短一些），然后再進行求和，得到一個 哈希值。
??例如，對于關鍵字 5201314，將它分為四組，并且相加得到：52+01+31+4=88，這就是哈希值。
??折疊法 比較適用于 不清楚關鍵字的分布，但是關鍵字位數(shù)較多 的情況。
??除留余數(shù)法 就是 關鍵字 模上 哈希表 長度，表示成函數(shù)值就是
f(x)=x mod m
??其中 m 代表了哈希表的長度，這種方法，不僅可以對關鍵字直接取模，也可以在 平方取中法、折疊法 之后再取模。
??例如，對于一個長度為 4 的哈希數(shù)組，我們可以將關鍵字 模 4 得到哈希值，如圖所示：
??哈希數(shù)組的長度一般選擇 2 的冪，因為我們知道取模運算是比較耗時的，而位運算相對較為高效。
??選擇 2 的冪作為數(shù)組長度，可以將 取模運算 轉換成 二進制位與。
??令 m = 2^k，那么它的二進制表示就是：
，任何一個數(shù)模上 m，就相當于取了 m 的二進制低 k 位，而
，所以和 位與m?1 的效果是一樣的。即：
??除了直接定址法，其它三種方法都有可能導致哈希沖突，接下來，我們就來討論下常用的一些哈希沖突的解決方案。
??開放定址法 就是一旦發(fā)生沖突，就去尋找下一個空的地址，只要哈希表足夠大，總能找到一個空的位置，并且記錄下來作為它的 哈希地址。公式如下：
??這里的di 是一個數(shù)列，可以是常數(shù)列(1,1,1,...,1)，也可以是等差數(shù)列(1,2,3,...,m?1)。
??上圖中，采用的是哈希函數(shù)算法是 除留余數(shù)法，采用的哈希沖突解決方案是 開放定址法，哈希表的每個數(shù)據(jù)就是一個關鍵字，插入之前需要先進行查找，如果找到的位置未被插入，則執(zhí)行插入；否則，找到下一個未被插入的位置進行插入；總共插入了 6 個數(shù)據(jù)，分別為：11、12、13、20、19、28。
??這種方法需要注意的是，當插入數(shù)據(jù)超過哈希表長度時，不能再執(zhí)行插入。
??本文在第四章講解 哈希表的現(xiàn)實 時采用的就是常數(shù)列的開放定址法。
??再散列函數(shù)法 就是一旦發(fā)生沖突，就采用另一個哈希函數(shù)，可以是 平方取中法、折疊法、除留余數(shù)法 等等的組合，一般用兩個哈希函數(shù)，產(chǎn)生沖突的概率已經(jīng)微乎其微了。
??再散列函數(shù)法 能夠使關鍵字不產(chǎn)生聚集，當然，也會增加不少哈希函數(shù)的計算時間。
待補充
??當然，產(chǎn)生沖突后，我們也可以選擇不換位置，還是在原來的位置，只是把 哈希值 相同的用鏈表串聯(lián)起來。這種方法被稱為 鏈地址法。
??上圖中，采用的是哈希函數(shù)算法是 除留余數(shù)法，采用的哈希沖突解決方案是 鏈地址法，哈希表的每個數(shù)據(jù)保留了一個 鏈表頭結點 和 尾結點，插入之前需要先進行查找，如果找到的位置，鏈表非空，則插入尾結點并且更新尾結點；否則，生成一個新的鏈表頭結點和尾結點；總共插入了 6 個數(shù)據(jù)，分別為：11、12、13、20、19、28。
??一旦產(chǎn)生沖突的數(shù)據(jù)，統(tǒng)一放到另外一個順序表中，每次查找數(shù)據(jù)，在哈希數(shù)組中到的關鍵字和給定關鍵字相等，則認為查找成功；否則，就去公共溢出區(qū)順序查找，這種方法被稱為 公共溢出區(qū)法。
??這種方法適合沖突較少的情況。
待補充
??由于哈希表的底層存儲還是數(shù)組，所以我們可以定義一個結構體，結構體中定義一個數(shù)組類型的成員，如果需要記錄哈希表元素的個數(shù)，還可以記錄一個 size字段。
??C語言實現(xiàn)如下：
#define maxn (1<<17) // (1)
#define mask (maxn-1) // (2)
#define DataType int // (3)
#define Boolean int // (4)
#define NULLKEY (maxn+2) // (5)
typedef struct {
DataType data[maxn];
}HashTable;(1) 利用位運算計算哈希函數(shù)進行加速，哈希表的長度為 2 的冪；
(2) 利用上文提到的 位與法 作為哈希函數(shù)，進行位與的掩碼必須是二進制表示都是1的，所以等于 2 的冪減一；
(3) 定義關鍵字類型為整型int；
(4) 定義一個布爾變量類型；
(5) NULLKEY作為哈希表對應位置為空時的標記，必須是一個非關鍵字能取到的值；
??哈希表初始化要做的事情，就是把哈希表的每個位置都置空。C語言代碼實現(xiàn)如下：
void HashInit(HashTable *ht) {
int i;
for(i = 0; i < maxn; ++i) {
ht->data[i] = NULLKEY; // (1)
}
}(1) 將哈希表的每個位置都置空；
??哈希函數(shù)計算采用 除留余數(shù)法 的優(yōu)化版本 位與法。C語言代碼實現(xiàn)如下：
int HashGetAddr(DataType key) {
return key & mask;
}??查找需要采用和插入時相同的哈希沖突方案，即開放尋址法。C語言代碼實現(xiàn)如下：
Boolean HashSearchKey(HashTable *ht, DataType key, int *addr) {
int startaddr = HashGetAddr(key); // (1)
*addr = startaddr; // (2)
while(ht->data[*addr] != key) { // (3)
*addr = HashGetAddr(*addr + 1); // (4)
if(ht->data[*addr] == NULLKEY) // (5)
return 0;
if(*addr == startaddr) // (6)
return 0;
}
return 1; // (7)
}(1) 根據(jù) 哈希函數(shù)HashGetAddr計算得到一個哈希值startaddr；
(2) addr是需要作為返回值的，所以要用解引用；
(3) 在哈希表的addr對應查找，如果不是空位，則繼續(xù)(4)；否則，跳出循環(huán)；
(4) 往后找一個位置；
(5) 如果發(fā)現(xiàn)一個空位，說明這個關鍵字在哈希表中沒有對應數(shù)據(jù)，直接返回 0，代表查找失敗；
(6) 代表整個 哈希表 都已經(jīng)遍歷完畢，都沒有找到合適的關鍵字，直接返回 0，代表查找失?。?/p>
(7) 否則，返回 1 代表查找成功；
??哈希沖突時（即當沒有合適位置），就找下一相鄰位置，即尋址數(shù)列為常數(shù)列 (1,1,1,...,1)。插入需要注意當哈希表慢時，不能再執(zhí)行插入操作。C語言代碼實現(xiàn)如下：
int HashInsert(HashTable *ht, DataType key) {
int addr = HashGetAddr(key); // (1)
int retaddr;
if ( HashSearchKey(ht, key, &retaddr ) ) { // (2)
return retaddr;
}
while(ht->data[addr] != NULLKEY) // (3)
addr = HashGetAddr(addr + 1); // (4)
ht->data[addr] = key; // (5)
return addr; // (6)
} (1) 根據(jù) 哈希函數(shù)HashGetAddr計算得到一個哈希值addr；
(2) 插入前需要先查找是否存在，如果已經(jīng)存在，則不執(zhí)行插入；
(3) 在哈希表的addr對應查找，如果不是空位，則繼續(xù) (3)；否則，跳出循環(huán)；
(4) 往后找一個位置，繼續(xù)判斷是否為空；
(5) 跳出循環(huán)則代表當前哈希表的addr位置沒有其它元素占據(jù)，則可以作為當前key的位置進行插入；
(6) 返回addr作為key的哈希地址；
??有了查找的基礎，刪除操作就比較簡單了，如果不能找到一個關鍵字的位置，則不對哈希表進行任何操作，返回空關鍵字；否則，將找到的位置賦為空關鍵字，并且返回刪除的位置；
int HashRemove(HashTable *ht, DataType key) {
int addr;
if ( !HashSearchKey(ht, key, &addr ) ) { // (1)
return NULLKEY;
}
ht->data[addr] = NULLKEY; // (2)
return addr;
}(1) 首先執(zhí)行查找；
(2) 對找到的位置，將找到位置關鍵字清空；
??最后，給出一個 開放定址法 的哈希表的完整實現(xiàn)，如下：
/******************** 哈希表 開放定址法 ********************/
#define maxn (1<<17)
#define mask (maxn-1)
#define DataType int
#define Boolean int
#define NULLKEY (1<<30)
typedef struct {
DataType data[maxn];
}HashTable;
void HashInit(HashTable *ht) {
int i;
for(i = 0; i < maxn; ++i) {
ht->data[i] = NULLKEY;
}
}
int HashGetAddr(DataType key) {
return key & mask;
}
Boolean HashSearchKey(HashTable *ht, DataType key, int *addr) {
int startaddr = HashGetAddr(key);
*addr = startaddr;
while(ht->data[*addr] != key) {
*addr = HashGetAddr(*addr + 1);
if(ht->data[*addr] == NULLKEY) {
return 0;
}
if(*addr == startaddr) {
return 0;
}
}
return 1;
}
int HashInsert(HashTable *ht, DataType key) {
int addr = HashGetAddr(key);
int retaddr;
if ( HashSearchKey(ht, key, &retaddr ) ) {
return retaddr;
}
while(ht->data[addr] != NULLKEY)
addr = HashGetAddr(addr + 1);
ht->data[addr] = key;
return addr;
}
int HashRemove(HashTable *ht, DataType key) {
int addr;
if ( !HashSearchKey(ht, key, &addr ) ) {
return NULLKEY;
}
ht->data[addr] = NULLKEY;
return addr;
}
/******************** 哈希表 開放定址法 ********************/關于“c語言中哈希表的示例分析”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。
免責聲明：本站發(fā)布的內容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權內容。
