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

            




            






            

				

            


    
    







            
	   
	



精品免费久久久久久久|
久久无码中文字幕东京热|
久久久久免费看成人影片|
久久婷婷人人澡人人爽人人爱|
欧美麻豆久久久久久中文|
久久国产福利免费|
久久婷婷五月综合色99啪ak|
久久激情五月丁香伊人|
久久午夜综合久久|
久久久久久曰本AV免费免费|
亚洲婷婷国产精品电影人久久|
久久SE精品一区二区|
久久久亚洲AV波多野结衣|
久久久噜噜噜久久熟女AA片|
69SEX久久精品国产麻豆|
亚洲综合精品香蕉久久网97|
久久最新免费视频|
久久久久久久精品妇女99|
97久久精品人妻人人搡人人玩|
91久久成人免费|
久久午夜夜伦鲁鲁片免费无码影视|
亚洲第一极品精品无码久久|
久久99中文字幕久久|
久久福利片|
久久亚洲精品中文字幕|
国产午夜精品久久久久九九电影|
亚洲欧美日韩精品久久亚洲区|
久久久国产精品亚洲一区|
91性高湖久久久久|
亚洲AV无码久久精品色欲|
国产精品99久久久久久www|
国产精品中文久久久久久久|
国产精品久久永久免费|
久久久久久国产a免费观看黄色大片|
欧洲成人午夜精品无码区久久|
国产精品成人99久久久久91gav|
午夜精品久久久久|
伊人色综合久久天天|
青草国产精品久久久久久|
久久人人爽人爽人人爽av
|
99久久精品国内|