해시법의 이용-2(나선본)

해본 일
이전 기사https://qiita.com/KenziTajima/items/e3ab73c23eee1e22895f에 올라온 리뷰를 참고해 AOJ의 질문ALDS1_4_C: Dictionary에 재도전한다.
개선된 일
다음과 같은 점이 개선되었습니다.

Pow() 사용하지 않음

용기를 맵에서vector

로 변경
다음 소스 코드

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort((c).begin(), (c).end())
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

using namespace std;

#define M 1777771

int hash_1(int kay)
{
    return kay % M;
}
int hash_2(int kay) { return 1 + (kay % (M - 1)); }

int get_Kay(string str)
{
    int k = 0;
    REP(i, (int)str.length())
    {
        k += (int)str[i] + i * 5;
    }
    return k;
}

int hash_Insert(string str, vector<string> data)
{
    int i = 0;
    int hashed_Kay;
    int kay = get_Kay(str);
    while (true)
    {
        hashed_Kay = (hash_1(kay) + i * hash_2(kay)) % M;
        if (data[hashed_Kay] == "" or data[hashed_Kay] == str)
            return hashed_Kay;
        i++;
    }
}

bool hash_Find(string str, vector<string> data)
{
    int i = 0;
    int hashed_Kay;
    int kay = get_Kay(str);
    while (true)
    {
        hashed_Kay = (hash_1(kay) + i * hash_2(kay)) % M;
        if (data[hashed_Kay] == str)
            return true;
        else if (data[hashed_Kay] == "")
            return false;
        i++;
    }
}

int main()
{
    int n;
    cin >> n;

    string op, word;
    vector<string> data(1000000);

    REP(_, n)
    {
        cin >> op >> word;
        if (op[0] == 'i')
            data[hash_Insert(word, data)] = word;
        else if (hash_Find(word, data))
            cout << "yes"
                 << "\n";
        else
            cout << "no"
                 << "\n";
    }
}

결실
아직 안 된다

고찰하다.
나는 지난번에 제시한 원본 코드에 오류가 있는 것을 발견했다.
while 순환 변수 i가 증가하지 않았습니다.(왜 중간에 AC를 사용합니까?)
그래서 무한순환에 빠진 것으로 여겨진다.

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort((c).begin(), (c).end())
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

using namespace std;

#define M 1777771

class Dictionary{
    private:
        vector<string> data;
        map<int, string> m;
    public:
        void insert(string str);
        void hash_Insert(string str);
        bool find(string str);
        bool hash_Find(string str);
        int get_Kay(string str);
        int hash_1(int kay);
        int hash_2(int kay);
};

int Dictionary::hash_1(int kay){ return kay%M; }
int Dictionary::hash_2(int kay){ return 1+(kay%(M-1)); }

int Dictionary::get_Kay(string str){
    int k = 0;
    REP(i, (int)str.length()){
        k += (int)str[i] * pow(5, i);
    }
    return k;
}

void Dictionary::insert(string str){
    if (!Dictionary::find(str)) data.PB(str);
}
void Dictionary::hash_Insert(string str){
    int i = 0;
    int hashed_Kay;
    int kay = get_Kay(str);
    while(true){
        hashed_Kay = hash_1(kay) + i*hash_2(kay);
        if(m[hashed_Kay] == "" or m[hashed_Kay] == str) break;
        //ここにi++;と書くべきだった
    }
    m[hashed_Kay] = str;
}

bool Dictionary::find(string str){
    if(std::find(ALL(data), str) != data.end()) return true;
    else return false;
}
bool Dictionary::hash_Find(string str){
    int i = 0;
    int hashed_Kay;
    int kay = get_Kay(str);
    while(true){
        hashed_Kay = hash_1(kay) + i*hash_2(kay);
        if(m[hashed_Kay] == str) return true;
        else if(m[hashed_Kay].length() == 0) return false;
        //ここにi++;と書くべきだった
    }
}

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    string op, word;
    Dictionary dic;

    REP(_, n){
        cin >> op >> word; 
        if (op[0] == 'i') dic.hash_Insert(word);
        else if(dic.hash_Find(word)) cout << "yes" << "\n";
        else cout << "no" << "\n";
    }  
}

나는 그 잘못을 수정함으로써 통과했다.