java - 查找部分属性

Question

我有一张 map 。 Key 包含 6 个字符的 String 和 Properties 类大致如下所示:

public class Properties {
    private String propertyOne;
    private String propertyTwo;
    private String propertyThree;
    private String propertyFour;
    ...
    ...
}

现在假设我在 map 中有一些条目，如下所示:

41111 -> {1,2,3,4,5}

41112 -> {1,2,3,4,6}

41234 -> {1,2,345,87,65}

51123 -> {100,200,30000,345,123}

51122 -> {100,200,30000,556,989}

现在，如果我这样做map.get("12567") ，我得到了想要的属性对象。

我面临的挑战是，我必须创建一个可以保存部分数据的数据结构。我所说的部分数据是指如果我这样做 map.get("4111")我应该得到 {1,2,3,4,5} 的交集 (41111 的属性) 和 {1,2,3,4,6} (41112 的属性)，即 {1,2,3,4,null}.

同样map.get("41")应该产生 {1,2,null,null,null} .

我现在有一个解决方案，即我创建了多个 HashMap，其中包含所有可能的部分键及其相应的值，例如:

Map<String, Property>`` keyValuesForOneChar包含所有可能的单个字符作为键及其相应的值。

Map<String, Property> keyValuesForTwoChars包含所有可能的两个字符作为键及其对应的值。

我不喜欢这个解决方案，因为它非常简单，而且我认为维护多个 HashMap 不是一个好主意。另一个问题是，我的原始数据计数约为 200000，并且对于所有排列组合，我将创建大量的部分数据，并且随着这一庞大的计数，我认为 HashMap 的性能会下降。请针对这个问题提出更好的解决方案。我有以下限制:

1. 解决方案应严格仅限于内存中。
2. 查找速度应该更快。这就是为什么如果处理原始数据和准备数据结构需要额外的时间和内存，那应该不是问题。

Answer 1

HashMap 绝对不是最适合您的问题的数据结构。由于您的键是字符串，因此您可以实现 trie(也称为前缀树)。

它的工作原理是将字符串键分割成更小的字符串或字符。通过这种方式，您可以存储键的值，也可以存储常见前缀的值。也就是说，您可以将“41111”和“41112”的交集存储在公共(public)前缀“4111”上。查找 4111 时，需要 O(m) 步，其中 m 是键的长度，您将能够检索 {1,2,3,4,5} 和 {1,2,3 的交集,4,6} 如果在 trie 中插入项时更新交集。

检索部分属性

您可以在构建 trie 时更新部分属性。假设您插入了这对 (41111, {1,2,3,4,5})。尝试是特定的树，它可以看起来像这样。符号 k,v 表示这是一个具有键 k 和值 v 的节点。

4,{1,2,3,4,5}
      |
1,{1,2,3,4,5}
      |
1,{1,2,3,4,5}
      |
1,{1,2,3,4,5}
      |
1,{1,2,3,4,5}

在路径上的每个节点上，您存储一个部分属性。现在，当插入这对 (41112,{1,2,3,4,6}) 时，您会更新 trie:

       4,{1,2,3,4,null}
             |
       1,{1,2,3,4,null}
             |
       1,{1,2,3,4,null}
             |
       1,{1,2,3,4,null}
      /                \
1,{1,2,3,4,5}     2,{1,2,3,4,6}

同样，如果您插入 41234,{1,2,345,87,65}，它将如下所示:

              4,{1,2,null,null,null}
                         |
              1,{1,2,null,null,null}
             /                      \
       1,{1,2,3,4,null}          2,{1,2,345,87,65}
             |                           |
       1,{1,2,3,4,null}          3,{1,2,345,87,65}
      /                \                 | 
1,{1,2,3,4,5}     2,{1,2,3,4,6}  4,{1,2,345,87,65}

这样做，您只需存储已插入项目的公共(public)前缀的部分属性，无需创建所有组合。另外，检索部分属性是使用与检索值相同的算法完成的。