为了解决数组增删的问题，链表就出现了。如果我们将值分成两部分，一部分用来储存原来的值，另一部分用来储存一个地址，这个地址指向另外一个同样的结构，以此类推就构成了一个链表。结构如下：
从上图可以明显看出，对链表进行增删非常简单，只要把目标项和前一项的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个字的差异，我们没对比字符串！
关于多关键词的匹配就说到这里了，优化版代码我就不贴了，因为一般也用不到。
您可能感兴趣的文章: