1、elasticsearch 了解多少毅往，說說你們公司 es 的集群架構牵咙，索引數據大小，分片有多少攀唯，以及一些調優(yōu)手段 洁桌。

面試官：想了解應聘者之前公司接觸的 ES 使用場景、規(guī)模革答，有沒有做過比較大

規(guī)模的索引設計战坤、規(guī)劃、調優(yōu)残拐。

解答：

如實結合自己的實踐場景回答即可途茫。

比如：ES 集群架構 13 個節(jié)點，索引根據通道不同共 20+索引溪食，根據日期囊卜，每日

遞增 20+，索引：10 分片错沃，每日遞增 1 億+數據栅组，

每個通道每天索引大小控制：150GB 之內。

僅索引層面調優(yōu)手段：

1.1枢析、設計階段調優(yōu)

1玉掸、根據業(yè)務增量需求，采取基于日期模板創(chuàng)建索引醒叁，通過 roll over API 滾動索

引司浪；

2、使用別名進行索引管理把沼；

3啊易、每天凌晨定時對索引做 force_merge 操作，以釋放空間饮睬；

4回窘、采取冷熱分離機制宪萄，熱數據存儲到 SSD，提高檢索效率；冷數據定期進行 shrink 操作抒钱，以縮減存儲建炫；

5酌儒、采取 curator 進行索引的生命周期管理阅羹；

6、僅針對需要分詞的字段矾克，合理的設置分詞器页慷；

7憔足、Mapping 階段充分結合各個字段的屬性，是否需要檢索酒繁、是否需要存儲等滓彰。……..

1.2州袒、寫入調優(yōu)

1揭绑、寫入前副本數設置為 0；

2郎哭、寫入前關閉 refresh_interval 設置為-1他匪，禁用刷新機制；

3夸研、寫入過程中：采取 bulk 批量寫入邦蜜；

4、寫入后恢復副本數和刷新間隔亥至；

5悼沈、盡量使用自動生成的 id。

1.3姐扮、查詢調優(yōu)

1絮供、禁用 wildcard；

2茶敏、禁用批量 terms（成百上千的場景）壤靶；

3、充分利用倒排索引機制惊搏，能 keyword 類型盡量 keyword萍肆；

4、數據量大時候胀屿，可以先基于時間敲定索引再檢索；

5包雀、設置合理的路由機制宿崭。

1.4、其他調優(yōu)

部署調優(yōu)才写，業(yè)務調優(yōu)等葡兑。

上面的提及一部分，面試者就基本對你之前的實踐或者運維經驗有所評估了赞草。

2讹堤、elasticsearch 的倒排索引是什么

面試官：想了解你對基礎概念的認知。

解答：通俗解釋一下就可以厨疙。 傳統(tǒng)的我們的檢索是通過文章洲守，逐個遍歷找到對應關鍵詞的位置。 而倒排索引，是通過分詞策略梗醇，形成了詞和文章的映射關系表知允，這種詞典+映射表 即為倒排索引。

有了倒排索引叙谨，就能實現 o（1）時間復雜度的效率檢索文章了温鸽，極大的提高了檢索效率。

學術的解答方式：

倒排索引手负，相反于一篇文章包含了哪些詞涤垫，它從詞出發(fā)，記載了這個詞在哪些文 檔中出現過竟终，由兩部分組成——詞典和倒排表蝠猬。

加分項：倒排索引的底層實現是基于：FST（Finite State Transducer）數據結構。

lucene 從 4+版本后開始大量使用的數據結構是 FST衡楞。FST 有兩個優(yōu)點：

1吱雏、空間占用小。通過對詞典中單詞前綴和后綴的重復利用瘾境，壓縮了存儲空間歧杏；

2、查詢速度快迷守。O(len(str))的查詢時間復雜度犬绒。

3、elasticsearch 索引數據多了怎么辦兑凿，如何調優(yōu)凯力，部署

面試官：想了解大數據量的運維能力。

解答：索引數據的規(guī)劃礼华，應在前期做好規(guī)劃咐鹤，正所謂“設計先行，編碼在后”圣絮， 這樣才能有效的避免突如其來的數據激增導致集群處理能力不足引發(fā)的線上客戶 檢索或者其他業(yè)務受到影響祈惶。

如何調優(yōu)，正如問題 1 所說扮匠，這里細化一下：

3.1 動態(tài)索引層面

基于模板+時間+rollover api 滾動創(chuàng)建索引捧请，舉例：設計階段定義：blog 索 引的模板格式為：blog_index_時間戳的形式，每天遞增數據棒搜。

這樣做的好處：不至于數據量激增導致單個索引數據量非常大疹蛉，接近于上線 2 的 32 次冪-1，索引存儲達到了 TB+甚至更大力麸。

一旦單個索引很大可款，存儲等各種風險也隨之而來育韩，所以要提前考慮+及早避免。

3.2 存儲層面

冷熱數據分離存儲筑舅，熱數據（比如最近 3 天或者一周的數據）座慰，其余為冷數據。 對于冷數據不會再寫入新數據翠拣，可以考慮定期 force_merge 加 shrink 壓縮操作版仔， 節(jié)省存儲空間和檢索效率。

3.3 部署層面

一旦之前沒有規(guī)劃误墓，這里就屬于應急策略蛮粮。

結合 ES 自身的支持動態(tài)擴展的特點，動態(tài)新增機器的方式可以緩解集群壓力谜慌，注意：如果之前主節(jié)點等規(guī)劃合理然想，不需要重啟集群也能完成動態(tài)新增的。

4欣范、elasticsearch 是如何實現 master 選舉的

面試官：想了解 ES 集群的底層原理变泄，不再只關注業(yè)務層面了。

解答： 前置前提：

1恼琼、只有候選主節(jié)點（master：true）的節(jié)點才能成為主節(jié)點妨蛹。

2、最小主節(jié)點數（min_master_nodes）的目的是防止腦裂晴竞。

這個我看了各種網上分析的版本和源碼分析的書籍蛙卤，云里霧里。 核對了一下代碼噩死，核心入口為 findMaster颤难，選擇主節(jié)點成功返回對應 Master，否 則返回 null已维。選舉流程大致描述如下：

第一步：確認候選主節(jié)點數達標行嗤，elasticsearch.yml 設置的值discovery.zen.minimum_master_nodes；

第二步：比較：先判定是否具備 master 資格垛耳，具備候選主節(jié)點資格的優(yōu)先返回昂验； 若兩節(jié)點都為候選主節(jié)點，則 id 小的值會主節(jié)點艾扮。注意這里的 id 為 string 類型。

題外話：獲取節(jié)點 id 的方法

1GET /_cat/nodes?v&h=ip,port,heapPercent,heapMax,id,name
2ip port heapPercent heapMax id name

5占婉、詳細描述一下 Elasticsearch 索引文檔的過程

面試官：想了解 ES 的底層原理泡嘴，不再只關注業(yè)務層面了。

解答： 這里的索引文檔應該理解為文檔寫入 ES逆济，創(chuàng)建索引的過程酌予。 文檔寫入包含：單文檔寫入和批量 bulk 寫入磺箕，這里只解釋一下：單文檔寫入流程。

記住官方文檔中的這個圖抛虫。

第一步：客戶寫集群某節(jié)點寫入數據松靡，發(fā)送請求。（如果沒有指定路由/協(xié)調節(jié)點建椰， 請求的節(jié)點扮演路由節(jié)點的角色雕欺。）

第二步：節(jié)點 1 接受到請求后，使用文檔_id 來確定文檔屬于分片 0棉姐。請求會被轉 到另外的節(jié)點屠列，假定節(jié)點 3。因此分片 0 的主分片分配到節(jié)點 3 上伞矩。

第三步：節(jié)點 3 在主分片上執(zhí)行寫操作笛洛，如果成功，則將請求并行轉發(fā)到節(jié)點 1 和節(jié)點 2 的副本分片上乃坤，等待結果返回苛让。所有的副本分片都報告成功，節(jié)點 3 將 向協(xié)調節(jié)點（節(jié)點 1）報告成功湿诊，節(jié)點 1 向請求客戶端報告寫入成功狱杰。

如果面試官再問：第二步中的文檔獲取分片的過程？

回答：借助路由算法獲取枫吧，路由算法就是根據路由和文檔 id 計算目標的分片 id 的過程浦旱。

1shard = hash(_routing) % (num_of_primary_shards)

6、詳細描述一下 Elasticsearch 搜索的過程九杂？

面試官：想了解 ES 搜索的底層原理颁湖，不再只關注業(yè)務層面了。

解答：

搜索拆解為“query then fetch” 兩個階段例隆。

query 階段的目的：定位到位置甥捺，但不取。

步驟拆解如下：

1镀层、假設一個索引數據有 5 主+1 副本 共 10 分片镰禾，一次請求會命中（主或者副本 分片中）的一個。

2唱逢、每個分片在本地進行查詢吴侦，結果返回到本地有序的優(yōu)先隊列中。

3坞古、第 2）步驟的結果發(fā)送到協(xié)調節(jié)點备韧，協(xié)調節(jié)點產生一個全局的排序列表。

fetch 階段的目的：取數據痪枫。

路由節(jié)點獲取所有文檔织堂，返回給客戶端叠艳。

7、Elasticsearch 在部署時易阳，對 Linux 的設置有哪些優(yōu)化方法

面試官：想了解對 ES 集群的運維能力附较。

解答：

1、關閉緩存 swap;

2潦俺、堆內存設置為：Min（節(jié)點內存/2, 32GB）;

3拒课、設置最大文件句柄數；

4黑竞、線程池+隊列大小根據業(yè)務需要做調整捕发；

5、磁盤存儲 raid 方式——存儲有條件使用 RAID10很魂，增加單節(jié)點性能以及避免單 節(jié)點存儲故障扎酷。

8、lucence 內部結構是什么遏匆？

面試官：想了解你的知識面的廣度和深度法挨。

解答：

Lucene 是有索引和搜索的兩個過程，包含索引創(chuàng)建幅聘，索引凡纳，搜索三個要點〉圯铮可以

基于這個脈絡展開一些荐糜。

最近面試一些公司，被問到的關于 Elasticsearch 和搜索引擎相關的問題葛超，以及自

己總結的回答暴氏。

9、Elasticsearch 是如何實現 Master 選舉的绣张？

1答渔、Elasticsearch 的選主是 ZenDiscovery 模塊負責的，主要包含 Ping（節(jié)點之 間通過這個 RPC 來發(fā)現彼此）和 Unicast（單播模塊包含一個主機列表以控制哪 些節(jié)點需要 ping 通）這兩部分侥涵；

2沼撕、對所有可以成為 master 的節(jié)點（node.master: true）根據 nodeId 字典排 序，每次選舉每個節(jié)點都把自己所知道節(jié)點排一次序芜飘，然后選出第一個（第 0 位） 節(jié)點务豺，暫且認為它是 master 節(jié)點。

3嗦明、如果對某個節(jié)點的投票數達到一定的值（可以成為 master 節(jié)點數 n/2+1）并 且該節(jié)點自己也選舉自己冲呢，那這個節(jié)點就是 master。否則重新選舉一直到滿足上 述條件。

4敬拓、補充：master 節(jié)點的職責主要包括集群、節(jié)點和索引的管理裙戏，不負責文檔級 別的管理乘凸；data 節(jié)點可以關閉 http 功能*。

10累榜、Elasticsearch 中的節(jié)點（比如共 20 個）营勤，其中的 10 個 選了一個 master，另外 10 個選了另一個 master壹罚，怎么辦葛作？

1、當集群 master 候選數量不小于 3 個時猖凛，可以通過設置最少投票通過數量 （discovery.zen.minimum_master_nodes）超過所有候選節(jié)點一半以上來解 決腦裂問題赂蠢；

2、當候選數量為兩個時辨泳，只能修改為唯一的一個 master 候選虱岂，其他作為 data 節(jié)點，避免腦裂問題菠红。

11第岖、客戶端在和集群連接時，如何選擇特定的節(jié)點執(zhí)行請求的试溯？

1蔑滓、TransportClient 利用 transport 模塊遠程連接一個 elasticsearch 集群。它并 不加入到集群中遇绞，只是簡單的獲得一個或者多個初始化的 transport 地址键袱，并以 輪 詢 的方式與這些地址進行通信。

12试读、詳細描述一下 Elasticsearch 索引文檔的過程杠纵。

協(xié)調節(jié)點默認使用文檔 ID 參與計算（也支持通過 routing），以便為路由提供適的分片钩骇。

shard = hash(document_id) % (num_of_primary_shards)

1比藻、當分片所在的節(jié)點接收到來自協(xié)調節(jié)點的請求后，會將請求寫入到 Memory Buffer倘屹，然后定時（默認是每隔 1 秒）寫入到 Filesystem Cache银亲，這個從 Momery Buffer 到 Filesystem Cache 的過程就叫做 refresh；

2纽匙、當然在某些情況下务蝠，存在 Momery Buffer 和 Filesystem Cache 的數據可能會 丟失，ES 是通過 translog 的機制來保證數據的可靠性的烛缔。其實現機制是接收到請 求后馏段，同時也會寫入到 translog 中轩拨，當 Filesystem cache 中的數據寫入到磁盤中 時，才會清除掉院喜，這個過程叫做 flush亡蓉；

3、在 flush 過程中喷舀，內存中的緩沖將被清除砍濒，內容被寫入一個新段，段的 fsync 將創(chuàng)建一個新的提交點硫麻，并將內容刷新到磁盤爸邢，舊的 translog 將被刪除并開始個新的 translog。

4拿愧、flush 觸發(fā)的時機是定時觸發(fā)（默認 30 分鐘）或者 translog 變得太大（默認 為 512M）時杠河；

補充：關于 Lucene 的 Segement：

1、Lucene 索引是由多個段組成赶掖，段本身是一個功能齊全的倒排索引感猛。

2、段是不可變的奢赂，允許 Lucene 將新的文檔增量地添加到索引中陪白，而不用從頭重 建索引。

3膳灶、對于每一個搜索請求而言咱士，索引中的所有段都會被搜索，并且每個段會消耗 CPU 的時鐘周轧钓、文件句柄和內存序厉。這意味著段的數量越多，搜索性能會越低毕箍。

4弛房、為了解決這個問題，Elasticsearch 會合并小段到一個較大的段而柑，提交新的合并 段到磁盤文捶，并刪除那些舊的小段。

13媒咳、詳細描述一下 Elasticsearch 更新和刪除文檔的過程粹排。

1、刪除和更新也都是寫操作涩澡，但是 Elasticsearch 中的文檔是不可變的顽耳，因此不 能被刪除或者改動以展示其變更；

2、磁盤上的每個段都有一個相應的.del 文件射富。當刪除請求發(fā)送后膝迎，文檔并沒有真 的被刪除，而是在.del 文件中被標記為刪除胰耗。該文檔依然能匹配查詢弄抬，但是會在 結果中被過濾掉。當段合并時宪郊，在.del 文件中被標記為刪除的文檔將不會被寫入 新段。

3拖陆、在新的文檔被創(chuàng)建時弛槐，Elasticsearch 會為該文檔指定一個版本號，當執(zhí)行更新 時依啰，舊版本的文檔在.del 文件中被標記為刪除乎串，新版本的文檔被索引到一個新段。 舊版本的文檔依然能匹配查詢速警，但是會在結果中被過濾掉叹誉。

14、詳細描述一下 Elasticsearch 搜索的過程闷旧。

1长豁、搜索被執(zhí)行成一個兩階段過程，我們稱之為 Query Then Fetch忙灼；

2匠襟、在初始查詢階段時，查詢會廣播到索引中每一個分片拷貝（主分片或者副本分 片）该园。 每個分片在本地執(zhí)行搜索并構建一個匹配文檔的大小為 from + size 的 優(yōu)先隊列酸舍。

PS：在搜索的時候是會查詢 Filesystem Cache 的，但是有部分數據還在 Memory Buffer里初，所以搜索是近實時的啃勉。

3、每個分片返回各自優(yōu)先隊列中 所有文檔的 ID 和排序值 給協(xié)調節(jié)點双妨，它合并 這些值到自己的優(yōu)先隊列中來產生一個全局排序后的結果列表淮阐。

4、接下來就是 取回階段斥难，協(xié)調節(jié)點辨別出哪些文檔需要被取回并向相關的分片 提交多個 GET 請求枝嘶。每個分片加載并 豐富 文檔，如果有需要的話哑诊，接著返回 文檔給協(xié)調節(jié)點群扶。一旦所有的文檔都被取回了，協(xié)調節(jié)點返回結果給客戶端。

5竞阐、補充：Query Then Fetch 的搜索類型在文檔相關性打分的時候參考的是本分 片的數據缴饭，這樣在文檔數量較少的時候可能不夠準確，DFS Query Then Fetch 增 加了一個預查詢的處理骆莹，詢問 Term 和 Document frequency颗搂，這個評分更準確， 但是性能會變差幕垦。*

15丢氢、在 Elasticsearch 中，是怎么根據一個詞找到對應的倒排索 引的先改？

SEE：

• Lucene 的索引文件格式(1)
• Lucene 的索引文件格式(2)

16疚察、Elasticsearch 在部署時，對 Linux 的設置有哪些優(yōu)化方 法仇奶？

1貌嫡、64 GB 內存的機器是非常理想的， 但是 32 GB 和 16 GB 機器也是很常見的该溯。 少于 8 GB 會適得其反岛抄。

2、如果你要在更快的 CPUs 和更多的核心之間選擇狈茉，選擇更多的核心更好夫椭。多 個內核提供的額外并發(fā)遠勝過稍微快一點點的時鐘頻率。

3论皆、如果你負擔得起 SSD益楼，它將遠遠超出任何旋轉介質。 基于 SSD 的節(jié)點点晴，查 詢和索引性能都有提升感凤。如果你負擔得起，SSD 是一個好的選擇粒督。

4陪竿、即使數據中心們近在咫尺，也要避免集群跨越多個數據中心屠橄。絕對要避免集群 跨越大的地理距離族跛。

5、請確保運行你應用程序的 JVM 和服務器的 JVM 是完全一樣的锐墙。 在 Elasticsearch 的幾個地方礁哄，使用 Java 的本地序列化。

6溪北、通過設置 gateway.recover_after_nodes桐绒、gateway.expected_nodes夺脾、 gateway.recover_after_time 可以在集群重啟的時候避免過多的分片交換，這可 能會讓數據恢復從數個小時縮短為幾秒鐘茉继。

7咧叭、Elasticsearch 默認被配置為使用單播發(fā)現，以防止節(jié)點無意中加入集群烁竭。只 有在同一臺機器上運行的節(jié)點才會自動組成集群菲茬。最好使用單播代替組播。

8派撕、不要隨意修改垃圾回收器（CMS）和各個線程池的大小婉弹。

9、把你的內存的（少于）一半給 Lucene（但不要超過 32 GBＶ蘸稹）马胧，通過 ES_HEAP_SIZE 環(huán)境變量設置。

10衔峰、內存交換到磁盤對服務器性能來說是致命的。如果內存交換到磁盤上蛙粘，一個100 微秒的操作可能變成 10 毫秒垫卤。 再想想那么多 10 微秒的操作時延累加起來。 不難看出 swapping 對于性能是多么可怕出牧。

11穴肘、Lucene 使用了大量 的文件。同時舔痕，Elasticsearch 在節(jié)點和 HTTP 客戶端之間進行通信也使用了大量的套接字评抚。 所有這一切都需要足夠的文件描述符。你應該增加你的文件描述符伯复，設置一個很大的值慨代，如 64,000。

補充：索引階段性能提升方法

1啸如、使用批量請求并調整其大惺坛住：每次批量數據 5–15 MB 大是個不錯的起始點。

2叮雳、存儲：使用 SSD

3想暗、段和合并：Elasticsearch 默認值是 20 MB/s，對機械磁盤應該是個不錯的設置帘不。如果你用的是 SSD说莫，可以考慮提高到 100–200 MB/s。如果你在做批量導入寞焙， 完全不在意搜索储狭，你可以徹底關掉合并限流互婿。另外還可以增加index.translog.flush_threshold_size 設置，從默認的 512 MB 到更大一些的值晶密，比如 1 GB擒悬，這可以在一次清空觸發(fā)的時候在事務日志里積累出更大的段。

4稻艰、如果你的搜索結果不需要近實時的準確度懂牧，考慮把每個索引的 index.refresh_interval 改到 30s。

5尊勿、如果你在做大批量導入僧凤，考慮通過設置 index.number_of_replicas: 0 關閉副 本。

17元扔、對于 GC 方面躯保，在使用 Elasticsearch 時要注意什么？

1澎语、SEE：https://elasticsearch.cn/article/32

2途事、倒排詞典的索引需要常駐內存，無法 GC擅羞，需要監(jiān)控 data node 上 segment memory 增長趨勢尸变。

3、各類緩存减俏，field cache, filter cache, indexing cache, bulk queue 等等召烂，要 設置合理的大小，并且要應該根據最壞的情況來看 heap 是否夠用娃承，也就是各類緩 存全部占滿的時候奏夫，還有 heap 空間可以分配給其他任務嗎？避免采用 clear cache 等“自欺欺人”的方式來釋放內存历筝。

4酗昼、避免返回大量結果集的搜索與聚合。確實需要大量拉取數據的場景梳猪，可以采用 scan & scroll api 來實現仔雷。

5、cluster stats 駐留內存并無法水平擴展舔示，超大規(guī)模集群可以考慮分拆成多個集 群通過 tribe node 連接碟婆。

6、想知道 heap 夠不夠惕稻，必須結合實際應用場景竖共，并對集群的 heap 使用情況做 持續(xù)的監(jiān)控。

18俺祠、Elasticsearch 對于大數據量（上億量級）的聚合如何實現公给？

Elasticsearch 提供的首個近似聚合是 cardinality 度量借帘。它提供一個字段的基數， 即該字段的 *distinct *或者 *unique *值的數目淌铐。它是基于 HLL 算法的肺然。HLL 會先對 我們的輸入作哈希運算，然后根據哈希運算的結果中的 bits 做概率估算從而得到 基數腿准。其特點是：可配置的精度际起，用來控制內存的使用（更精確 ＝ 更多內存）； 小的數據集精度是非常高的吐葱；我們可以通過配置參數街望，來設置去重需要的固定內 存使用量。無論數千還是數十億的唯一值弟跑，內存使用量只與你配置的精確度相關灾前。

19、在并發(fā)情況下孟辑，Elasticsearch 如果保證讀寫一致哎甲？

1、可以通過版本號使用樂觀并發(fā)控制饲嗽，以確保新版本不會被舊版本覆蓋烧给，由應用 層來處理具體的沖突；

2喝噪、另外對于寫操作，一致性級別支持 quorum/one/all指么，默認為 quorum酝惧，即只 有當大多數分片可用時才允許寫操作。但即使大多數可用伯诬，也可能存在因為網絡 等原因導致寫入副本失敗晚唇，這樣該副本被認為故障，分片將會在一個不同的節(jié)點 上重建盗似。

3哩陕、對于讀操作，可以設置 replication 為 sync(默認)赫舒，這使得操作在主分片和副 本分片都完成后才會返回悍及；如果設置 replication 為 async 時，也可以通過設置搜 索請求參數_preference 為 primary 來查詢主分片接癌，確保文檔是最新版本心赶。

20、如何監(jiān)控 Elasticsearch 集群狀態(tài)缺猛？

Marvel 讓你可以很簡單的通過 Kibana 監(jiān)控 Elasticsearch缨叫。你可以實時查看你 的集群健康狀態(tài)和性能椭符，也可以分析過去的集群、索引和節(jié)點指標耻姥。

21销钝、介紹下你們電商搜索的整體技術架構。

22琐簇、介紹一下你們的個性化搜索方案蒸健？

SEE 基于 word2vec 和 Elasticsearch 實現個性化搜索

23、是否了解字典樹鸽嫂？

常用字典數據結構如下所示

Trie 的核心思想是空間換時間纵装，利用字符串的公共前綴來降低查詢時間的開銷達到提高效率的目的。

它有 3 個基本性質：

1据某、根節(jié)點不包含字符橡娄，除根節(jié)點外每一個節(jié)點都只包含一個字符。

2癣籽、從根節(jié)點到某一節(jié)點挽唉，路徑上經過的字符連接起來，為該節(jié)點對應的字符串筷狼。

3瓶籽、每個節(jié)點的所有子節(jié)點包含的字符都不相同茫孔。

1告抄、可以看到，trie 樹每一層的節(jié)點數是 26^i 級別的畅哑。所以為了節(jié)省空間俏险，我們 還可以用動態(tài)鏈表严拒，或者用數組來模擬動態(tài)。而空間的花費竖独，不會超過單詞數×單 詞長度裤唠。

2、實現：對每個結點開一個字母集大小的數組莹痢，每個結點掛一個鏈表种蘸，使用左兒 子右兄弟表示法記錄這棵樹；

3竞膳、對于中文的字典樹航瞭，每個節(jié)點的子節(jié)點用一個哈希表存儲，這樣就不用浪費太 大的空間坦辟，而且查詢速度上可以保留哈希的復雜度 O(1)沧奴。

24、拼寫糾錯是如何實現的长窄？

1滔吠、拼寫糾錯是基于編輯距離來實現纲菌；編輯距離是一種標準的方法，它用來表示經 過插入翰舌、刪除和替換操作從一個字符串轉換到另外一個字符串的最小操作步數只冻；

2舍悯、編輯距離的計算過程：比如要計算 batyu 和 beauty 的編輯距離，先創(chuàng)建一個 7×8 的表（batyu 長度為 5朴艰，coffee 長度為 6，各加 2）芯急，接著，在如下位置填入 黑色數字。其他格的計算過程是取以下三個值的最小值：

如果最上方的字符等于最左方的字符喻犁，則為左上方的數字传轰。否則為左上方的數字 +1。（對于 3,3 來說為 0）

左方數字+1（對于 3,3 格來說為 2）

上方數字+1（對于 3,3 格來說為 2）

最終取右下角的值即為編輯距離的值 3路召。

對于拼寫糾錯勃刨，我們考慮構造一個度量空間（Metric Space），該空間內任何關 系滿足以下三條基本條件：

d(x,y) = 0 -- 假如 x 與 y 的距離為 0股淡，則 x=y

d(x,y) = d(y,x) -- x 到 y 的距離等同于 y 到 x 的距離

d(x,y) + d(y,z) >= d(x,z) -- 三角不等式

1身隐、根據三角不等式，則滿足與 query 距離在 n 范圍內的另一個字符轉 B唯灵，其與 A 的距離最大為 d+n贾铝，最小為 d-n。

2埠帕、BK 樹的構造就過程如下：每個節(jié)點有任意個子節(jié)點垢揩，每條邊有個值表示編輯 距離。所有子節(jié)點到父節(jié)點的邊上標注 n 表示編輯距離恰好為 n敛瓷。比如叁巨，我們有樹父節(jié)點是”book”和兩個子節(jié)點”cake”和”books”，”book”到”books”的邊標號 1呐籽，”book”到”cake”的邊上標號 4锋勺。從字典里構造好樹后，無論何時你想插入新單詞時狡蝶，計算該單詞與根節(jié)點的編輯距離庶橱，并且查找數值為d(neweord, root)的邊。遞歸得與各子節(jié)點進行比較贪惹，直到沒有子節(jié)點苏章，你就可以創(chuàng)建新的子節(jié)點并將新單詞保存在那。比如，插入”boo”到剛才上述例子的樹中枫绅，我們先檢查根節(jié)點泉孩，查找 d(“book”, “boo”) = 1 的邊，然后檢查標號為 1 的邊的子節(jié)點撑瞧，得到單詞”books”棵譬。我們再計算距離 d(“books”, “boo”)=2，則將新單詞插在”books”之后预伺，邊標號為 2订咸。

3、查詢相似詞如下：計算單詞與根節(jié)點的編輯距離 d酬诀，然后遞歸查找每個子節(jié)點 標號為 d-n 到 d+n（包含）的邊脏嚷。假如被檢查的節(jié)點與搜索單詞的距離 d 小于 n， 則返回該節(jié)點并繼續(xù)查詢瞒御。比如輸入 cape 且最大容忍距離為 1父叙，則先計算和根的 編輯距離 d(“book”, “cape”)=4，然后接著找和根節(jié)點之間編輯距離為 3 到 5 的肴裙，這個就找到了 cake 這個節(jié)點趾唱，計算 d(“cake”, “cape”)=1，滿足條件 所以返回 cake蜻懦，然后再找和 cake 節(jié)點編輯距離是 0 到 2 的甜癞，分別找到 cape 和 cart 節(jié)點，這樣就得到 cape 這個滿足條件的結果宛乃。