1

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

有两个类表示键/值对：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

一个可能的改进是预先分配一个 CItems 数组，这将避免 malloc()s / news 和 free() 删除；并且您需要将数组更改为“CItem *table;”

但是再说一遍：您想要的基本上是在方形轮子的汽车中平稳行驶。

于 2011-11-12T15:25:44.130 回答