没有数据重复的性能结构

Question

说我有以下课程:

public class Tagged {

    private List<String> tags;
}

public class ContainerOfTagged {

    private List<Tagged> tagged;
}

有了这个结构,每当我需要找到一个Tagged带有特定标记的东西时,我需要遍历所有标记的内容ContainerOfTagged,并迭代每个标记的所有标记Tagged.这可能会影响性能,具体取决于列表的大小.

一个简单的解决方案是更改ContainerOfTagged类以使用以下Map列表中的映射标记Tagged:

public class ContainerOfTagged {

    private Map<String, List<Tagged>> tagMapping;
}

现在我需要做的就是提供一个标签,并且Map将Tagged使用所述标签返回所有标签.但是,通过执行此操作,我导致数据重复,因为在类Tagged和ContainerOfTagged类中都存在相同的标记.

那么,有没有办法用不重复数据的性能解决方案来解决这个问题？

Answer 1

您无法真正避免“复制”标签，但请记住，您并没有真正复制它们，因为列表和映射仅存储对标签字符串的引用，而不是值（但是，引用可能会占用相当多的空间）本身的空间）。

问题是你需要两个索引：

1. 您需要在给定 Tagged 对象的情况下找到标签列表。
2. 您需要找到给定标签的 Tagged 对象。

理想情况下，您的解决方案应如下所示。您可以通过使用单一方法来管理标记来解决您对事物不同步的担忧。

请注意，Tagged您应该使用 Set 而不是列表，以避免标签重复。

public class Tagged {
    Set<String> tags;
}

public class TagContainer {
    Map<String, Tagged> tagIndex;

    public tag(String tag, Tagged tagged) {
        tagged.tags.add(tag);
        tagIndex.put(tag, tagged);
    }

如果内存利用率是一个主要问题，您可以尝试某种引用压缩。使用这种技术，您可以将标签存储在数组中，然后通过索引引用它们。如果你的数据足够少，你可以使用字节或短字符来代替引用，但代码会更加混乱，我不会推荐它。

编辑：

在我的第一篇文章中，我建议 Tagged 应该是一个名为 Tagable 的接口。这更干净，但延长了解决方案，所以我回到了课堂。但是，您也许可以考虑拥有一个 Tagable 接口并在 Tagged 类中实现它。

public interface Tagable {
    Set<String> getTags;
    tag(String tag);
}