4

我有大量映射到文件路径的键值参数。大多数有以下形式

filepath : /some/path
param_name_1 => 1234
param_name_2 => qwerty

但其他可以包含通配符

filepath : /other/path
param_name_1 => 123*4
param_name_2 => ab?12

其中?是匹配任何一个字符*的通配符,是匹配 0+ 个字符的通配符。

我的用户可以提供他们自己的一组 KV 参数,我必须匹配并返回映射路径。

示例:用户提供

param_name_1 => 1234
param_name_2 => qwerty

Application returns /some/path

用户提供

param_name_1 => 123asdqweqweqdqweq1231asdcase4
param_name_2 => abW12

Application returns /other/path

对于所有不包含通配符的映射,我可以计算hashCode()我存储的映射和用户提供的映射,并进行HashMap非常快的查找(匹配 3-4 个参数,100000 个映射,在 0 毫秒内,这是一个毕竟哈希)。

但是,对于包含通配符的映射,我有点坚持通过包含通配符的所有映射的列表进行线性查找。大约有 2000-5000 个这样的映射,每次查找只需要不到 200 毫秒,我需要加快速度。

有没有一种方法可以进行一般查找以匹配通配符或其他可以结合所有映射的匹配技术?

4

1 回答 1

4

如果您使用 aTreeMap而不是 a HashMap,则可以进行前缀搜索以减少必须迭代的项目数。只需抓住出现在*or之前的字符?,并遍历以这些字符开头的所有键。当然,如果您的搜索词以通配符开头,这将不起作用。

解决这个问题的另一种常见方法是使用字符ngrams或一些基于 trie 的结构,但这要复杂得多。

于 2013-01-16T16:45:15.790 回答