摘要：当遇到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 longhash(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/17310 -> 143/17350 -> 170/173100 -> 170/173300 -> 172/173400 -> 173/173

这里给出我的解答：

C 代码

// 字符串最大值，hash表大小，估值和理论数据个数无关#define MAXWORDCOUNT 1000static int wordCount[MAXWORDCOUNT];static int currWordCount[MAXWORDCOUNT];// ref: http://www.cse.yorku.ca/~oz/hash.htmlunsigned 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;}

点击关注，第一工夫理解华为云陈腐技术~