• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        

            
	

            隨感而發
            

            雜七雜八
            

            


            
	
		

            統計
            
	
		

            留言簿(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 閱讀(1333) 評論(2)  編輯 收藏 引用  所屬分類: 數據結構和算法 
		
            
	
            
	
	


	


            
	    
    


            

            評論
            
	
	
			
            
				# re: 除法散列發解決碰撞的散列表
					
						2011-05-20 21:59
					
				shongbee2
			
            
			
            
				不就是hash的一種算法嘛，我還以為。。呵呵。。  回復  更多評論
				  
			
            
		
			
            
				# re: 除法散列發解決碰撞的散列表[未登錄]
					
						2011-10-12 23:41
					
				方君君
			
            
			
            
				       if (pTemp == g_data[nPos])
                      {
                            g_data[nPos] = pTemp->pNext;
                       }
                        else
                    這個可以去掉啊.....  回復  更多評論
				  
			
            
		

            




            






            

				

            


    
    







            
	   
	



青青青国产精品国产精品久久久久
|
久久综合精品国产一区二区三区|
久久精品国产只有精品2020|
AAA级久久久精品无码区|
久久久久这里只有精品|
日本人妻丰满熟妇久久久久久|
国产一久久香蕉国产线看观看|
久久亚洲中文字幕精品一区|
伊人色综合久久天天人手人婷|
亚洲国产精品久久久久久|
久久久久国产精品嫩草影院
|
久久久久国产精品嫩草影院|
九九久久自然熟的香蕉图片|
久久97久久97精品免视看秋霞
|
欧美久久一级内射wwwwww.|
亚洲综合熟女久久久30p|
久久久久国产一级毛片高清板|
久久精品无码一区二区WWW|
国产真实乱对白精彩久久|
亚洲国产精品无码成人片久久|
精品久久人人爽天天玩人人妻|
亚洲狠狠婷婷综合久久久久|
亚洲精品国产综合久久一线|
69国产成人综合久久精品|
亚洲女久久久噜噜噜熟女|
久久一区二区三区免费|
久久国产热这里只有精品|
久久99热精品|
亚洲AV无码久久精品狠狠爱浪潮
|
岛国搬运www久久|
成人免费网站久久久|
无码人妻久久一区二区三区免费
|
久久福利青草精品资源站|
人妻精品久久久久中文字幕69|
中文成人久久久久影院免费观看|
久久97久久97精品免视看|
亚洲精品高清久久|
国产精品VIDEOSSEX久久发布|
日本道色综合久久影院|
久久夜色精品国产亚洲|
国产精品伦理久久久久久|