7-17 字符串关键字的散列映射 (25分)（哈希+平方探测）

朱雀 2022-11-20 03:56 125阅读 0赞

最后一个数据是啥，大佬可以告诉我吗？  
还是STL方便  
，下面是大佬代码  
https://blog.csdn.net/xiang\_6/article/details/78254367

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <set>
    #include <map>
    
    using namespace std;
    const int BASIC_NUM = 32;
    const int MAXNUM = 1e5 + 5;
    //n将添加的元素个数， p大于n的素数，表示散列表的长度
    int n, p;
    string word;
    map<string, int> mp;
    bool vis[MAXNUM] = {
        false};
    int main()
    {
        
        scanf("%d %d", &n, &p);
        for (int i = 1; i <= n; i++)
        {
        
            cin >> word;
            int len = word.size();
            int address = 0;
            if (len == 1)
            {
        
                address += (word[0] - 'A');
            }
            else if(len == 2)
            {
        
                address = BASIC_NUM * (word[0] - 'A') + (word[1] - 'A');
            }
            else 
                for (int j = len - 3; j < len; j++)
                    address = address * BASIC_NUM + word[j] - 'A';
            
            address %= p;
            if (mp[word] == 0 && vis[address] == true)
            {
        
                for (int t = 1; t < MAXNUM; t++)
                {
        
                    if (!vis[(address + t * t) % p])
                    {
        
                        address = (address + t *t) % p;
                        vis[address] = true;
                        mp[word] = address;
                        cout << address;
                        break;
                    }
                    else if (!vis[(address - t * t + p) % p])
                    {
        
                        address = (address - t *t + p) % p;
                        vis[address] = true;
                        mp[word] = address;
                        cout << address;
                        break;
                    }
                }
            }
            /*
            else的内容我不是很明白
            之前我曾分成四种状态，但是最后一份数据过不了
            mp已经存了地址  vis[num]已经被访问 
    		mp已经存了地址  vis[num]没有被访问 （不存在）
    		这个情况好像存在 之前的单词的地址和现在的单词相同 还需要 再散列
    		我好想知道错哪了
    		mp没存存了地址  vis[num]已经被访问 （平方探测）
    		mp没存存了地址  vis[num]没有被访问 （直接存放）
            
    		else这里 如果 mp已经存了地址，
    		为什么要更新 并输出 这次得到的地址
    	
    		我好像想到了一种情况，就是 ABC ACB （八种排列方式）
    		好吧，这几种情况的地址不同
    		同一个word
    		
    		但是 又出现了另外一种情况， 两个字符串 不同 但地址相同
    		那就是 应该 再散列探测的 情况了
    		
    		*/
            else
            {
        
                mp[word] = address;
                cout << address;
                vis[address] = true;
            }
            
            
            if (i < n) cout << ' ';
            else cout << endl;
        }
        system("pause");
        return 0;
    }