时间戳

首页 > 解决方案 > 与标记化地图键的字符串匹配

java - 与标记化地图键的字符串匹配

问题描述

我的 Dynamo DB 中有一张地图，存储如下：

"A|1,2,3,4|B" : "[some data]"
"C|5,6|D" : "[some data]"
"X|7,8,9,10,11,12,13|Y" : "[some data]"
 ..

为了便于讨论，假设上图中的每个键都是 LEFT、MIDDLE 和 RIGHT 三个字符串的连接结果，如：“LEFT|MIDDLE|RIGHT”。

我想知道给定的字符串是否是上图中的键。但是，中间字符串应该按此匹配的逗号值拆分。示例：“A|1|B”和“A|3|B”都应该与第一个条目匹配。类似地，“C|5|D”匹配第二个条目，依此类推。

假设： MIDDLE 字符串可以是 1 到 200 个数字的串联（存储为字符串）。该地图有大约 35K 条目。

我想一种直接的方法是“扩展”原始映射并分解中间字符串上的每个条目以创建多个具有重复值的新键值对。但是，我的数据量很大，因此这种方法会花费大量的时间和空间复杂性。有没有一种优雅的方法可以在生产环境中解决这个问题？

标签： javaalgorithmdata-structures

解决方案

例如，我会用一些随机字符串替换 MIDDLE

"A|4806369425|B" : "[some data M]"
"A|0848833569|B" : "[some data N]"
"A|5514390566|B" : "[some data P]"

添加另一个映射

"1" : "4806369425"
"2" : "4806369425"
"3" : "4806369425"
"4" : "4806369425"
"5" : "0848833569"
"6" : "0848833569"
"7" : "5514390566"
"8" : "5514390566"
"9" : "5514390566"
...
"13" : "5514390566"

当获取一个值时，我会去第二个映射找到中间的键。它应该在 O(1) 中执行，然后将左右连接并在 O(1) 中再次从第一个映射中获取一些数据

推荐阅读