ほぼコスト0でのハッシュクリア

　http://d.hatena.ne.jp/ak11/20090514#p1

　aki.さんの日記を読んでて思い出したんで、サクッと書いときます。

　要点としてはこんな感じです。

1. ハッシュアクセス時にハッシュ表固有のカウンタをインクリメントしていく
2. ハッシュの各エントリに、最後にアクセスした時点のカウンタを保存しておく
3. ハッシュクリア時は、その時点でのカウンタを覚えておくだけ
4. ハッシュアクセス時にエントリのカウンタとクリア時のカウンタを比較し、クリア以前のエントリは消されたものとして扱う

　もの凄く大雑把に言うと「クリア以前のデータは無視する」ってだけなんですけどね。

　色々書くよりサンプルコード書いた方が後で読み返した時に分かりやすいだろうから、以下サンプル。

// 局面クラス
public class Position {

  // ...

};// Position

// ハッシュに保存するデータをまとめるクラス
public class Entry {

public:
  // 最終アクセス時のカウンタ
  int lastAccessCounter;
  
  // その他、評価値とかウィンドウ位置とか色々

};

public class HashTable {

private:
  // アクセスカウンタ
  int counter;

public:
  // ハッシュをクリアした時点でのカウンタの値
  int clearCounter;

  // この辺に実際のハッシュ表用のメンバを書いとく

public:
  HashTable() : counter( 0 ), clearCounter( 0 ) { /* NOP */ }

public:
  // ハッシュ表からデータを取り出す
  Entry get( Position *const p ) {

    this->counter++;

    // ...
    
    Entry *entry;

    // 最終アクセスがクリア以前なら、存在しないエントリとして処理する
    if( entry->lastAccessCounter <= this->clearCounter ) { /* ... */ }

    // ...

    // アクセス時点のカウンタを保存
    e->lastAccessCounter = this->counter;

    // ...

  }// get(...)

public:
  // ハッシュ表にデータを保存する
  void set( Position *const p, Entry *const e ) {

    this->counter++;

    // アクセス時点のカウンタを保存
    e->lastAccessCounter = this->counter;

    // ...

  }// set(...)

public:
  void clear() {

    this->counter++;

    this->clearCounter = this->counter;

  }// clear()
  
};// HashTable

　細かい事を言うと、マルチスレッド時はカウンタインクリメントにInterlockedIncrementあたりを使った方がよさげとか、カウンタが32ビットだと心許ないとかありますが、その辺はサンプルって事でどうか一つ。

　まぁ、デメリットもいくつかあって

1. エントリごとに32ビットなり64ビットなりのメンバ変数が必要（＝同じメモリ量だと格納可能なエントリ数が減る）
2. アクセスごとにカウンタをインクリメントするのが、多少時間を喰う

　って感じです。前者はひょっとしたら痛いかも。時間を取るか空間を取るか、悩ましい所です。