不久前，我需要实现一个已经由其他人实现并且不止一次的功能，但是不适合某些特性。 在这种情况下，需要某种数据结构，并具有通过字符串键或键的几个初始字符进行搜索的能力。 密钥是一串拉丁字母，无论如何都是空格和数字。
首先，其他实现不适用于消耗的内存。 而且在任何情况下，前缀树的另一种实现都是多余的。
这个想法可能是受
本文启发的，因为它决定使用位图索引来索引到节点中后续节点的链接。
显然，一个节点中的链接数不能超过63（10位数字，每种情况下为26个字母，再加上一个空格）。 因此，对于位图索引，在每个节点上使用64位数字。 任何位置的置位意味着存在相应的符号和节点（子树）。
位图索引中的分布如下：0到9的数字占0到9位，字母az占10到35位，字母AZ占36到62位，空格占63位。 要获得位数，只需使用ASCII字符代码，并将其减少一定数量即可。 对于每个字符范围，数字都不同：对于数字48（ASCII代码中的数字范围以48开头），对于字母az 87（字母az的范围以已由10位数字占据的负10位开始）等等。
相应的表如下所示。
该节点由以下代码表示：
type Trie struct { rw sync.RWMutex characters uint64 subTries []*Trie data interface{} }
因此，每个节点都存储以下字符的位图索引，带有子树链接的切片以及数据本身。 我将简要介绍一下搜索，插入和删除的机制。
输入输入时，键从根节点开始象征性地穿过树。 对于来自其ASCII码的每个字符，将计算位数，并在其基础上计算到子树的链接（subTries）切片中的索引。 索引值是所需位之前的位数。 例如，我们有这样的索引：00 ... 101。 这意味着在位图索引中有数字0和2。然后，数字0的索引将为零，数字2的索引将为1，即subTries将存储2个到子树的链接：subTries [0]和subTries [1] 。
获取字符位数的代码：
func calcBitNum(char rune) (uint64, bool) {
获取字符节点索引的代码：
func (trie *Trie) getSubTreeIndex(bitNum uint64) int { shifted := trie.characters << (64 - bitNum) return bits.OnesCount64(shifted) }
获取给定字符的节点的代码：
func (trie *Trie) getSubTrie(char rune) (uint64, int, *Trie) { bitNum, _ := calcBitNum(char) subTrieId := trie.getSubTreeIndex(bitNum)
插入
遍历树以插入元素。 如果缺少任何字符（以及所有后续字符），则将其插入位图索引。 创建一个子树，将其链接插入到切片subTries的正确位置（正确位置由所需位的位数确定）。 当它们到达键的最后一个字符时，数据将插入到最后一个子树中。
搜寻
要搜索，该键象征性地“遍历”树。 一旦结束，将返回结果。 如果没有该键的数据，但还有其他子树，则从具有数据的所有后续子树中选择结果。 可以设置返回数据的数量限制。 因此，可以通过整个键的一致性来搜索单个节点，或者通过几个初始字符的一致性来搜索节点集。
删掉
删除过程比预期的要复杂得多（按预期）。 要删除密钥，请遍历一棵树，在此期间将没有数据的节点记录在单独的切片中。 如果找到带有数据的节点，则切片将重置为零，并且继续通过树。 也就是说，要删除的节点片应包含一系列没有数据的节点。 如果最后切片不为空，则以相反的顺序进行操作，并从位图索引中删除相应的位，并删除节点。
总结
结果是前缀树在速度和内存消耗方面均优于其他类似物（平均减少了30％的内存，并且速度更快）。 另外，我也不懒于使用树进行多线程操作，这极大地提高了生产率，尤其是在搜索操作中。 当然，该解决方案非常专业（以拉丁字符，数字和空格作为关键组成部分的形式存在限制）。
基于前缀树的目的，此解决方案可用于创建字典，搜索索引。
我没有引用插入，搜索和删除代码，以免使文章混乱，此外，源代码
在github上可用。