在論壇和聊天室這樣的場景里，為了保證用戶體驗，我們經常需要屏蔽很多不良詞語。對于單個關鍵詞查找，自然是indexOf、正則那樣的方式效率比較高。但對于關鍵詞較多的情況下，多次重復調用indexOf、正則的話去匹配全文的話，性能消耗非常大。由于目標字符串通常來說體積都比較大，所以必須要保證一次遍歷就得到結果。根據這樣的需求，很容易就想到對全文每個字符依次匹配的方式。比如對于這段文字：“Mike Jordan had said "Just do IT", so Mark has been a coder.”，假如我們的關鍵詞是“Mike”“Mark”，那么可以遍歷整句話，當找到“M”就接著看能不能匹配到“i”或者“a”，能一直匹配到最后則成功找到一個關鍵詞，否則繼續遍歷。那么關鍵詞的結構就應該是這樣的： 

var keywords = { M: { i: {  k: {  e: {end: true}  } }, a: {  r: {  k: {end: true}  } } }}

由上文可以看出這個數據就是一個樹結構，而根據關鍵詞組來創建樹結構還是比較耗時的，而關鍵詞卻又是我們早已給定的，所以可以在匹配前預先創建這樣的數據結構。代碼如下： 

function buildTree(keywords) { var tblCur = {}, key, str_key, Length, j, i; var tblRoot = tblCur; for(j = keywords.length - 1; j >= 0; j -= 1) { str_key = keywords[j]; Length = str_key.length; for(i = 0; i < Length; i += 1) {  key = str_key.charAt(i);  if(tblCur.hasOwnProperty(key)) {  tblCur = tblCur[key];  } else {  tblCur = tblCur[key] = {};  } } tblCur.end = true; //最后一個關鍵字 tblCur = tblRoot; } return tblRoot;}

 這段代碼中用了一個連等語句：tblCur = tblCur[key] = {}，這里要注意的是語句的執行順序，由于[]的運算級比=高，所以首先是在 tblCur對象中先創建一個key屬性。結合tblRoot = tblCur = {} 看，執行順序就是： 

var tblRoot = tblCur = {};tblRoot = tblCur;tblCur['key'] = undefined; // now tblRoot = {key: undefined}tblCur['key'] = {};tblCur = tblCur['key'];

通過上面的代碼就構建了好了所需的查詢數據，下面看看查詢接口的寫法。 

對于目標字符串的每一字，我們都從這個keywords頂部開始匹配。首先是 keywords[a] ，若存在，則看 keyword[a][b]，若最后 keyword[a][b]…[x]=true 則說明匹配成功，若 keyword[a][b]…[x]=undefined，則從下一個位置重新開始匹配 keywords[a] 。 

function search(content) { var tblCur, p_star = 0, n = content.length, p_end, match, //是否找到匹配 match_key, match_str, arrMatch = [], //存儲結果 arrLength = 0; //arrMatch的長度索引 while(p_star < n) { tblCur = tblRoot; //回溯至根部 p_end = p_star; match_str = ""; match = false; do {  match_key = content.charAt(p_end);  if(!(tblCur = tblCur[match_key])) { //本次匹配結束  p_star += 1;  break;  } else {  match_str += match_key;  }  p_end += 1;  if(tblCur.end) //是否匹配到尾部  {  match = true;  } } while (true); if(match) { //最大匹配  arrMatch[arrLength] = {   key: match_str,  begin: p_star - 1,  end: p_end  };  arrLength += 1;  p_star = p_end; } } return arrMatch;} 

以上就是整個關鍵詞匹配系統的核心。這里很好的用到了js的語言特性，效率非常高。我用一篇50萬字的《搜神記》來做測試，從中查找給定的300個成語，匹配的效果是1秒左右。重要的是，由于目標文本是一次遍歷的，所以目標文本的長短對查詢時間的影響幾乎不計。對查詢時間影響較大的是關鍵詞的數量，目標文本的每個字都遍歷一遍關鍵詞，所以對查詢有一定影響。

簡單分析

看到上文估計你也納悶，對每個字都遍歷一遍所有關鍵詞，就算有些關鍵詞有部分相同，但是完全遍歷也是挺耗時的呀。但js中對象的屬性是使用哈希表來進行構建的，這種結構的數據跟單純的數組遍歷是有很大不同的，效率要比基于順序的數組遍歷高得多。可能有些同學對數據結構不太熟悉，這里我簡單說一下哈希表的相關內容。 

首先看看數據的存儲。

數據在內存的存儲由兩部分組成，一部分是值，另一部分是地址。把內存想象成一本新華字典，那字的解釋就是值，而目錄就是地址。字典里面是按拼音排序的，比如相同發音的“ni”就排在同一塊，也就是說數組整齊排列在一塊內存區域里面，這樣的結構就是數組，你可以指定“ni” 1號，10號來訪問。結構圖如下：

數組的優勢是遍歷簡單，通過下標就能直接訪問相應的數據了。但是它要增刪某一項就非常困難。比如你要把第6項刪掉，那第5項之后的數據都要向前移一個位置。如果你要刪除第一位，整個數組都要移動，消耗非常大。

為了解決數組增刪的問題，鏈表就出現了。如果我們將值分成兩部分，一部分用來儲存原來的值，另一部分用來儲存一個地址，這個地址指向另外一個同樣的結構，以此類推就構成了一個鏈表。結構如下：

從上圖可以明顯看出，對鏈表進行增刪非常簡單，只要把目標項和前一項的next改寫就完成了。但是要查詢某個項的值就非常困難了，你必須依次遍歷才可以訪問到目標位置。

 為了整合這兩種結構的優勢，聰明如你一定想到了下面這種結構。

這種數據結構就是哈希表結構。數組里面存儲鏈表的頭地址，就可以形成一個二維數據表。至于數據如何分布，這個就是哈希算法，正規的翻譯應該是散列算法。算法雖然有很多種，原理上都是通過一個函數對key進行求解，再根據求解得到的結果安放數據。也就是說key和實際地址之間形成了一個映射，所以這個時候我們不再以數組下標或者單純的遍歷來訪問數組，而是以散列函數的反函數來定位數據。js中的對象就是一個哈希結構，比如我們定義一個obj，obj.name通過散列，他在內存中的位置可能是上圖中的90，那我們想要操作obj.name的時候，底層就會自動幫我們通過哈希算法定位到90的位置，也就是說直接從數組的12項開始查找鏈表，而不是從0開始遍歷整個內存塊。

js中定義一個對象obj{key: value}，key是被轉換成字符串然后經過哈希處理得到一個內存地址，然后將值放入其中。這就可以理解為什么我們可以隨意增刪屬性，也能理解為什么在js中還能為數組賦屬性，而且數組也沒有所謂的越界了。

在數據量較大的場合，哈希表具有非常明顯的優勢，因為它通過哈希算法減少了很多不必要的計算。所謂性能優化，其實就是讓計算機少運算；最大的優化，就是不計算！

算法的優化

現在理解算法底層實現，回過頭來就可以考慮對算法進行優化了。不過在優化前還是要強調一句：不要盲目追求性能！比如本案例中，我們最多就是5000字的匹配，那現有算法足矣，所有優化都是不必要的。之所以還來說說優化，就是為了提高自己對算法對程序的理解，而不是真的要去做那1ms的優化。

我們發現我們的關鍵詞都沒有一個字的，那我們按照一個字的單位進行關鍵詞遍歷顯然就是一個浪費了。這里的優化就是預先統計關鍵詞的最大最小長度，每次以最小長度為單位進行查找。比如說我測試用例的關鍵詞是成語，最短都是4個字，那么我每次匹配都是4個字一起匹配，如果命中就繼續深入查找到最大長度。也就是說我們最開始構造樹的時候首先是以最小長度構建的，然后再逐字增加。

 簡單計算一下，按照我們的測試用例，300個成語，我們匹配一個詞只需一次對比，而單字查詢的話我們需要對比4次，而每次對比我們都要訪問我們的樹結構，這就是可避免的性能消耗。更重要的是，這里的對比并不是字符串對比，這里我們的關鍵字都是作為key存在的，效果就是 和key in obj一樣的，都是對key進行哈希變換然后訪問相應的地址！所以千萬不要糾結對比一個字和對比4個字的差異，我們沒對比字符串！

 關于多關鍵詞的匹配就說到這里了，優化版代碼我就不貼了，因為一般也用不到。