一种使用多级Hash存储路径字符串并优化访问的方法

在进行web开发,经常会使用各种不一样的路径进行相应的逻辑定义。特别是使用spring体系时,会使用各种path来定义访问方法。浏览器在访问某个API时,服务端则会使用特定的匹配逻辑来匹配到具体应该访问某个方法。如例子如下

@GetMapping({"/index/**", "index2"})
public String index() throws Exception {
}

在如上的定义中,可以匹配如下的路径

/index2
/index
/index/abc
/index/abc/def

当在项目中定义的路径过多时,默认情况下,常规的逻辑即是根据代码中定义的 path,遍列匹配请求路径,最终找到匹配的方法。当path过多时,在一定程度上其本身的性能也不会太快. 在笔者的实际项目中,大部分的path定义如下

/a/api/business1/index
/b/api/business1/index
/c/api/business1/index
/a/api/business1/*/path1/*
/b/api/business1/*/path1/*
/c/api/business1/*/path1/*
/a/api/business1/**
/b/api/business1/**
/c/api/business1/**

可以看出,path 定义中,有相同的前缀,只是末尾或中间有一些不同。在这种典型的场景中,有点类似于前缀树的概念。不过是按 / 进行分隔节点.
在标准的前缀树(字典树)中,都是按单个字母(字符)来进行节点划分,并没有一种按不固定的字符串(每个/中的字符串长度不定)进行前缀划分的逻辑.

本文描述了一种通过多级Hash存储,来模拟前缀树,并通过优化访问路径,来提升匹配速度的算法. 考虑到具体使用场景,本文描述的算法,仅处理 插入和查找 的逻辑,不处理更新或删除的逻辑.

继续阅读“一种使用多级Hash存储路径字符串并优化访问的方法”