7-17 字符串关键字的散列映射 (25分) (防止标题重复)

忘是亡心i 2022-12-29 00:11 118阅读 0赞

> 这份是自己写的…  
> 不能在HashCode()求key值对key%P, 而应该在插入到list中或者解决冲突的时候可以求余  
> 对一些变量名和函数名有疑问可以在评论回复

#include <iostream>
    #include <cstdlib>
    #include <string>
    
    using namespace std;
    const int constnum = 32;
    const int MAXNUM = 1e3 + 20;
    string Hashtable[MAXNUM];
    string original_list[MAXNUM];
    int n, P;
    
    void input() {
        
        cin >> n >> P;
        for (int i = 0; i < n; i++) {
        
            cin >> original_list[i];
        }
    }
    
    int HashCode(string word) {
        
        int cnt = 0, key = 0;
        int base = 1;
        for (int i = word.length() - 1; i >= 0 && cnt < 3; i--, cnt++) {
        
            key += (int)(word[i] - 'A') * base;
            base *= constnum;
        }
        //printf("[%d]\n", key);
        return key;
    }
    
    //我想用这个函数
    //1 构造哈希表的时候,找空位置
    //2 查哈希表的时候,定位, 所以参数string word
    int Conflict_resolution_and_return_finalkey(int key, string word) {
        
        int di = 1;
        while (di <= P / 2) {
        
            int temp_key = ((key + di * di) % P);
            if (Hashtable[temp_key].empty() || Hashtable[temp_key] == word) {
        
                Hashtable[temp_key] = word;
                return temp_key;
            }
            temp_key = ((key - di * di) % P);
            if (Hashtable[temp_key].empty() || Hashtable[temp_key] == word) {
        
                Hashtable[temp_key] = word;
                return temp_key;
            }
            di++;
        }
        return -1;
    }
    
    void word_into_hashtable(int key, string word) {
        
        //若这个位置是空的
        if (Hashtable[key % P].empty()) {
        
            Hashtable[key % P] = word;
        }
        //解决冲突
        else {
        
            Conflict_resolution_and_return_finalkey(key, word);
        }
    }
    
    void list_into_hashtable() {
        
        for (int i = 0; i < n; i++) {
        
            word_into_hashtable(HashCode(original_list[i]), original_list[i]);
        }
    }
    
    void print() {
        
        for (int i = 0; i < n; i++) {
        
            int key = HashCode(original_list[i]);
            if (i != 0) cout << " ";
            if (Hashtable[key % P] == original_list[i])
                cout << key % P;
            else 
            cout << Conflict_resolution_and_return_finalkey(key, original_list[i]);
        }
        cout << endl;
    }
    int main() {
        
        input();
        list_into_hashtable();
        print();
        //cout << HashCode(original_list[0]) << endl;
        system("pause");
        return 0;
    }