algorithm - 如何实现在一组固定长度的字节数组中搜索前缀的有效方法？

Question

我有一大组固定长度的字节数组，例如:

type Fixed [64]byte

set := make([]Fixed, 10240)

大多数条目都有不同的 5-7 字节前缀。 我如何实现根据给定前缀查找 set 元素的有效方法？例如:

set.Find([7]byte{ /*...*/ }) == /* no hit || single hit || multiple hit */

Answer 1

看起来你需要一个 trie .

您可以将您的集合存储为一个 trie 树并给定一个前缀，您可以一直向下到达一个节点。然后，您只需遍历以该节点为根的子树即可获取所有项。