使用100行代码提高10倍性能的Object，它具有各种属性。每个属性的值可以是基本类型、对象，甚至是数组。这里对象或数组内部的元素可以继续包含对象或数组，并允许无限嵌套。例如{"name":{"firstName":"yi","lastName":"li"},"age":23,"roles":['developer','admin'],"projects":[{"name":"demo","re??po":""}]}页面提供了一个搜索框，用户输入搜索内容即可找到包含该内容的数据。注意，只要是任何数据对象的任何属性值（比如上面的数据结构中，只要是name、age、roles的任何属性值）都包含这个关键字。如果属性值为数组或对象，则数组的元素或对象的值会继续匹配检测输入的内容，并递归继续检测。只要有命中，就会算作数据匹配。如何设计这个功能，让搜索功能尽可能高效快捷？解决方案如果你有程序员的敏感度，此时你的脑海中应该有两种想法：遍历和深度优先遍历是最直接的方式。如果你要求足够快的遍历，我就输了。的确，遍历是最简单但也是最慢的。所以通常的优化之一是用空间换取时间；另一个……稍后再说。这里我们尝试通过构建Trie来优化搜索。如果你还不知道什么是字典树，这里简单介绍一下：假设我们有一个简单的对象，key和value的对应关系如下：我们按照出现的字母依次建树“键”，而叶节点的值可能是一个“键”的值。这时，无论用户想访问任何一个属性的值，只需要从树的根节点开始，按照属性字母的顺序访问树的叶子节点，就可以得到该属性。价值。例如，当我们要访问茶时：但在我们需要解决的场景中，我们不需要关心“属性”，我们只关心“值”是否与搜索到的内容相匹配。所以我们只需要为“值”建立一个字典树。假设如下对象值consto={message:'ack'fruit:'apple',unit:'an',name:'anna',}建立的树结构如下：root--a|--c|--k|--p|--p|--l|--e|--n|--n|--a当用户搜索apple时，他从a开始访问，最后访问到字母e，如果树中有对应的节点，表示命中；当用户搜索aha，访问h时在树中找不到对应的节点，说明该对象不满足搜索条件，但是在实际工作中我们会有很多Object值，它们之间可能存在重复值多个对象值，所以在匹配的时候，我们需要返回所有可能的匹配结果。例如[{id:1,message:'ack'fruit:'apple',unit:'an',name:'anna',},{id:2,message:'ack'fruit:'banana',unit:'an',name:'lee',},]上面两个对象ack和an的值相同，所以我们还需要在叶子上加上对象root--a|--c的id标识信息树上的节点|--k(ids:[1,2])|--p|--p|--l|--e(ids:[1])|--n(ids:[1,2])|--n|--a(ids:[1])这样当用户搜索an时，我们就可以返回所有匹配项OK。有了想法之后，我们就开始实现代码。代码实现造假数据首先要解决的问题之一就是如何快速伪造5000条数据？这里我们使用https://randomuser.me/api/开源API。为了简单起见，让它只返回性别、电子邮件、电话、单元格、nat原始数据类型的值，而不是嵌套结构（对象和数组）。注意这里只是为了方便代码展示和理解，省略了复杂的结构，也避免了复杂的代码。添加复杂结构后，代码没有太大变化，只是增加了遍历逻辑和递归逻辑。请求https://randomuser.me/api/?results=5000&inc=gender,email,phone,cell,nat结果如下：{"results":[{"gender":"male","email":"enzo.dumont@example.com","phone":"02-65-13-26-00","cell":"06-09-02-19-99","nat":"FR"},{"性别":"男","电子邮件":"gerald.omahony@example.com","电话":"011-376-3811","手机":"081-697-1414","nat":"IE"}//...]}叶子节点数据结构根据idea中的描述，数据结构描述如下：classLeaf{constructor(id="",value=""){this.ids=id?[id]:[];this.value=value;this.children={};}share(id){this.ids.push(id);}}share方法用于添加多个相同的将ids匹配到叶子节点我们在编码过程中需要一些辅助函数，例如：isEmptyObject：判断是否为空对象distinct：去除数组中的重复元素。这两个功能可以借用lodash类库来实现，即使手动实现也很简单。我不会在这里详细介绍。另一个重要的方法是归一化。我更习惯将normalize翻译为“扁平化”（而不是“标准化”），因为它更直观。该方法用于将数组中的对象拆分成id和object的映射关系。例如，[{id:1,message:'ack'fruit:'apple',unit:'an',name:'anna',},{id:2,message:'ack'fruit:'banana',unit:'an',name:'lee',},]压平后变成{'1':{id:1,message:'ack'fruit:'apple',unit:'an',name:'anna',},'2':{id:2,message:'ack'fruit:'banana',unit:'an',name:'lee',}}这样做的原因是当检索结果当数组为：[1,2,3]时，我们只需要遍历其中一侧并返回结果，就可以立即通过id在展平后的Map中找到对应的数据。否则，需要不断遍历原始数据数组，才能找到对应的数据。由于randomuser.me返回的信息不包含id信息，我们暂时使用email信息作为唯一标识。normalize的实现如下：functionnormalize(identify,data){constid2Value={};data.forEach(item=>{constidValue=item[identify];id2Value[idValue]=item;});returnid2Value;}构建一个tree部分代码没有什么秘密，按照递归算法fetch("https://randomuser.me/api/?results=5000&inc=gender,email,phone,cell,nat")递归建树.then(response=>{returnresponse.json();}).then(data=>{const{results}=data;constroot=newLeaf();constidentifyKey="email";results.forEach(item=>{constidentifyValue=item[identifyKey];Object.values(item).forEach(itemValue=>{//注意这里Number和Boolean类型也会被字符串化conststringifiedValue=String(itemValue);lettempRoot=root;constarraiedStringifiedValue=Array.from(stringifiedValue);arraiedStringifiedValue.forEach((character,characterIndex)=>{constreachEnd=characterIndex===arraiedStringifiedValue.length-1;if(!tempRoot.children[character]){tempRoot.children[character]=newLeaf(reachEnd?identifyValue:"",character);tempRoot=tempRoot.children[character];}else{if(reachEnd){tempRoot.children[字符].share(identifyValue);}tempRoot=tempRoot.children[字符];}});});});搜索部分代码的模糊搜索没有秘密。这就是全部：functionsearchBlurry(root,keyword,userMap){constkeywordArr=Array.from(String(keyword));lettempRoot=root;letresult=[];for(leti=0;i
