查找部分属性

Question

我有一张地图。密钥包含 6 个字符的字符串和属性 class 大致如下所示：

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

现在假设我在地图中有一些条目如下：

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") 我应该得到 intersection of {1,2,3,4,5} (属性 for 41111) 和 {1,2,3,4,6} （属性 for 41112） 即 {1,2,3,4,null}.

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

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

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

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

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

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

Answer 1

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

它的工作原理是将字符串键拆分为更小的字符串或字符。通过这种方式，您可以存储键的值，也可以存储通用前缀的值。也就是说，可以将“41111”和“41112”的交集存储在公共前缀“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}

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

查找部分属性

Finding partial properties

java

hashmap

in-memory

data-structures