散列 table 在 c 中的查找功能？

Question

题目出自《数据结构与算法分析》c.When一书中讲到散列table，作者给出的查找函数是这样的：

Positon find(ElementType Key,HashTable H)
{
    Position CurrentPos;
    int CollisionNum;
    CollisionNum=0;
    CurrenPos=Hash(Key,T->TableSize)
    while(H->TheCells[CurrentPos].info!=Empty&&H->TheCells[CurrentPos].Element!=key)
    {
        CurrentPos+=2*++CollisionNum-1;
        if(CurrentPos>=H->TableSize)
            CurrentPos-=H->TableSize;
    }
    return CurrentPos;
}

作者说while句中判断条件的顺序，

H->TheCells[CurrentPos].info!=Empty && H->TheCells[CurrentPos].Element!=key

非常重要，不应交换。但我不知道为什么。我曾尝试交换订单，但该功能仍然正常工作。换单会出现什么BUG？

Answer 1

没有进一步的细节，我的猜测是，如果 H->TheCells[CurrentPos].info 是 Empty，那么 H->TheCells[CurrentPos].Element 是没有意义的（可能没有初始化？），因此评估它会导致错误。

这是一个（有点silly/extreme）这种模式的例子：

char *dst = NULL;
if (dst != NULL && memcpy(dst, "foo", strlen("foo" +1))) // this is OK
    // do stuff
memcpy(dst, "foo", strlen("foo" +1)); // segfault here!!!

这里有一些（不太傻的）伪代码来理解这个想法：

if (something.has_a_value == true && something.value == value_I_look_for)
    // then proceed

Answer 2

假设你写了多个条件，比如condition1 && condition2 && ...。这些是从左到右评估的。如果其中任何条件的计算结果为假，则不会计算右侧的其余条件。

现在您还没有向我们提供有关代码中使用的结构的足够信息，但假设单元格的 .info 包含 Empty 似乎是合理的，如果 [=15] =] 该单元格尚未初始化。

如果我们写

H->TheCells[CurrentPos].info!=Empty && H->TheCells[CurrentPos].Element!=key

那么我们首先要检查.Element是否已经初始化。只有当它是时，我们才会继续将它的值与 key 进行比较。如果不是，则永远不会访问 .Element。

但是如果我们写

 H->TheCells[CurrentPos].Element!=key && H->TheCells[CurrentPos].info!=Empty

可能会有问题。假设当前单元格的 .Element 尚未初始化。第一个条件访问 .Element 以将其与 key 进行比较。这可能会导致未定义的行为。

散列 table 在 c 中的查找功能？

Hash table's finding function in c?

c

data-structures

hashtable