java - 没有数据重复的性能结构

Question

假设我有以下类(class):

public class Tagged {

    private List<String> tags;
}

public class ContainerOfTagged {

    private List<Tagged> tagged;
}

使用这种结构，每当我需要找到一个带有特定标签的Tagged时，我需要遍历ContainerOfTagged中的所有标签，并遍历所有标签每个标记。这可能会影响性能，具体取决于列表的大小。

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

public class ContainerOfTagged {

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

现在我需要做的就是提供一个标签，Map 将返回所有带有该标签的Tagged。但是，这样做会导致数据重复，因为 Tagged 和 ContainerOfTagged 类中存在相同的标记。

那么，有没有一种方法可以通过不重复数据的高性能解决方案来解决这个问题？

Answer 1

您无法真正避免“复制”标签，但请记住，您并不是真的在复制它们，因为列表和 map 仅存储对标签字符串的引用，而不是值(但是，引用可能会占用本身有很大的空间)。

问题是你需要两个索引:

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);
    }

如果内存利用率是一个主要问题，您可以尝试某种引用压缩。使用这种技术，您可以将标签存储在一个数组中，然后通过索引引用它们。如果足够少，可以使用 byte 或 short 而不是引用，但代码会更困惑，我不推荐它。

编辑:

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

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