實操案例：字元串哈希表操作

摘要：當遇到C語言庫沒有字元串哈希表的時候，該如何進行操作。

有考C語言可信程式設計認證的同僚經常會問到，C語言庫沒有字元串哈希表操作，那考試遇到了怎麼辦。雖然曆次考試的題目中沒有必須要用到C語言哈希表的題目（至少我都能用正常C做出來），但是還需要防患未然，這裡給出一道有代表性的題目，可以嘗試做做看：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/

給定一個字元串 s 和一些長度相同的單詞 words。找出 s 中恰好可以由 words 中所有單詞串聯形成的子串的起始位置。 注意子串要與 words 中的單詞完全比對，中間不能有其他字元，但不需要考慮 words 中單詞串聯的順序。

這題不考慮程式設計語言的話，用哈希表會比較簡單，那要是用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- 代碼

有了字元串哈希函數，就能夠将大串字元串轉換成數字，數字進而可以作為數組的下标（key）存儲資訊。那麼哈希表的大小怎麼取呢？一般大小要大于存儲的資料個數，比如最多100個資料，存到哈希表的話大小肯定要大于100才行。對于這題而言，沒有明确告訴你單詞的最大個數，隻能估值了，這裡經過幾輪送出測試，得到哈希表大小與通過用例個數的關系，說明這道題目最多的單詞數可能在300左右，平均個數<50個吧：

這裡給出我的解答：

C 代碼

點選關注，第一時間了解華為雲新鮮技術~