为什么我的变量值会随机变化?

I'm a newbie to C programming and I start learning data structures and algorithms just recently. The textbook I select is Data Structures and Algorithm Analysis in C, which introduces the hash table ADT in Chap.5. And here is one implementation of its quad open addressing version, in which the function Find passes values of Key and TableSize to Hash function and it will return the hashed value as the variable CurrentPos. The following are function Hash and Find:

我是C编程的新手，最近我开始学习数据结构和算法。我选择的教材是C语言的数据结构和算法分析，其中介绍了第5章中的哈希表ADT。这是它的四*度开放寻址版本的一个实现，其中函数查找键值并将TableSize传递给哈希函数，它将返回哈希值作为变量CurrentPos。下面是函数哈希和查找:

Index
Hash( ElementType Key, int TableSize )
{
    return Key % TableSize;
}

Position
Find(ElementType Key, HashTable H)
{
    Position CurrentPos;
    int CollisionNum;

    CollisionNum = 0;
    CurrentPos = Hash(Key, H->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;
}

And here is the header:

这是标题:

    typedef int ElementType;
    #ifndef _HashQuad_H
    #define _HashQuad_H

    typedef unsigned int Index;
    typedef Index Position;

    struct HashTbl;
    typedef struct HashTbl *HashTable;

    HashTable InitializeTable( int TableSize );
    void DestroyTable( HashTable H );
    Position Find( ElementType Key, HashTable H );
    void Insert( ElementType Key, HashTable H );
    ElementType Retrieve( Position P, HashTable H );
    HashTable Rehash( HashTable H );

    #endif

And the following are typedefs and structs in source file:

源文件中的typedef和struct:

    struct HashEntry
    {
        ElementType      Element;
        enum KindOfEntry Info;
    };

    typedef struct HashEntry Cell;

    /* Cell *TheCells will be an array of */
    /* HashEntry cells, allocated later */
    struct HashTbl
    {
        int TableSize;
        Cell *TheCells;
    };

This is the way H being initialized

这是H初始化的方式

    HashTable
    InitializeTable( int TableSize )
    {
        HashTable H;
        int i;

    if( TableSize < MinTableSize )
        {
            Error( "Table size too small" );
            return NULL;
        }

        /* Allocate table */
        H = malloc( sizeof( struct HashTbl ) );
        if( H == NULL )
            FatalError( "Out of space!!!" );

        H->TableSize = NextPrime( TableSize );

        /* Allocate array of Cells */
        H->TheCells = malloc( sizeof( Cell ) * H->TableSize );
        if( H->TheCells == NULL )
            FatalError( "Out of space!!!" );

        for( i = 0; i < H->TableSize; i++ )
            H->TheCells[ i ].Info = Empty;

        return H;
    }

Now the problem is, however this implementation works fine for most cases. It does encounter crash sometimes. When it happens, I try unit-test and find that after calling of Hash function at one certain round, the value of CurrentPos will be assigned to be a integer that's much larger than the actual return value of Hash function, it could be 1000 plus or even bigger. For example, if Key is 29918 and TableSize is 101, the correct answer and yes the returned value by Hash is 22, but after the assignment line:

现在的问题是，不管怎样，这种实现在大多数情况下都很有效。它有时会遇到崩溃。当发生这种情况时，我尝试进行单元测试，并发现在某一轮调用哈希函数后，CurrentPos的值将被赋值为一个比哈希函数的实际返回值大得多的整数，可能是1000 +甚至更大。例如，如果Key是29918,TableSize是101，正确的答案是yes，那么Hash返回的值是22，但是在赋值行之后:

 CurrentPos = Hash(Key, H->TableSize);

The value of CurrentPos changes to be 1580 all by itself, for no reason. Note that the Key value at the time that's randomly assigned using rand() based on a seed of function time() is less than the upper-boundary of type integer - I mean there should be no overflow.

CurrentPos的值会自动变为1580，没有任何原因。注意，在使用rand()的时候，根据函数时间()的种子随机分配的键值小于类型整数的上限，我的意思是不应该有溢出。

I tried hard to look closer to the Watches, but there is no other error or clue. I'm confused because this error happens really randomly. Is there anyone who's familiar with this?

我尽量靠近手表看，但没有其他错误或线索。我很困惑，因为这个错误是随机发生的。有谁知道这个吗?

1 个解决方案

#1

If CollisionNum becomes sufficiently large then this test will not work correctly:

如果碰撞足够大，那么这个测试将不能正确工作:

       if(CurrentPos >= H->TableSize)
            CurrentPos -= H->TableSize;

since if CurrentPos >= H->TableSize*2 then CurrentPos will still be out of range after the subtraction of H->TableSize.

因为如果CurrentPos >= H->TableSize*2，那么在H->TableSize做减法之后，CurrentPos仍然会超出范围。

You should change this to either:

您应该将其改为:

       while (CurrentPos >= H->TableSize)
            CurrentPos -= H->TableSize;

or:

或者:

       CurrentPos = CurrentPos % H->TableSize;

or even:

甚至:

       CurrentPos %= H->TableSize;

#1