隨感而發

雜七雜八

隨筆分類(62)

隨筆檔案(67)

統計

隨筆 - 67
文章 - 0
評論 - 132
引用 - 0

留言簿(13)

閱讀排行榜

評論排行榜

除法散列發解決碰撞的散列表

今天學習了除法散列法解決散列表的碰撞。他的基本思路為：
1. 用一個閥值作為除數，對要求散列值的key除以他，得到的結果就是該key要存放的位置。
2. 注意的是，這個除數一定要選擇好，不能太大，太大浪費了空間。也不能太小，太小碰撞太嚴重。一般選擇里2的p次冪最遠的質數。因為這樣的話散列的效果可能更好。具體論證我也不清楚。
3. 空間的選擇，只要除數定下來之后，一般空間就是除數這么大了。
4. 碰撞處理，萬一遇到碰撞怎么辦，我目前采用的是鏈表法處理碰撞，就是如果兩個key算出的值一樣。就把他們用鏈表的形式連接起來，然后再鏈接到他們的域中。這個最容易理解的方法了。
基本就這么多了，奉上源代碼：

#include <stdio.h>

#include <stdlib.h>

//定義保存數據的鏈表

struct stList

{

int nData; //數據的key，也作為數據

stList* pNext;

};

//散列表的域，保存時數據鏈表的指針

stList* g_data[702] = {0};

//計算關鍵字的散列值。

int HashFunc(int nKey)

{

//用除法散列法求散列值，他的一個思路是

//求余，但是除數一定要選好，書上說的最好于2的整數冪不太接近

//的質數。具體為什么書上有說明。

return nKey % 701;

}

//插入數據到散列表中

int InsertData(int nKey)

{

//就是選算出算列值，然后就是鏈表的插入了。

int nPos = HashFunc(nKey);

stList* pTemp = new stList();

pTemp->nData = nKey;

pTemp->pNext = g_data[nPos];

g_data[nPos] = pTemp;

return nPos;

}

int g_MaxFind = -1; //這個計算最大查找次數的，因為數據很特殊，所以沒有看到效果。

bool FindData(int nKey)

{

//也是先算出散列值，再對應值處做鏈表查找。

int nPos = HashFunc(nKey);

int i = 0;

stList* pTemp = g_data[nPos];

while(pTemp)

{

++i;

if (pTemp->nData == nKey)

{

if (g_MaxFind < i)

{

g_MaxFind = i;

}

return true;

}

pTemp = pTemp->pNext;

}

//增加了一個算出最大查找次數的比較。多余的。

if (g_MaxFind < i)

{

g_MaxFind = i;

}

return false;

}

int DeleteData(int nKey)

{

//先算出散列值，再對對應的區域做鏈表刪除

int nPos = HashFunc(nKey);

stList* pTemp = g_data[nPos];

stList* pPre = g_data[nPos];

while(pTemp)

{

if (pTemp->nData == nKey)

{

if (pTemp == g_data[nPos])

{

g_data[nPos] = pTemp->pNext;

}

else

{

pPre->pNext = pTemp->pNext;

}

delete pTemp;

return nPos;

}

pPre = pTemp;

pTemp = pTemp->pNext;

}

return -1;

}

int main()

{

//插入2000個數，因為太特殊了，所以效果很好。呵呵。

for (int i = 0; i < 2000; ++i)

{

InsertData(i);

}

//找這些數據。

for (int i = 0; i < 2; ++i)

{

if (FindData(i))

{

//printf("%d ", i);

}

else

{

printf("Wrong!\n");

}

//輸出最大查找次數，是3次，數據太特殊。所以不能說明什么

//這個結果是最好的，完全散列在散列表中。碰撞次數最少。

printf("%d ", g_MaxFind);

//刪除數據

for (int i = 0; i < 2000; ++i)

{

DeleteData(i);

}

//再次查找，跟定時找不到的啦。

for (int i = 0; i < 2000; ++i)

{

if (FindData(i))

{

printf("%d Wrong!\n", i);

}

system("pause");

return 0;

}

posted on 2009-05-06 20:19 shongbee2 閱讀(1354) 評論(2) 編輯收藏引用所屬分類: 數據結構和算法

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 除法散列發解決碰撞的散列表求2-nMax的素數用數組模擬指針和對象鏈表學習--雙向鏈表實現隊列學習--數組實現棧學習---數組實現尋找第i小元素求最大最小值排序算法總結希爾排序

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

# re: 除法散列發解決碰撞的散列表 2011-05-20 21:59 shongbee2

# re: 除法散列發解決碰撞的散列表[未登錄] 2011-10-12 23:41 方君君

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

隨感而發

導航

隨筆分類(62)

隨筆檔案(67)

統計

留言簿(13)

閱讀排行榜

評論排行榜

除法散列發解決碰撞的散列表

評論