哈希表的分类，创建，查找 以及相关问题解决

总体的hash学习导图如下：

定义

1. 需要拥有关键字 key
2. 维护一个key和value的映射关系，哈希函数
3. 最终的hash表拥有直接通过key访问值的能力

分类

字符hash

/*count letters*/
void hash_char() {int char_map[128] = {0};string s = "aabbbcddeh";for (int i = 0;i < s.length(); ++i) {char_map[s[i]] ++;}for (int i = 0;i < 128; ++i) {if (char_map[i] > 0) {printf("[%c] [%d]\n",i,char_map[i]);}}
}

排序hash

void hash_sort() {int arr[] = {1,100,2,6,998,532,40};int hash_arr[999] = {0};for (int i = 0;i < 7; ++i) {hash_arr[arr[i]] ++;}for (int i = 0;i < 999; i++) {if (hash_arr[i] > 0) {cout << i << endl;}}
}

链式hash（解决hash冲突）

创建链式hash

struct HashNode
{int data;struct HashNode *next;HashNode(int x):data(x),next(NULL){}
};int get_key(int key, int tabel_len) {return key % tabel_len;
}void insert_hash(HashNode *hash_table[], HashNode *node, int tabel_len) {int key = get_key(node -> data, tabel_len);node ->next = hash_table[key];hash_table[key] = node ;
}

查找指定数值

int get_key(int key, int tabel_len) {return key % tabel_len;
}bool search(HashNode *hash_table[], int value, int tabel_len) {int key = get_key(value,tabel_len);HashNode *head = hash_table[key];while(head) {if (head -> data == value) {return true;}head = head -> next;}return false;
}

STL map(hash)

void stl_hash() {std::map<string, int> map;string a[3] = {"aaa","ssss","ddd"};map[a[0]] = 1;map[a[1]] = 100;map[a[2]] = 301;cout << "stl hash_table is " << endl;for (std::map<string, int>::iterator it = map.begin(); it != map.end(); it ++) {cout << "[" << it -> first.c_str() << "] :" << it -> second << endl; }if (map.find(a[1]) != map.end()) {cout << "sss is in the stl map "  << map[a[1]]<< endl;}
}

哈希分类 完整测试代码

#include <iostream>
#include <vector> 
#include <string>
#include <map>
#include <stdio.h>using namespace std;struct HashNode
{int data;struct HashNode *next;HashNode(int x):data(x),next(NULL){}
};/*count letters*/
void hash_char() {int char_map[128] = {0};string s = "aabbbcddeh";for (int i = 0;i < s.length(); ++i) {char_map[s[i]] ++;}for (int i = 0;i < 128; ++i) {if (char_map[i] > 0) {printf("[%c] [%d]\n",i,char_map[i]);}}
}void hash_sort() {int arr[] = {1,100,2,6,998,532,40};int hash_arr[999] = {0};for (int i = 0;i < 7; ++i) {hash_arr[arr[i]] ++;}for (int i = 0;i < 999; i++) {if (hash_arr[i] > 0) {cout << i << endl;}}
}int get_key(int key, int tabel_len) {return key % tabel_len;
}void insert_hash(HashNode *hash_table[], HashNode *node, int tabel_len) {int key = get_key(node -> data, tabel_len);node ->next = hash_table[key];hash_table[key] = node ;
}bool search(HashNode *hash_table[], int value, int tabel_len) {int key = get_key(value,tabel_len);HashNode *head = hash_table[key];while(head) {if (head -> data == value) {return true;}head = head -> next;}return false;
}void stl_hash() {std::map<string, int> map;string a[3] = {"aaa","ssss","ddd"};map[a[0]] = 1;map[a[1]] = 100;map[a[2]] = 301;cout << "stl hash_table is " << endl;for (std::map<string, int>::iterator it = map.begin(); it != map.end(); it ++) {cout << "[" << it -> first.c_str() << "] :" << it -> second << endl; }if (map.find(a[1]) != map.end()) {cout << "sss is in the stl map "  << map[a[1]]<< endl;}
}int main(int argc, char const *argv[])
{cout << "hash_char" << endl;hash_char();cout << "hash_sort" << endl;hash_sort();const int TABEL_LEN = 11;HashNode *hash_table[TABEL_LEN] = {0};std::vector<HashNode *> hash_node_vec;int test[8] = {1,100,2,6,998,532,40,1};for (int i = 0;i < 8; ++i) {hash_node_vec.push_back(new HashNode(test[i]));}for (int i = 0;i < hash_node_vec.size(); ++i) {insert_hash(hash_table,hash_node_vec[i],TABEL_LEN);}cout << "hash_table" << endl;for (int i = 0;i < TABEL_LEN; ++i) {printf("[%d] ",i);HashNode *head = hash_table[i];while(head) {printf("-> %d", head->data);head = head -> next;}printf("\n");}cout << endl;for (int i =0;i < 10; ++i) {if (search(hash_table, i, TABEL_LEN)) {printf("%d is in the hash_table\n",i);} else {printf("%d is not int the hash_table\n",i);}}stl_hash();return 0;
}

输出如下:

hash_char
[a] [2]
[b] [3]
[c] [1]
[d] [2]
[e] [1]
[h] [1]
hash_sort
1
2
6
40
100
532
998
hash_table
[0] 
[1] -> 1-> 100-> 1
[2] -> 2
[3] 
[4] -> 532
[5] 
[6] -> 6
[7] -> 40
[8] -> 998
[9] 
[10] 0 is not int the hash_table
1 is in the hash_table
2 is in the hash_table
3 is not int the hash_table
4 is not int the hash_table
5 is not int the hash_table
6 is in the hash_table
7 is not int the hash_table
8 is not int the hash_table
9 is not int the hash_table
stl hash_table is 
[aaa] :1
[ddd] :301
[ssss] :100
sss is in the stl map 100

应用（常见题目）

1. 回文字符串（Longest Palindrome）

问题如下:
已知一个只包括大小写字符的 字符串，求用该字符串中的字符可以生 成的最长回文字符串长度。
例如 s = “abccccddaa”，可生成的 最长回文 字符串长度为 9，如 dccaaaccd、 adccbccda、 acdcacdca等，都是正确的。

代码实现如下:

#include <iostream>
#include <vector> 
#include <string>
#include <map>
#include <stdio.h>using namespace std;/*
已知一个只包括大小写字符的 字符串，求用该字符串中的字符可以生 成的最长回文字符串长度。
例如 s = “abccccddaa”，可生成的 最长回文 字符串长度为 9，如 dccaaaccd、 adccbccda、 acdcacdca等，都是正确的。
*/int max_count_palindrome(string s) {if (s.length() == 0) {return 0;}int hash_table[128] = {0};int max_count = 0;int flag = 0;for (int i = 0; i < s.length(); ++i) {if ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z')) {hash_table[s[i]] ++;} else {return -1;}}for (int i = 0;i < 128; ++i) {if (hash_table[i] > 0 ) {if(hash_table[i] % 2 == 0) {max_count += hash_table[i];} else {max_count += hash_table[i] - 1;flag = 1;}}}return max_count + flag;
}int main(int argc, char const *argv[])
{string s;cin >> s; cout << max_count_palindrome(s) << endl;return 0;
}

输出如下:

abccccddaabb
11

2. 词语模式(Word Pattern)

问题描述如下：

已知字符串pattern与字符串str，确认str是否与pattern匹配。
str与pattern匹配代表字符 串str中的单词与pattern中的字符一一对应。(其中pattern中只包含小写字符，str中
的单词只包含小写字符，使用空格分隔。) 例如，
pattern = “abba”, str = “dog cat cat dog” 匹配.
pattern = “abba”, str = “dog cat cat fish” 不匹配.
pattern = “aaaa”, str = "dog cat cat dog"不匹配.
pattern = “abba”, str = "dog dog dog dog"不匹配.

实现如下:

#include <iostream>
#include <vector> 
#include <string>
#include <map>
#include <stdio.h>using namespace std;/*
已知字符串pattern与字符串str，确认str是否与pattern匹配。
str与pattern匹配代表字符 串str中的单词与pattern中的字符一一对应。(其中pattern中只包含小写字符，str中
的单词只包含小写字符，使用空格分隔。) 例如，
pattern = “abba”, str = “dog cat cat dog” 匹配. 
pattern = “abba”, str = “dog cat cat fish” 不匹配. 
pattern = "aaaa", str = "dog cat cat dog"不匹配. 
pattern = "abba", str = "dog dog dog dog"不匹配.
*/bool judge_word_partten(string partten, string str) {if ((partten.length() == 0 && str.length() != 0)  || (str.length() == 0)) {return false;}std::map<string, char> hash_table;int used[128] = {0};str.push_back(' ');int i = 0;int j = 0;string tmp = "";cout << partten << " " << str << endl;for(int j = 0;j < str.length(); ++j){if (str[j] == ' ') {if (hash_table.find(tmp) == hash_table.end()) {if (used[partten[i]]) {return false;}used[partten[i]] = 1;hash_table[tmp] = partten[i];} else {if (hash_table[tmp] != partten[i]) {return false;}}tmp = "";i++;} else {tmp += str[j];}}if (i != partten.length()) {return false;}return true;
}int main(int argc, char const *argv[])
{/* code */string partten = "abba";string str = "dog cat cat do";cout << judge_word_partten(partten,str) << endl;return 0;
}

输出如下:

abba 
dog cat cat do 
0abba 
dog cat cat dog 
1

3. 同字符词语分组(Group Anagrams)

问题描述：
已知一组字符串，将所有anagram(由颠倒字母顺序而构成的 字)放到一起输出。
例如:[“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] :[“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
返回:[ [“ate”, “eat”,“tea”], [“nat”,“tan”], :[ [“ate”, “eat”,“tea”], [“nat”,“tan”],[“bat”] ]

实现如下:

#include <iostream>
#include <vector> 
#include <string>
#include <map>
#include <algorithm>
#include <stdio.h>using namespace std;/*
已知一组字符串，将所有anagram(由颠倒字母顺序而构成的 字)放到一起输出。
例如:["eat", "tea", "tan", "ate", "nat", "bat"] :["eat", "tea", "tan", "ate", "nat", "bat"]
返回:[ ["ate", "eat","tea"], ["nat","tan"], :[ ["ate", "eat","tea"], ["nat","tan"],["bat"] ]
*//*map 建立 string to vector<sting> 的存储映射*/
std::vector<std::vector<string>> get_group_anagrams(std::vector<string> &str) {std::map<string, std::vector<string> > hash_table;string tmp;std::vector<std::vector<string>> result;for (int i = 0;i < str.size(); ++i){tmp = str[i];sort(tmp.begin(), tmp.end());if (hash_table.find(tmp) != hash_table.end()) {hash_table[tmp].push_back(str[i]);} else {std::vector<string> item;item.push_back(str[i]);hash_table[tmp] = item;}}std::map<string, std::vector<string> >::iterator it = hash_table.begin();for (;it != hash_table.end(); ++it) {result.push_back(it->second);}return result;
}int main(int argc, char const *argv[])
{/* code */std::vector<string> str;for (int i = 0;i < 6; ++i) {string tmp;cin >> tmp;str.push_back(tmp);}std::vector<std::vector<string> > result = get_group_anagrams(str);for (int i = 0;i < result.size(); ++i) {for (int j = 0;j < result[i].size(); ++j) {cout << "[" << result[i][j] << " ] ";}cout << endl;}return 0;
}

输出如下:

ate eat tea tan nat bat
[bat ] 
[ate ] [eat ] [tea ] 
[tan ] [nat ]