C++哈希表对比数组搜索代码编译无错但无输出且无法运行

你的代码编译通过但无输出，核心原因是**insert函数存在死循环**，导致程序在启动初期就卡住，无法执行后续逻辑。以下是具体问题点和修复方案：

1. Insert函数的死循环（最关键问题） #

原insert的逻辑完全颠倒，导致程序第一次调用insert就进入无限循环，这也是main开头的cout没输出的原因（程序还没执行到那一步就卡住了）。

原代码错误： #

void hashtable::insert(int n){
    int key = n % size;

    while(p[key] == -1){
        if(p[key] ==n){ 
            break;
        }
        else{
            key = (key+1) % size;
        }
    }
    p[key]=n;
}

错误逻辑：

• 循环条件while(p[key] == -1)是"当位置为空时进入循环"，但我们的目标是找到空位置或已存在的元素，正确逻辑应该是"当位置被占用且不是目标元素时，继续探测"。
• 初始状态下所有位置都是-1，进入循环后p[key] ==n永远不成立（n是0-99的随机数），导致无限执行key = (key+1) % size，形成死循环。

修复后的Insert函数： #

void hashtable::insert(int n){
    int key = n % size;

    // 当当前位置被占用且不是要插入的元素时，继续线性探测
    while(p[key] != -1 && p[key] != n){
        key = (key+1) % size;
    }
    p[key] = n;
}

2. 数组S初始化未给循环变量赋值 #

原代码初始化数组S时，循环变量i未初始化，初始值为随机值，可能直接跳过循环，导致S数组存的是垃圾值：

for(int i; i<50;i++){
    S[i] = -1;
}

修复： #

for(int i = 0; i<50;i++){
    S[i] = -1;
}

3. 数组搜索逻辑的越界与计数错误 #

原代码中搜索数组时，内层循环修改了外层循环的变量i，导致循环次数混乱，甚至越界访问数组；如果搜索的元素不存在，还会无限循环：

for (int i = 0; i<5; i++){
    cout <<"Enter number to search: ";
    cin >> k;
    while(S[i]!=k){
        arrayavg++;
        i++;
    }
    hashavg = hashavg + h.search(k);
}

修复方案： #

使用独立的索引变量，避免修改外层循环的计数器，同时处理元素不存在的情况：

for (int i = 0; i<5; i++){
    cout <<"Enter number to search: ";
    cin >> k;
    // 数组搜索用独立变量j，不干扰外层循环
    int j = 0;
    int arr_compare = 0;
    bool found_in_arr = false;
    while(j < 50){
        arr_compare++;
        if(S[j] == k){
            found_in_arr = true;
            break;
        }
        j++;
    }
    if(!found_in_arr){
        cout << "该数不在数组中，请重新输入" << endl;
        i--; // 重新执行当前循环
        continue;
    }
    arrayavg += arr_compare;

    // 哈希表搜索并处理未找到的情况
    int hash_compare = h.search(k);
    if(hash_compare == -1){
        cout << "该数不在哈希表中，请重新输入" << endl;
        i--;
        continue;
    }
    hashavg += hash_compare;
}

4. Search函数的比较计数错误 #

原search函数的比较次数初始值为-1，找到元素时返回的数值不符合实际比较次数，且未处理全表遍历仍未找到的情况：

int hashtable::search(int n){
    int key = n%size;
    int comparisons =-1;

    while (p[key] != -1){
        if (p[key] ==n){
            return comparisons;
        }
        else{
            key = (key+1) %size;
            comparisons++;
        }
    }
    return comparisons;
}

修复后的Search函数： #

int hashtable::search(int n){
    int key = n%size;
    int comparisons = 1; // 第一次比较算1次

    while (p[key] != -1){
        if (p[key] ==n){
            return comparisons;
        }
        else{
            key = (key+1) %size;
            comparisons++;
            // 防止全表遍历仍未找到，避免死循环
            if(comparisons > size){
                return -1;
            }
        }
    }
    return -1; // 未找到目标元素
}

其他补充修复 #

• 添加必要头文件：rand()需要<cstdlib>，time()需要<ctime>，在代码开头补充：

  #include <cstdlib>
  #include <ctime>
  

• 设置随机种子：在main开头添加srand(time(nullptr));，避免每次运行生成相同的随机数。

完整修复后的代码 #

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

class hashtable{
    private:
        int *p;
        int size;
    public:
        hashtable();
        ~hashtable();
        void insert(int n);
        int search(int n);

};

hashtable::hashtable(){
    size =50;
    p =new int[50];
    for (int i =0; i<size; i++){
        p[i] = -1;
    }

}

hashtable::~hashtable(){
    delete [] p;
}

void hashtable::insert(int n){
    int key = n % size;

    while(p[key] != -1 && p[key] != n){
        key = (key+1) % size;
    }
    p[key]=n;
}

int hashtable::search(int n){
    int key = n%size;
    int comparisons = 1;

    while (p[key] != -1){
        if (p[key] ==n){
            return comparisons;
        }
        else{
            key = (key+1) %size;
            comparisons++;
            if(comparisons > size){
                return -1;
            }
        }
    }
    return -1;
}

int main(){
    srand(time(nullptr));
    cout <<"program start" <<endl;
    hashtable h;
    int S[50];

    for(int i = 0; i<50;i++){
        S[i] = -1;
    }

    for (int i = 0; i<50 ; i++){
        int j = rand()%100;
        h.insert(j);
        S[i] = j;    
    }
    int k;
    int hashavg = 0;
    int arrayavg =0;
    for (int i = 0; i<5; i++){
        cout <<"Enter number to search: ";
        cin >> k;
        int j = 0;
        int arr_compare = 0;
        bool found_in_arr = false;
        while(j < 50){
            arr_compare++;
            if(S[j] == k){
                found_in_arr = true;
                break;
            }
            j++;
        }
        if(!found_in_arr){
            cout << "该数不在数组中，请重新输入" << endl;
            i--;
            continue;
        }
        arrayavg += arr_compare;

        int hash_compare = h.search(k);
        if(hash_compare == -1){
            cout << "该数不在哈希表中，请重新输入" << endl;
            i--;
            continue;
        }
        hashavg += hash_compare;
    }
    cout <<"Average comparisons of hash table: " <<double(hashavg) / 5 <<endl;
    cout <<"Average comparisons of array: " <<double(arrayavg) /5 <<endl;
}

内容的提问来源于stack exchange，提问作者JdoubleU