如何使用除法和二次探测将 int 存储到散列 table 中以避免在 C++ 中发生冲突

Question

所以最近我有一个关于我的数据结构主题的小测验，并且有一个涉及哈希表的问题。我的讲师确实教授了它背后的理论，但从未教授过编码方法，这非常令人沮丧。我试图 google 任何关于如何做的信息，但无济于事。现在在测验之后，我只想知道这是如何完成的，这样我就可以提高我的知识以进行进一步的测试或测验。我还添加了我的提交内容，以防有人需要查看它。

#include <iostream>
using namespace std;

int hash[30]; 
string key;
int value, keylength;
char yesorno;

int division(int keylength){
for(int i = 0; i <= keylength; i++){
    value = keylength % 30;
    hash[value];
    cout << "The bucket/cell location : " << hash[value] << endl;
}
}


/*int hashing(int hash[], int value){
for(int k = 0; k <=30; k++){
    hash[k] = value;
    cout << "The bucket/cell location : " << hash[value] << endl;
}
}*/

int main(){

do {
cout << "Enter planet name : ";
cin >> key;
keylength == key.length();
division(keylength);
//hashing(hash, value);
cout << "Do you want to continue...? " << endl;
cout << "Press 'Y' or 'y' for Yes else 'N' or 'n' : ";
cin >> yesorno;
} while(yesorno = 'Y' || 'y');

return 0;
}

Answer 1

问题不是要求将 int 存储到散列 table 中，而是要求存储 key（这里是行星名称）的散列 table 中的位置值。二次探测将像这样实现：

使用除法从键创建哈希值
如果hashtable[value]没有被占用则不需要任何探测。我们占据它和return的价值。否则我们将像这样开始二次探测：

for(int i=0;i<30;i++){ probe_value=(i*i+value)%30; // quadratic probing if(hashtable[probe_value] == "0"){ return probe_value; } } return -1; // as hashtabletable is full;

完整程序代码：

#include<bits/stdc++.h>
using namespace std;
string hashtable[30];
int hashtableing(string key){
        int value,probe_value;
        value= (key.length())%30; //division
        if(hashtable[value] == "0" || hashtable[value] ==key){
                hashtable[value]=key;
                return value;
        }else{
                for(int i=0;i<30;i++){
                        probe_value=(i*i+value)%30; // quadratic probing
                        if(hashtable[probe_value] == "0"){
                                return probe_value;
                        }
                }
                return -1; // as hashtabletable is full;
        }
}


int main(){
        string key;
        char choice='Y';
        for(int i=0;i<30;i++){
                hashtable[i]="0"; //0 indicates cell is unoccupied for probing
        }
        while(choice != 'N' && choice !='n'){
                cout<<"Enter planet name:"<<endl;
                cin>>key;
                cout<<"The bucket/cell location :"<< hashtableing(key)<<endl;
                cout<<"Do you want to continue...?"<<endl;
                cout<<"Press 'Y' or 'y' for Yes else 'n' or 'N':";
                cin>>choice;
        }
        return 0;
}

如何使用除法和二次探测将 int 存储到散列 table 中以避免在 C++ 中发生冲突

How to store int into hash table using division method and quadratic probing to avoid collision in C++

c++

hashtable

data-structures