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

            step by step

             

            散列2

            3 不使用鏈表的散列表
                分離鏈接散列算法的缺點(diǎn)是使用一些鏈表。由于給新單元分配地址需要時間,因此這就導(dǎo)致算法的速度有些緩慢,同時算法實(shí)際上還要求第二種數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)。解決沖突的另一個方法是當(dāng)沖突發(fā)生時就嘗試選擇另一個單元,直到找到空的單元。更正式地,單元hi(x)=(hash(x)+f(i))mod TableSize,且f(0)=0.函數(shù)f是沖突解決函數(shù)。因?yàn)樗械臄?shù)據(jù)都要置入表內(nèi),所以使用這個方案所需要的表要比分離鏈接散列需要的表大。一般說來,對不使用分離鏈接法的散列表來說,其裝填因子應(yīng)該低于λ=0.5。我們稱這樣的表為探測散列表(probing hash tables)。
                (1)當(dāng)f是i的線性函數(shù)時,為線性探測,一般情況下f(i)=i,線性探測容易在占據(jù)的單元形成一些區(qū)塊,其結(jié)果成為一次聚集(primary clustering)。
                (2)平方探測是消除線性探測中一次聚集問題的沖突解決方法。平方探測就是沖突函數(shù)為二次函數(shù)的探測方法。流行的選擇是f(i)=i2.
                           定理:如果使用平方探測,且表的大小是素數(shù),那么當(dāng)表至少有一半是空的時候,總能夠插入一個新的元素。
                    如果哪怕表有比一半多一個的位置被填滿,那么插入都有可能失敗(雖然這種可能性極小)。另外,表的大小是素數(shù)也非常重要。如果表的大小不是素數(shù),則備選單元
                    的個數(shù)可能會銳減。例如,若表的大小是16,那么備選單元只能在距散列值1,4或9遠(yuǎn)處。
                    在探測散列表中標(biāo)準(zhǔn)的刪除操作不能執(zhí)行,因?yàn)橄鄳?yīng)的單元可能已經(jīng)引起過沖突,元素繞過它存儲在別處。因此,探測散列表需要懶惰刪除。
                    實(shí)現(xiàn)探測散列表所需要的類接口在下圖中給出。這里不使用鏈表數(shù)組,而是使用散列表項單元數(shù)組。嵌套的類HashEntry存儲在info成員中一個項的狀態(tài),這個狀態(tài)可
                    以是ACTIVE,EMPTY或DELETED。

               

             1//使用探測策略的散列表的類接口,包括嵌套的HashEntry
             2  類
             3template <typename HashedObj>
             4class HashTable
             5{
             6public:
             7    explicit HashTable( int size = 101 );
             8    
             9    bool contains( const HashedObj &x ) const;
            10    
            11    void makeEmpty();
            12    bool insert( const HashedObj &x );
            13    bool remove( const HashedObj &x );
            14    
            15    emum EntryType (ACTIVE,EMPTY,DELETED );
            16
            17private:
            18    struct HashEntry
            19    {
            20        HashedObj element;
            21        EntryType info;
            22        HashEntry( const HashedObj & e = HashedObj(), EntryType i = EMPTY ) : element(e), info(i) { }
            23    }
            ;
            24
            25    vector<HashEntry> array;
            26    int currentSize;
            27 
            28    bool isActive( int currentPos ) const;
            29    int findPos( const HashedObj &x ) const;
            30    void rehash();
            31    int myhash( const HashedObj &x ) const;
            32}
            ;


             

             1//初始化平方探測散列表的例程
             2explicit HashTable( int size = 101 ) : array(nextPrime( size ) )
             3{ makeEmpty(); }
             4
             5void makeEmpty()
             6{
             7    currentSize = 0;
             8    forint i = 0; i<array.size(); i++ )
             9        array[i].info = EMPTY;
            10}



             

             1//使用平方探測進(jìn)行散列的contains例程
             2bool contains( const HashedObj &x ) const
             3{
             4    return isActive( findPos(x) ); }

             5
             6int findPos( const HashedObj &x ) const
             7{
             8    int offset = 1;
             9    int currentPos = myhash(x);
            10    
            11    //下面是一個小小的trick
            12    while ( array[ currentPos ].info != EMPTY && array[ currentPos ].element != x )
            13    {
            14        currentPos += offset;
            15        offset += 2;
            16        if( currentPos >= array.size() )
            17        currentPos -= array.size();
            18    }

            19    
            20    return currentPos;
            21}

            22
            23bool isActive( int currentPos ) const
            24{
            25    return array[ currentPos ].info == ACTIVE; }



             

             1//使用平方探測的散列表的insert和remove例程
             2bool insert ( const HashedObj &x )
             3{
             4    int currentPos = findPos( x );
             5    if ( isActive ( currentPos ) )
             6        return false;
             7    
             8    array[ currentPos ] = hashEntry( x, ACTIVE );
             9    if++currentSize > array.size() / 2 )
            10        rehash();
            11    
            12    return true;
            13}

            14
            15bool remove( const HashedObj &x )
            16{
            17    int currentPos = findPos(x);
            18    if ( !isActive( currentPos ) )
            19        return false;
            20    
            21    array[ currentPos ].info = DELETED;//傳說中的懶惰刪除
            22    return true;
            23}


              (3)最后一個沖突解決方法是雙散列(double hashing)。對于雙散列,一種流行的選擇是f(i)=i*hash2(x)。這個公式是說,將第二個散列函數(shù)應(yīng)用到x并在距離hash2(x),2hash2(x),
                  ...等處探測。hash2(x)選擇不好將會非常糟糕。
               
            .

            posted on 2009-11-26 20:20 小羅羅 閱讀(488) 評論(0)  編輯 收藏 引用


            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            導(dǎo)航

            統(tǒng)計

            常用鏈接

            留言簿

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久国产午夜精品一区二区三区| 亚洲一本综合久久| 国产精品一区二区久久精品无码 | 亚洲精品国精品久久99热| 亚洲一区精品伊人久久伊人| 国产精品久久久99| 久久乐国产综合亚洲精品| 亚洲AV日韩精品久久久久久久| 国产成年无码久久久久毛片| 伊人精品久久久久7777| 亚洲精品乱码久久久久久蜜桃不卡 | 久久亚洲国产精品成人AV秋霞| 久久精品国产亚洲精品2020| 久久受www免费人成_看片中文| 国产69精品久久久久99| 日韩欧美亚洲综合久久影院Ds| 久久66热人妻偷产精品9| 94久久国产乱子伦精品免费| 777久久精品一区二区三区无码| 久久久久久国产精品无码下载| 久久人做人爽一区二区三区| 色8激情欧美成人久久综合电| 亚洲综合伊人久久综合| 国产香蕉久久精品综合网| 久久久久亚洲AV无码网站| 老男人久久青草av高清| 日本免费一区二区久久人人澡| 国产一区二区三区久久| 久久香蕉超碰97国产精品| 久久久久av无码免费网| 久久这里只精品国产99热| 欧美一级久久久久久久大| 国内精品伊人久久久久av一坑 | 四虎久久影院| 91久久精品国产免费直播| 久久综合狠狠综合久久| 久久综合九色综合久99| 久久久久AV综合网成人| 狠狠色丁香久久婷婷综合图片| 久久久精品免费国产四虎| 亚洲乱码精品久久久久..|