为什么我们在C++中使用pos？假设由我的代码intpos=cHash（符号）；

Question

我在为我的编译器课程做一个SymbolTable的程序...我遇到了一个pos的问题...为什么我们首先要用它呢？TIA<3

void insert(char *symbol, char *type)
{
    int pos = cHash(symbol);

    if (block[pos] == NULL)
    {
        block[pos] = new SymbolInfo();
        block[pos]->symbol = symbol;
        block[pos]->type = type;
        block[pos]->next = NULL;
    }
    else
    {
        SymbolInfo *newNode = new SymbolInfo();
        newNode->symbol = symbol;
        newNode->type = type;

        // pointer swap
        SymbolInfo *nextNode = block[pos];
        block[pos] = newNode;
        newNode->next = nextNode;
    }
}

Answer 1

这里的代码实现了所谓的链式哈希表。我们维护一个链表数组，并使用函数cHash将每个符号分配给其中一个链表。

这样存放东西的好处是速度快。如果我们把所有东西都放入一个单链表中，那么查找东西的平均成本是O(n)，其中n是列表中的条目数，因为平均来说，我们至少要查找列表中的一半条目。但是，通过拥有多个链表（例如，其中的b个），并或多或少随机地在它们之间分配项目，我们将查找的平均成本降低到O(1+N/b)，如果b与N大致相同的数量级，则查找速度要快得多。