哈希表总结

Posted on | In
  • 用数组来实现简单的哈希表，把数组的小标设为哈希表的键值（Key）,而把数组中的每一个数字设为哈希表的值（Value），这样每一个下标及数组中该下标对应的数字就组成了一个键-值的配对，见下方createHash，若字符则更方便用int hash[256] = {0};hash[s[0]] = 出现次数或自己赋予的意义(也可存储当前字符)，这里256相当于hash的size，每次字符%size时即原位置。
应用1：第一个只出现一次的字符

题目描述：在一个字符串中找出第一个只出现一次的字符，如输入”abaccdeff”，输出’b’.
解题思路：
用数组创建一个简单的哈希表来存储每一个字符出现的次数，再次遍历字符串，并用O(1)的时间判断该字符是否只出现了一次

应用2：定义一个函数，输入两个字符串，从第一个字符串中删除在第二个字符串中出现过的所有字符。例如，从第一个字符串“We are stduents”中删除在第二个字符串”aeio”中出现过的字符得到的结果时”W r stdnts”

解题思路：
创建一个用数组实现的简单哈希表来存储第二个字符串，从头到尾扫描第一个字符串的每一个字符时，用O(1)时间判断该字符是不是在第二个字符中

应用3：删除重复字符

定义一个函数，删除字符串中所有重复出现的字符。例如输入”google”,删除重复的字符之后得到”gole”

解题思路：
创建一个用布尔型数组实现的简单哈希表，数组中的元素的意义是其下标看做ASCII码后对应的字母在字符串中是否已经出现

应用4：变位词判断

在英语中，如果两个单词中出现的字母相同，并且每个字母出现的次数也相同，那么这两个单词互为变为词（Anagram），例如silent和listen，evil和live等为变位词

解题思路：
创建一个数组实现的简单哈希表，用来统计字符串出现的次数，当扫描到第一个字符串中的每一字符时，为哈希表对应的项的值加1，接下来扫描第二个字符串，扫描到每个字符串时，为哈希表中对应的项的值减1，如果扫描第二个字符串后，哈希表中所有的值都为0，那么这两个字符串就互为变为词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
vector<int> createHash(const vector<int> array){
    size_t size = array.size();
    vector<int> hash(size, -1);
    for (int i = 0; i < array.size(); i++) {
        int idx = array[i] % size;
        while(hash[idx] != -1)
            idx = (idx + 1) % size;
        hash[idx] = array[i];
    }
    return hash;
}

int findSingleAlphabat(string s){
    int array[256] = {0};
    //这里不考虑大小即没有除余，有限的key,key直接当地址来索引
    //标准hash存自然数无限长度，关键字除余映射到地址
    //地址即数组下标，地址中存放出现次数
    for (int i = 0; i < s.size(); i++) {
        array[s[i]]++;
    }
    for (int i = 0; i < s.size(); i++) {
        if(array[s[i]] == 1)
            return i;
    }
    return -1;
}

string deleteSubChar(const string &s1, const string &s2){
    string result;
    int hash[256] = {0};
    for (size_t i = 0; i < s2.size(); i++)
        hash[s2[i]] = 1;
    
    for (size_t i = 0; i < s1.size(); i++)
        if(hash[s1[i]] == 0) result.push_back(s1[i]);
    
    return result;
}

void deleteStrDuplication(string &str){
    vector<int> temp(str.size());
    size_t i = 0;
    for (i = 0; i < str.size(); i++) {
        temp[i] = str[i] - 'a';
    }
    vecdeleteDuplication(temp);
    
    for (i = 0; i < temp.size(); i++) {
        str[i] = temp[i] + 'a';
    }
    str.erase(str.begin() + temp.size(), str.end());
    return;
}

void vecdeleteDuplication(vector<int> &array){
    size_t size = array.size();
    int count = 0;
    vector<int> hash(size, -1);
    
    for (int i = 0; i < size; i++)
        if(hash[array[i] % size] == -1){
            //hash表里取值任意，可以取简单的数量，区分非初始值即可
            hash[array[i] % size] = array[i];
            array[count++] = array[i];
        }
    //在原array操作；也可以新建一个vector在后面添加,return vec
    array.resize(count);
}

bool Anagram(const string &s1, const string &s2){
    //字符串的hash用静态数组即可
    int hash[256] = {0};
    for (int i = 0; i <s1.size(); i++)
        hash[s1[i]]++;
    
    for (int i = 0; i < s2.size(); i++)
        hash[s2[i]]--;
    
    for(int i = 0; i < 256; i++)
        if(hash[i] != 0) return false;
    return true;
}