[C++知识库]哈希表的使用

哈希表一般用于存储键值对即key-val

一般是由数组和链表构成

常用操作

//查找是否存在键值
unordered_map<int,int> hash;
hash.find(key)==hash.end();
hash.count(key)==1;

例题

290. Word Pattern

由于C++中的哈希表不能查找某一值的存在，只能查找某一键是否存在，所以C++需要两个哈希表来相互存储。

class Solution {
public:
    //将字符串传入到数组中
    vector<string> split(string &s) {
	    string temp;
	    vector<string> v;
	    for (int i = 0; i < s.size(); i++) {
		    if (s[i] != ' ')temp += s[i];
		    else {
			v.push_back(temp);
			temp = "";
		    }
	    }
	    v.push_back(temp);
	    return v;
    }

    bool wordPattern(string pattern, string s) {
        //两个哈希表双向存储
        //事实上如果C++STL中如果有类似于java的containsKey函数，只需要一个哈希表就足够
        unordered_map<string,char> hash1;
        unordered_map<char,string> hash2;
        vector<string> v = split(s);

        if(v.size()!=pattern.size()) return false;  

        for(int i=0;i<pattern.size();i++){
             //如果存在并且相互对应
            if(hash1.count(v[i]) && hash2[pattern[i]] != v[i]) return false;

            if(hash2.count(pattern[i]) && hash1[v[i]] != pattern[i]) return false;
            
            //双向映射
            hash1[v[i]] = pattern[i];

            hash2[pattern[i]] = v[i];
            
        }
        return true;
    }
};

?C++中没有split函数对字符串进行划片，手写辅助函数split()。

未完待续！