• <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 閱讀(1332) 評論(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
                    這個可以去掉啊.....  回復  更多評論
				  
			
            
		

            




            






            

				

            


    
    







            
	   
	



久久er国产精品免费观看2|
久久久久久极精品久久久|
久久久久久国产a免费观看黄色大片
|
久久精品这里热有精品|
中文精品99久久国产|
天天爽天天狠久久久综合麻豆|
91精品国产综合久久香蕉|
怡红院日本一道日本久久
|
秋霞久久国产精品电影院|
久久国产精品免费一区|
无码人妻久久一区二区三区免费
|
思思久久99热只有频精品66|
国产亚洲综合久久系列|
一本久道久久综合狠狠躁AV|
国产精品久久精品|
无码任你躁久久久久久久|
99久久国语露脸精品国产|
亚洲国产成人久久综合区|
99久久精品免费看国产|
国产精品久久国产精麻豆99网站
|
国产69精品久久久久9999|
77777亚洲午夜久久多喷|
国产精品久久久久一区二区三区
|
国产精品久久久久久搜索|
亚洲国产精品高清久久久|
亚洲国产日韩综合久久精品|
精品人妻伦九区久久AAA片69|
久久精品国产网红主播|
色综合久久中文字幕无码|
久久精品国产男包|
国产精品亚洲综合久久|
亚洲欧洲精品成人久久曰影片|
久久精品国产亚洲一区二区三区|
日本道色综合久久影院|
蜜桃麻豆www久久|
久久99亚洲综合精品首页|
国产日韩欧美久久|
九九久久精品国产|
亚洲伊人久久成综合人影院
|
人妻无码αv中文字幕久久琪琪布
人妻无码久久一区二区三区免费
人妻无码中文久久久久专区
|
久久无码高潮喷水|