c++ - 如何使我的线性探测哈希表更高效？

Question

我正在尝试实现一个高效的哈希表，其中使用带步骤的线性探测来解决冲突。此功能必须尽可能高效。没有不必要的 = 或 == 操作。我的代码有效，但效率不高。这种效率由公司内部系统评估。它需要变得更好。

有两个类表示键/值对:CKey 和CValue。这些类每个都有一个标准构造函数、复制构造函数和重写运算符 = 和 ==。它们都包含一个返回内部私有(private)变量值的getValue() 方法。 CKey中还有方法getHashLPS()，返回哈希表中的哈希位置。

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;
}

这两个函数都返回冲突计数(出于我自己的目的)，当搜索到的 CKey 不在表中或表已满时，它们返回 -1。

墓碑是被禁止的。删除后重新散列是必须的。

Answer 1

我看到的最大改进变化是删除功能。您不需要重新散列整个表。您只需要从删除点开始重新散列，直到到达一个空桶。此外，在重新散列时，在进行重新散列之前移除并存储所有需要重新散列的项目，以便在将它们放回原位时不会妨碍它们。

还有一点。对于所有哈希，提高效率的最快方法是降低 loadFactor(元素与支持数组大小的比率)。这减少了碰撞的次数，这意味着更少的迭代寻找开放点，以及更少的移除时的重新散列。在极限情况下，随着loadFactor趋近于0，碰撞概率趋近于0，越来越像一个数组。当然，内存使用量会增加。

更新 您只需要从删除点开始重新散列，然后按您的步长向前移动，直到达到空值。这样做的原因是这些是唯一可能因移除而改变其位置的对象。所有其他物体最终都会到达完全相同的位置，因为它们不属于同一个“碰撞运行”。