• <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>
            

    
            

            




            







												


        

            
	

            隨感而發(fā)
            

            雜七雜八
            

            


            
	
		

            統(tǒng)計(jì)
            
	
		

            留言簿(13)
            


        
		

        

            閱讀排行榜
            

            
	
			
		

            

		

            評(píng)論排行榜
            


	

            

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

            #include <stdio.h>
            #include             <stdlib.h>

            //定義保存數(shù)據(jù)的鏈表
            struct stList
            {
                            int nData;    //數(shù)據(jù)的key，也作為數(shù)據(jù)
                stList* pNext;
            }            ;

            //散列表的域，保存時(shí)數(shù)據(jù)鏈表的指針
            stList* g_data[702] = {0};

            //計(jì)算關(guān)鍵字的散列值。
            int HashFunc(int nKey)
            {
                            //用除法散列法求散列值，他的一個(gè)思路是
                            //求余，但是除數(shù)一定要選好，書上說的最好于2的整數(shù)冪不太接近
                            //的質(zhì)數(shù)。具體為什么書上有說明。
                return nKey % 701;
            }

            //插入數(shù)據(jù)到散列表中
            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;    //這個(gè)計(jì)算最大查找次數(shù)的，因?yàn)閿?shù)據(jù)很特殊，所以沒有看到效果。

            bool FindData(int nKey)
            {
                            //也是先算出散列值，再對應(yīng)值處做鏈表查找。
                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;
                }

                            //增加了一個(gè)算出最大查找次數(shù)的比較。多余的。
                if (g_MaxFind < i)
                            {
                    g_MaxFind             = i;
                }

                            return false;
            }

            int DeleteData(int nKey)
            {
                            //先算出散列值，再對對應(yīng)的區(qū)域做鏈表刪除
                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個(gè)數(shù)，因?yàn)樘厥饬耍孕Ч芎谩：呛恰?/span>
                for (int i = 0; i < 2000; ++i)
                            {
                    InsertData(i);
                }

                            //找這些數(shù)據(jù)。
                for (int i = 0; i < 2; ++i)
                            {
                                if (FindData(i))
                                {
                                    //printf("%d ", i);
                    }
                                else
                                {
                        printf(            "Wrong!\n");
                    }
                }

                            //輸出最大查找次數(shù)，是3次，數(shù)據(jù)太特殊。所以不能說明什么
                            //這個(gè)結(jié)果是最好的，完全散列在散列表中。碰撞次數(shù)最少。
                printf("%d ", g_MaxFind);

                            //刪除數(shù)據(jù)
                for (int i = 0; i < 2000; ++i)
                            {
                    DeleteData(i);
                }

                            //再次查找，跟定時(shí)找不到的啦。
                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 閱讀(1341) 評(píng)論(2)  編輯 收藏 引用  所屬分類: 數(shù)據(jù)結(jié)構(gòu)和算法 
		
            
	
            
	
	


	


            
	    
    


            

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

            




            






            

				

            


    
    







            
	   
	



日本精品久久久久久久久免费|
久久综合久久综合久久综合|
久久性精品|
久久精品一本到99热免费|
色综合久久久久久久久五月|
久久国产精品-久久精品|
久久久久亚洲AV综合波多野结衣|
久久久久亚洲av成人网人人软件|
久久99精品久久久久婷婷|
久久久久亚洲精品天堂久久久久久|
久久国语露脸国产精品电影|
久久久无码精品亚洲日韩蜜臀浪潮|
91久久九九无码成人网站|
日韩精品久久久久久免费|
国产精品欧美亚洲韩国日本久久|
香蕉久久av一区二区三区|
久久精品国产色蜜蜜麻豆|
丰满少妇人妻久久久久久|
国产精品久久久久免费a∨|
国产精品久久久久9999高清|
久久人人爽人人爽人人av东京热|
久久精品成人欧美大片|
久久青青草原综合伊人|
久久久精品2019免费观看|
久久www免费人成看片|
午夜视频久久久久一区|
国产一区二区精品久久凹凸|
久久精品国产精品国产精品污|
亚洲中文精品久久久久久不卡|
久久天天躁狠狠躁夜夜2020|
国产成人精品久久综合|
四虎国产精品免费久久5151|
久久午夜伦鲁片免费无码|
亚洲精品无码久久久久sm|
国内精品综合久久久40p|
一本一道久久a久久精品综合|
国产精品久久免费|
精品免费tv久久久久久久|
精品久久久久久中文字幕|
丁香五月综合久久激情|
国产精品狼人久久久久影院|