1//对探测散列表和分离链接散列表的再散列
 2void rehash()
 3{
 4    vector<HashEntry> oldArray = array;
 5    array.resize( nextPrime( 2* oldArray.size() ) );
 6    for( int j = 0; j<array.size(); j++ )
 7        array[j].info = EMPTY;
 8    currentSize = 0;
 9    for( int i = 0; i<oldArray.size(); i++ )
10        if( oldArray[i].info == ACTIVE )
11            insert( oldArray[i].element );
12}
13
14void rehash()
15{
16    vector<list<HashedObj> > oldLists = theLists;
17    theLists.resize( nextPrime( 2* theLists.size() ) );
18    for( int j = 0; j<theLists.size(); j++ )
19        theLists[j].clear();
20    currentSize = 0;
21    for( int i = 0; i<oldLists.size(); i++ )
22    {
23        list<HashedObj>::iterator itr = OldLists[i].begin();
24        while ( itr != oldLists[i].end() )
25            insert( *itr++ );
26    }
27}

2.标准库中的散列表
    标准库中不包括set和map的散列表实现。但是，许多的编译器提供具有与set和map类相同的成员函数的hash_set和hash_map.
    要使用hash_set和hash_map，就必须有相应的包含指令，而且，可能也需要相应的命名空间。这两者都是和编译器相关的。接下来还必须提供相应的类型参数来说明
hash_set和hash_map。对于hash_map，这些类型参数包括键的类型，值的类型，散列函数(返回无符号整数)和一个相等性操作符。遗憾的是，至于键和值的类型参数如何
表示还是编译器相关的。
    下一次c++的较大的修订将不可避免地包括这些hash_set和hash_map中的一个。

3.可扩散列
    最后讨论数据量太大以至于装不进主存的情况，此时主要考虑的是检索数据所需的磁盘存取次数。假设在任意时刻都有N个记录要存储，N的值随时间而变化。此外，最多可把M个记录放入一个磁盘区块，设M=4,如果使用探测散列或分离链接散列，那么主要的问题在于，即使是理想分布的散列表，在一次查找操作中，冲突也可能引起对多个区块的访问。不仅如此，当表变得过慢的时候，必须执行代价巨大的再散列这一步，它需要O(N)的磁盘访问。
    一种聪明的选择成为可扩散列(extendible hashing),它允许用两次磁盘访问执行一次查找。插入操作也需要很少的磁盘访问.
   Extendible hashing from Wikipedia
   Extendible hashing is a type of hash system which treats a hash as a bit string, and uses a trie for bucket lookup. Because of the hierarchal nature of the system, re-hashing is an incremental operation (done one bucket at a time, as needed). This means that time-sensitive applications are less affected by table growth than by standard full-table rehashes.

   

This is a more simplistic example from Fagin et al. (1979).

Assume that the hash function h(k) returns a binary number. The first i bits of each string will be used as indices to figure out where they will go in the "directory" (hash table). Additionally, i is the smallest number such that the first i bits of all keys are different.

Keys to be used:

h(k₁) = 100100
h(k₂) = 010110
h(k₃) = 110110

Let's assume that for this particular example, the bucket size is 1. The first two keys to be inserted, k₁ and k₂, can be distinguished by the most significant bit, and would be inserted into the table as follows:

 directory
---------
|    0    |-----------> Bucket A (contains k2)
|---------|
|    1    |-----------> Bucket B (contains k1)
---------

Now, if k₃ were to be hashed to the table, it wouldn't be enough to distinguish all three keys by one bit (because k₃ and k₁ have 1 as their leftmost bit. Also, because the bucket size is one, the table would overflow. Because comparing the first two most significant bits would give each key a unique location, the directory size is doubled as follows:

  directory
----------
|    00    |-----\
|----------|      ----------> Bucket A (contains k2)
|    01    |-----/
|----------|
|    10    |-----------> Bucket B (contains k1)
|----------|
|    11    |-----------> Bucket C (contains k3)
----------

And so now k₁ and k₃ have a unique location, being distinguished by the first two leftmost bits. Because k₂ is in the top half of the table, both 00 and 01 point to it because there is no other key to compare to that begins with a 0.

helmi:

Hi, I just found this very useful site and I have read almost all of tutorial, guide, articles.

I just ask everybody opinion on the future of C/C++ because a lot of other programming language out there now days. What do you think since more applications develop as on web base platform? This is just my observation in my country. I really like coding in C++ because I can feel I'm doing low level programming. I do have write game using directX as a hobby but to sustain, I have need to write applications using php, asp .net and jsp.


ps: Sorry for my bad English.

"the number of seasoned C++ programmers is also relatively small. In the United States, C++ programmers are in high demand (and are very well paid)."

Really? I should go working in the United States


I have read of about the D language in a game forum. It's has a lot of features and so powerful but still need improvement, good IDE etc.

QUOTE (helmi @ Feb 1 2007, 05:30 PM)

QUOTE (Bartosz @ Feb 2 2007, 04:32 AM)

QUOTE (peter @ Feb 15 2007, 07:34 AM)

QUOTE (James @ Feb 20 2007, 02:02 PM)

QUOTE (Dave @ Aug 23 2007, 12:25 PM)

QUOTE (peter @ Mar 4 2008, 05:22 AM)

QUOTE (hansgostajonsson @ Mar 4 2008, 12:51 PM)

QUOTE (Bartosz @ Mar 4 2008, 11:10 PM)

We are trying to incorporate the latest PL trends in D, sometimes even before they mature .

One major area is safe programming. There's been a lot of research into proving soundness of various languages using operational semantics. It culminated in the soundness proof for Featherweight (Generic) Java. Although it's not a goal of D to be a sound language (we do want pointers after all), we are defining a sound subset of D. In particular, we have a program that can translate Java programs into this subset. We will have one-to-one correspondence between Java semantics and the semantics of a subset of D (which is equivalent to having denotational semantics for the D subset).

We are planning on extending the safe D subset with other sound features, such as discriminated unions and elements of functional programming. D already supports anonymous functions and closures.

The other major area is concurrent programming. Again, Java leads the crowd with its memory model. D's memory model will most likely resemble that of C++ (still in the form of a proposal). The difference between the Java model and the C++ model is that Java gives some guarantees even for programs with race conditions-- C++ doesn't. So a racy program in C++ may exhibit undefined behavior. On the other hand Java has a virtual machine that may enforce a lot more during runtime that can be accomplished in a compiled language.

How can we support safe concurrency in the presence of races--or eliminate the races altogether? The idea is to build software transactional memory into D. Even though STM might not offer the best performance, it is much safer (and easier) than lock-based programming. Especially if we can build support for transactions into the type system, as has been done for Concurrent Haskell.

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)选择不好将会非常糟糕。
   
.