与C ++中的哈希表基础混淆

Question

这是我编写的有关哈希表的一小段代码。

#include <iostream>
using namespace std;

int hashval(int n){
    return n%5;
}


int main(){
    int hashtable[4],num, value;
    for (int i=0 ; i<=4; i++){
        hashtable[i]=0;
    }
    for (int i=0; i <=4; i++){
        cout << "Enter the number you wanna enter : ";
        cin>> num;
        value=hashval(num);
        while (hashtable[value]!=0){
            value=(value+1)%5;
        }
        hashtable[value]=num;
    }
     **// line A //** cout << hashtable[0] << "  " << hashtable[1] << "  " << hashtable[2] << "  " <<hashtable[3]<< "  " << hashtable[4] << "  " <<endl; 

    for (int j=0; j<=4; j=j+1){
    **// line B //**    cout << hashtable[j] << " ";  
    }

}

当我输入五个数字作为“ 13,15,18,29,30”时，A行显示输出“ 15 29 30 13 18”。但是，B行未显示最后一个元素，即显示的输出为“ 15 29 30 13 4”。 4来自哪里？无论为什么输入了什么元素，为什么总是不打印最后一个元素，而打印了一个不存在的元素，我对此感到困惑。 A和B行的功能不同吗？我的代码有什么问题？任何帮助将不胜感激。谢谢！

Answer 1

您的问题是int hashtable[4]分配了一个数组，该数组可以存储四个值，索引从0 ... 3开始。但是，然后尝试在数组中存储五个值。

通常，C ++非常不适合编译和查看学习方法。当代码依赖未定义的行为时，在C ++中编译和测试代码，发现代码“有效”是非常普遍的。但是，在这种情况下，我们可以凭经验看到[4]仅为四个元素分配足够的空间。以下代码将数组的大小除以元素之一的大小，从而计算出数组可以存储的最大元素数。

#include <iostream>                                                                                                     
int main(){                                                                                                                     
  int a[4];                                                                                                               
  std::cout << (sizeof(a)/sizeof(a[0]));
  return 0;                                                                          
}

上面的代码输出4，表明int a[4]为4个元素分配了足够的空间。在包含4个元素的数组中存储5个元素会导致未定义的行为。

虽然我们可以在这里结束故事，只是说未定义的行为可以做任何事情，但有时了解（但不依赖）溢出数组最常见的副作用是很有用的。通常，发生的情况是您访问未分配的内存或分配给另一个变量的内存。请注意，在第一次和第二次打印hashtable[4]之间，您分配了变量j，并且当第二次访问j时，hashtable[4]恰好是4。最好打赌，由于您没有分配hashtable[4]所在的内存，因此编译器认为该内存未被使用，然后将j放在此处。然后，当您打印hashtable[4]时，实际上是在打印j。

强调未定义的行为意味着您不应该依赖编译和测试，这不是我的编译器（g++）发生的事情。您的代码运行良好，甚至没有发出任何valgrind或-Wall警告。

除了数组太小以外，您的代码对我而言似乎是正确的，因此，如果您仅将int hashtable[4]更改为int hashtable[5]，则您的代码应在每个C ++编译器上都能正常工作。