用鏈表和數組實現HASH表，幾種碰撞沖突解決方法

?

?

　　Hash算法中要解決一個碰撞沖突的辦法，后文中描述了幾種解決方法。下面代碼中用的是鏈式地址法，就是用鏈表和數組實現HASH表。

he/*hash table max size*/
#define HASH_TABLE_MAX_SIZE 40/*hash table大小*/
int hash_table_size=0;/*.BH-----------------------------------------------------------------
**                 結構體定義
**.EH-----------------------------------------------------------------
*/
/*hashTable結構*/
typedef int HashKeyType;
typedef struct{     OMS_TYPE__CurrFaultReport curr_fault_report;unsigned int begin_time[SYS_FAULT_REPORT_MAX_NUM];unsigned int end_time[SYS_FAULT_REPORT_MAX_NUM];unsigned int report_valid[SYS_FAULT_REPORT_MAX_NUM];
}HashValueType;typedef struct HashNode_Struct HashNode;
struct HashNode_Struct
{HashKeyType sKey;HashValueType nValue;HashNode* pNext;
};
HashNode* hashTable[HASH_TABLE_MAX_SIZE]; //hash table data strcutrue/*=================hash table function======================*/
/*.BH-----------------------------------------------------------------
**
**函數名：
**
**功能：string hash function
**
**參數： 無
**
**返回值：無
**
**設計注記：
**
**.EH-----------------------------------------------------------------
*/
unsigned int hash_table_hash_str(const char* skey)
{const signed char *p = (const signed char*)skey;unsigned int h = *p;if(h){for(p += 1; *p != '\0'; ++p){h = (h << 5) - h + *p;}}return h;
}/*.BH-----------------------------------------------------------------
**
**函數名：
**
**功能：insert key-value into hash table
**
**參數： 無
**
**返回值：無
**
**設計注記：
**
**.EH-----------------------------------------------------------------
*/
int hash_table_insert(const HashKeyType skey, HashValueType nvalue)
{unsigned int pos = 0;HashNode* pHead = NULL;HashNode* pNewNode = NULL;if (hash_table_size >= HASH_TABLE_MAX_SIZE){printf("out of hash table memory!\n");return 0;}pos = hash_table_hash_str(skey) % HASH_TABLE_MAX_SIZE;pHead = hashTable[pos];while (pHead){if (pHead->sKey == skey){printf("hash_table_insert: key %d already exists!\n", skey);return 0;}pHead = pHead->pNext;}pNewNode = (HashNode*)malloc(sizeof(HashNode));memset(pNewNode, 0, sizeof(HashNode));pNewNode->sKey = skey;memcpy(&pNewNode->nValue, &nvalue, sizeof(HashValueType));pNewNode->pNext = hashTable[pos];hashTable[pos] = pNewNode;hash_table_size++;return 1;
}/*.BH-----------------------------------------------------------------
**
**函數名：
**
**功能：lookup a key in the hash table
**
**參數： 無
**
**返回值：無
**
**設計注記：
**
**.EH-----------------------------------------------------------------
*/
HashNode* hash_table_find(const HashKeyType skey)
{unsigned int pos = 0;pos = hash_table_hash_str(skey) % HASH_TABLE_MAX_SIZE;if (hashTable[pos]){HashNode* pHead = hashTable[pos];while (pHead){if (skey == pHead->sKey)return pHead;pHead = pHead->pNext;}}return NULL;
}/*.BH-----------------------------------------------------------------
**
**函數名：
**
**功能：free the memory of the hash table
**
**參數： 無
**
**返回值：無
**
**設計注記：
**
**.EH-----------------------------------------------------------------
*/
void hash_table_release()
{int i;for (i = 0; i < HASH_TABLE_MAX_SIZE; ++i){if (hashTable[i]){HashNode* pHead = hashTable[i];while (pHead){HashNode* pTemp = pHead;pHead = pHead->pNext;if (pTemp){free(pTemp);}}}}
}//remove key-value frome the hash table
/*.BH-----------------------------------------------------------------
**
**函數名：
**
**功能：string hash function
**
**參數： 無
**
**返回值：無
**
**設計注記：
**
**.EH-----------------------------------------------------------------
*/
void hash_table_remove(const HashKeyType skey)
{unsigned int pos = hash_table_hash_str(skey) % HASH_TABLE_MAX_SIZE;if (hashTable[pos]){HashNode* pHead = hashTable[pos];HashNode* pLast = NULL;HashNode* pRemove = NULL;while (pHead){if (skey == pHead->sKey){pRemove = pHead;break;}pLast = pHead;pHead = pHead->pNext;}if (pRemove){if (pLast)pLast->pNext = pRemove->pNext;elsehashTable[pos] = NULL;free(pRemove);}}hash_table_size--;
}/*.BH-----------------------------------------------------------------
**
**函數名：
**
**功能：print the content in the hash table
**
**參數： 無
**
**返回值：無
**
**設計注記：
**
**.EH-----------------------------------------------------------------
*/
void hash_table_print()
{int i;printf("===========content of hash table===========\n");for (i = 0; i < HASH_TABLE_MAX_SIZE; ++i){if (hashTable[i]){HashNode* pHead = hashTable[i];printf("%d=>", i);while (pHead){printf("%d:%d  ", pHead->sKey, pHead->nValue.begin_time);pHead = pHead->pNext;}printf("\n");}}
}/*.BH-----------------------------------------------------------------
**
**函數名：
**
**功能：初始化系統名稱的hashTable，插入所有系統名稱
**
**參數： 無
**
**返回值：無
**
**設計注記：
**
**.EH-----------------------------------------------------------------
*/
void Common_InitHashTable()
{hash_table_size = 0;memset(hashTable, 0, sizeof(HashNode*) * HASH_TABLE_MAX_SIZE);
}

?

Hash碰撞沖突

Hash函數的作用就是保證對象返回唯一hash值，但當兩個對象計算值一樣時，這就發生了碰撞沖突。如下將介紹如何處理沖突，當然其前提是一致性hash。

1.開放地址法

開放地執法有一個公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)
其中，m為哈希表的表長。di 是產生沖突的時候的增量序列。如果di值可能為1,2,3,…m-1，稱線性探測再散列。
如果di取1，則每次沖突之后，向后移動1個位置.如果di取值可能為1,-1,2,-2,4,-4,9,-9,16,-16,…k*k,-k*k(k<=m/2)，稱二次探測再散列。
如果di取值可能為偽隨機數列。稱偽隨機探測再散列。

2.再哈希法

當發生沖突時，使用第二個、第三個、哈希函數計算地址，直到無沖突時。缺點：計算時間增加。
比如上面第一次按照姓首字母進行哈希，如果產生沖突可以按照姓字母首字母第二位進行哈希，再沖突，第三位，直到不沖突為止

3.鏈地址法（拉鏈法）

將所有關鍵字為同義詞的記錄存儲在同一線性鏈表中。如下：

因此這種方法，可以近似的認為是筒子里面套筒子

4.建立一個公共溢出區

假設哈希函數的值域為[0,m-1],則設向量HashTable[0..m-1]為基本表，另外設立存儲空間向量OverTable[0..v]用以存儲發生沖突的記錄。

優缺點：

優點：

①拉鏈法處理沖突簡單，且無堆積現象，即非同義詞決不會發生沖突，因此平均查找長度較短；
②由于拉鏈法中各鏈表上的結點空間是動態申請的，故它更適合于造表前無法確定表長的情況；
③開放定址法為減少沖突，要求裝填因子α較小，故當結點規模較大時會浪費很多空間。而拉鏈法中可取α≥1，且結點較大時，拉鏈法中增加的指針域可忽略不計，因此節省空間；
④在用拉鏈法構造的散列表中，刪除結點的操作易于實現。只要簡單地刪去鏈表上相應的結點即可。而對開放地址法構造的散列表，刪除結點不能簡單地將被刪結 點的空間置為空，否則將截斷在它之后填人散列表的同義詞結點的查找路徑。這是因為各種開放地址法中，空地址單元(即開放地址)都是查找失敗的條件。因此在 用開放地址法處理沖突的散列表上執行刪除操作，只能在被刪結點上做刪除標記，而不能真正刪除結點。

缺點：

指針需要額外的空間，故當結點規模較小時，開放定址法較為節省空間，而若將節省的指針空間用來擴大散列表的規模，可使裝填因子變小，這又減少了開放定址法中的沖突，從而提高平均查找速度。

?

開放地址法和拉鏈法是比較常用的兩種，各有優缺點，開放地址法的過程可以參考以下鏈接。

參考鏈接：HASH碰撞