step by step

散列2

3 不使用链表的散列表
    分离链接散列算法的缺点是使用一些链表。由于给新单元分配地址需要时间，因此这就导致算法的速度有些缓慢，同时算法实际上还要求第二种数据结构的实现。解决冲突的另一个方法是当冲突发生时就尝试选择另一个单元，直到找到空的单元。更正式地，单元h_i(x)=(hash(x)+f(i))mod TableSize,且f(0)=0.函数f是冲突解决函数。因为所有的数据都要置入表内，所以使用这个方案所需要的表要比分离链接散列需要的表大。一般说来，对不使用分离链接法的散列表来说，其装填因子应该低于λ=0.5。我们称这样的表为探测散列表(probing hash tables)。
    (1)当f是i的线性函数时，为线性探测，一般情况下f(i)=i，线性探测容易在占据的单元形成一些区块，其结果成为一次聚集(primary clustering)。
    (2)平方探测是消除线性探测中一次聚集问题的冲突解决方法。平方探测就是冲突函数为二次函数的探测方法。流行的选择是f(i)=i².
               定理：如果使用平方探测，且表的大小是素数，那么当表至少有一半是空的时候，总能够插入一个新的元素。
        如果哪怕表有比一半多一个的位置被填满，那么插入都有可能失败(虽然这种可能性极小)。另外，表的大小是素数也非常重要。如果表的大小不是素数，则备选单元
        的个数可能会锐减。例如，若表的大小是16，那么备选单元只能在距散列值1，4或9远处。
        在探测散列表中标准的删除操作不能执行，因为相应的单元可能已经引起过冲突，元素绕过它存储在别处。因此，探测散列表需要懒惰删除。
        实现探测散列表所需要的类接口在下图中给出。这里不使用链表数组，而是使用散列表项单元数组。嵌套的类HashEntry存储在info成员中一个项的状态，这个状态可
        以是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    for( int i = 0; i<array.size(); i++ )
 9        array[i].info = EMPTY;
10}

 

 1//使用平方探测进行散列的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*hash₂(x)。这个公式是说，将第二个散列函数应用到x并在距离hash₂(x),2hash₂(x),
      ...等处探测。hash₂(x)选择不好将会非常糟糕。
   
.

posted on 2009-11-26 20:20 小罗罗 阅读(410) 评论(0)  编辑 收藏 引用