step by step

散列2

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

   

 1//使用探測(cè)策略的散列表的類(lèi)接口，包括嵌套的HashEntry
 2  類(lèi)
 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//初始化平方探測(cè)散列表的例程
 2explicit HashTable( int size = 101 ) : array(nextPrime( size ) )
 3{ makeEmpty(); }
 4
 5void makeEmpty()
 6{
 7    currentSize = 0;
 8    for( int i = 0; i<array.size(); i++ )
 9        array[i].info = EMPTY;
10}

 

 1//使用平方探測(cè)進(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    //下面是一個(gè)小小的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//使用平方探測(cè)的散列表的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;//傳說(shuō)中的懶惰刪除
22    return true;
23}

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

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