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，并给定一个前缀，您可以一直向下到达一个节点。然后，您只需遍历以该节点为根的子树即可获取所有项目。

Answer 2

如上所述，特里可能对您有好处。您也可以使用哈希表，密钥将是前 7-8 个字节（可以使用 long），访问时间是 O(1)，我认为实现起来更简单。