写点什么

实操案例:字符串哈希表操作

发布于: 2020 年 07 月 20 日

摘要:当遇到C语言库没有字符串哈希表的时候,该如何进行操作。



有考C语言可信编程认证的同事经常会问到,C语言库没有字符串哈希表操作,那考试遇到了怎么办。虽然历次考试的题目中没有必须要用到C语言哈希表的题目(至少我都能用常规C做出来),但是还需要防患未然,这里给出一道有代表性的题目,可以尝试做做看:https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/



给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配,中间不能有其他字符,但不需要考虑 words 中单词串联的顺序。



示例:
输入:
s = "barfoothefoobarman",
words = ["foo","bar"]
输出:[0,9]
解释:
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。



这题不考虑编程语言的话,用哈希表会比较简单,那要是用C语言的话,可以自己撸个哈希表用,对付这类题目还是绰绰有余的。



思路的话参考https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-6/中的解法二,这里只讲下怎么最简单构造一个哈希表。



首先是选取哈希函数,这里我用的是djb2算法,参考http://www.cse.yorku.ca/~oz/hash.html,碰撞率相当低,分布平衡,实现也很简单,就两三行代码,记住关键数字(5381和33)。



If you just want to have a good hash function, and cannot wait, djb2 is one of the best string hash functions i know. it has excellent distribution and speed on many different sets of keys and table sizes.



Language- 代码



unsigned long
hash(unsigned char *str)
{
unsigned long hash = 5381;

int c;

while (c = *str++)

hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

return hash;

}



有了字符串哈希函数,就能够将大串字符串转换成数字,数字进而可以作为数组的下标(key)存储信息。那么哈希表的大小怎么取呢?一般大小要大于存储的数据个数,比如最多100个数据,存到哈希表的话大小肯定要大于100才行。对于这题而言,没有明确告诉你单词的最大个数,只能估值了,这里经过几轮提交测试,得到哈希表大小与通过用例个数的关系,说明这道题目最多的单词数可能在300左右,平均个数<50个吧:



5 -> 110/173
10 -> 143/173
50 -> 170/173
100 -> 170/173
300 -> 172/173
400 -> 173/173



这里给出我的解答:





C 代码



// 字符串最大值,hash表大小,估值和实际数据个数有关

#define MAXWORDCOUNT 1000


static int wordCount[MAXWORDCOUNT];

static int currWordCount[MAXWORDCOUNT];



// ref: http://www.cse.yorku.ca/~oz/hash.html


unsigned long DJBHash(const char* s, int len) {

unsigned long hash = 5381; // 经验值,hash冲突概率低,分布平衡


while (len--) {

hash = (((hash << 5) + hash) + *(s++)) % MAXWORDCOUNT; /* hash * 33 + c */


}

return hash;


}



int* findSubstring(char * s, char ** words, int wordsSize, int* returnSize){

memset(wordCount, 0, sizeof(wordCount));


*returnSize = 0;



const int kSLen = strlen(s);

if (kSLen == 0 || wordsSize == 0) return NULL;



const int kWordLen = strlen(words[0]);


// 将单词数量存到哈希表中,key: word, value: 单词数量

for (int i = 0; i < wordsSize; ++i)


++wordCount[DJBHash(words[i], kWordLen)];



int *result = malloc(sizeof(int) * kSLen);

for (int i = 0; i < kWordLen; ++i) {


for (int j = i; j + kWordLen * wordsSize <= kSLen; j += kWordLen) {

// 统计当前窗口的单词数量


for (int k = (j == i ? 0 : wordsSize - 1); k < wordsSize; ++k)

++currWordCount[DJBHash(s + j + k * kWordLen, kWordLen)];



// 判断两个哈希表是否相等,即窗口中的单词是否和给定词典完全匹配


if (memcmp(wordCount, currWordCount, sizeof(wordCount)) == 0)

result[(*returnSize)++] = j;



--currWordCount[DJBHash(s + j, kWordLen)];


}

// 哈希表清零操作


memset(currWordCount, 0, sizeof(currWordCount));

}


return result;

}



点击关注,第一时间了解华为云新鲜技术~



发布于: 2020 年 07 月 20 日阅读数: 60
用户头像

提供全面深入的云计算技术干货 2020.07.14 加入

华为云开发者社区,提供全面深入的云计算前景分析、丰富的技术干货、程序样例,分享华为云前沿资讯动态,方便开发者快速成长与发展,欢迎提问、互动,多方位了解云计算! 传送门:https://bbs.huaweicloud.com/

评论

发布
暂无评论
实操案例:字符串哈希表操作