Key-Value参数匹配通配符

Question

我有大量映射到文件路径的Key-Value参数。大多数都有如下形式

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毫秒，我需要加快速度。

是否有一种方法，我可以做一个一般的查找匹配通配符或一些其他匹配技术，将所有的映射组合?

Answer 1

如果您使用TreeMap而不是HashMap，则可以执行前缀搜索以减少必须遍历的项数。只需获取出现在*或?之前的字符，并遍历以这些字符开头的所有键。当然，如果你的搜索词以通配符开头，这是行不通的。

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