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

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

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

总体的hash学习导图如下：

在这里插入图片描述

文章目录

- - - 定义
    - 分类
    - - 字符hash
      - 排序hash
      - 链式hash（解决hash冲突）
      - 创建链式hash
        查找指定数值
      - STL map(hash)
      - 哈希分类完整测试代码
    - 应用（常见题目）
    - - 1. 回文字符串（Longest Palindrome）
      - 2. 词语模式(Word Pattern)
      - 3. 同字符词语分组(Group Anagrams)

定义

需要拥有关键字 key
维护一个key和value的映射关系，哈希函数
最终的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]
",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 
#include  
#include 
#include 
#include 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]
",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("
");}cout << endl;for (int i =0;i < 10; ++i) { if (search(hash_table, i, TABEL_LEN)) { printf("%d is in the hash_table
",i);} else { printf("%d is not int the hash_table
",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 
#include  
#include 
#include 
#include 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 
#include  
#include 
#include 
#include 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 
#include  
#include 
#include 
#include 
#include 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 的存储映射*/
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 ]