1

ステップ付きの線形プロービングを使用して衝突を解決する効率的なハッシュテーブルを実装しようとしています。この機能は、可能な限り効率的である必要があります。不必要な=操作==はありません。私のコードは機能していますが、効率的ではありません。この効率は、社内システムによって評価されます。それはより良い必要があります。

キーと値のペアを表す2つのクラスがあります：CKeyとCValue。これらのクラスにはそれぞれ、標準コンストラクター、コピーコンストラクター、およびオーバーライドされた演算子=とがあり==ます。どちらにも、getValue()内部プライベート変数の値を返すメソッドが含まれています。getHashLPS()の中には、ハッシュテーブル内CKeyのハッシュされた位置を返すメソッドもあります。

int getHashLPS(int tableSize,int step, int collision) const
{
    return ((value + (i*step)) % tableSize);
}

ハッシュ表。

class CTable
{
    struct CItem {
            CKey key;
            CValue value;
        };
    CItem **table;
    int valueCounter;       
}

メソッド

// return collisions count
int insert(const CKey& key, const CValue& val)
{
    int position, collision = 0;

    while(true)
    {
        position = key.getHashLPS(tableSize, step, collision); // get position
        if(table[position] == NULL) // free space
        {
            table[position] = new CItem; // save item
            table[position]->key = CKey(key);
            table[position]->value = CValue(val);
            valueCounter++;
            break;
        }

        if(table[position]->key == key) // same keys => overwrite value
        {
            table[position]->value = val;
            break;
        }

        collision++; // current positions is full, try another

        if(collision >= tableSize) // full table
            return -1;
    }

    return collision;
}

// return collisions count
int remove(const CKey& key)
{
    int position, collision = 0;

    while(true)
    {
        position = key.getHashLPS(tableSize, step, collision);
        if(table[position] == NULL) // free position - key isn't in table or is unreachable bacause of wrong rehashing
            return -1;

        if(table[position]->key == key) // found
        {
            table[position] = NULL; // remove it
            valueCounter--;

            int newPosition, collisionRehash = 0;
            for(int i = 0; i < tableSize; i++, collisionRehash = 0) // rehash table
            {
                if(table[i] != NULL) // if there is a item, rehash it
                {
                    while(true)
                    {
                        newPosition = table[i]->key.getHashLPS(tableSize, step, collisionRehash++);
                        if(newPosition == i) // same position like before
                            break;

                        if(table[newPosition] == NULL) // new position and there is a free space
                        {
                            table[newPosition] = table[i]; // copy from old, insert to new
                            table[i] = NULL; // remove from old
                            break;
                        }
                    }
                }
            }

            break;
        }

        collision++; // there is some item on newPosition, let's count another

        if(collision >= valueCounter) // item isn't in table
            return -1;
    }

    return collision;
}

どちらの関数も（私自身の目的で）衝突カウントを返し-1、検索対象CKeyがテーブルにない場合、またはテーブルがいっぱいの場合に戻ります。

墓石は禁止されています。取り外した後の再ハッシュは必須です。

4

2 に答える 2

2

私が見る改善のための最大の変更は、削除機能にあります。テーブル全体を再ハッシュする必要はありません。空のバケットに到達するまで、削除ポイントから再ハッシュする必要があるだけです。また、再ハッシュする場合は、再ハッシュを行う前に、再ハッシュが必要なすべてのアイテムを削除して保存し、元に戻すときに邪魔にならないようにします。

別物。すべてのハッシュで、loadFactor（バッキングアレイサイズに対する要素の比率）を減らすために効率を上げる最も速い方法。これにより、衝突の数が減ります。つまり、オープンスポットを探す反復が少なくなり、削除時の再ハッシュが少なくなります。限界では、loadFactorが0に近づくと、衝突確率は0に近づき、配列のようになります。もちろんメモリ使用量は増えますが。

更新 削除ポイントから開始して、ヌルに達するまでステップサイズずつ進めていくだけで再ハッシュする必要があります。これは、削除によって場所が変更される可能性があるのはこれらのオブジェクトだけであるためです。他のすべてのオブジェクトは、同じ「衝突ラン」に属していないため、まったく同じ場所に移動することになります。

于 2011-11-12T14:18:24.813 に答える
0

考えられる改善は、CItemの配列を事前に割り当てることです。これにより、malloc（）s / newsおよびfree（）の削除が回避されます。配列を「CItem*table;」に変更する必要があります。

しかし、繰り返しになりますが、必要なのは、基本的に四角い車輪のある車でのスムーズな乗り心地です。

于 2011-11-12T15:25:44.130 に答える