在进行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存储，来模拟前缀树，并通过优化访问路径，来提升匹配速度的算法. 考虑到具体使用场景，本文描述的算法，仅处理 插入和查找 的逻辑，不处理更新或删除的逻辑.
数据结构定义
class LevelTree {
int hash;
String str;
boolean hasValue;
HashMap<Int,LevelTree> leafs;
}
hash 表示单层的字符串的hash值, 这里借鉴了String的hash计算公式, 并没有实际使用hashCode，以避免在查找时先组装字符串，再调用hashCode的问题
str 表示单层的字符串,仅用于查看，没有其它特别的意义
hasValue 表示当前层是否存储着最终的叶子节点值，因为每一层均可能存储叶子节点点，因此此值并不表示是否为叶子节点
leafs 表示下层的节点树， 使用 hash 作为key，以优化查找性能
插入
整个逻辑，即是通过针对 / 分层，然后循环地创建出子节点出来，并设置相应的值信息. 大概逻辑如下所示(以下仅供示例,部分逻辑有删除)
//其中 sidx, eidx 默认为 0, s.length()
private void add(String s, int sidx, int eidx) {
int preIdx = sidx;
int k = 0;
LevelTree<V> st;
LevelTree<V> parent = this;
for(int i = sidx; i < eidx; i++) {
char c = s.charAt(i);
//这里找到 / ,则先处理上一层的数据
if(c == SLASH) {
st = parent.addLeaf(k, s.substring(preIdx, i));
parent = st;
//重置各项数据
k = 0;
preIdx = i + 1;
} else {
k = k * 31 + c;
}
}
val leafValue = s.substring(preIdx, eidx);
st = parent.addLeaf(k, leafValue, v);
//置叶子值标记, 用于查找定位
st.hasValue = true;
}
查找
查找的过程，也是通过 / 分层，然后每一层递进，最终达到最末的节点，查看其 hasValue 是否有值. 因为path中存在 * 号的概念，因此匹配时，也要针对其作特殊的处理. 在处理过程中，需要处理以下的场景(暂不支持 ** 在中间的情况)
正常路径 /a/b/c /a/b/c *在末尾 /a/b/* /a/b/c *在中间 /a/*/c /a/b/c *在中间(不能匹配的场景) /a/*/c /a/b/cc **在末尾，匹配不带**的路径 /a/b/** /a/b **在末尾，匹配带1层的路径 /a/b/** /a/b/c **在末尾，匹配带多层的路径 /a/b/** /a/b/c/d
相应的大概逻辑如下所示(以下仅供示例,部分逻辑有删除):
//sidx, eidx 默认为 0, s.length(), 在处理过程中。为优化调用，尽量不会创建中间字符串
private boolean find(String s, int sidx, int eidx) {
int k = 0;
LevelTree st = this;
int preIdx = sidx;
for(int i = sidx; i < eidx; i++) {
char c = s.charAt(i);
if(c == SLASH) {
val tmpParent = st;
st = tmpParent.getLeaf(k, s, preIdx, i);
//未找到时，支持匹配 a/*/b 中的 *
if(st == null) {
st = tmpParent.leafs.get('*');
if(st != null && st.find(s, i + 1, eidx)) {
return true;
}
return false;
}
//支持 /a/b/** 的场景
if(st.leafs.get('**') != null) {
return true;
}
//继续往下，要求leafs 非空
if(st.leafs == null) {
return false;
}
k = 0;
preIdx = i + 1;
} else {
k = k * 31 + c;
}
}
val parent = st;
//支持 /a/* /a/** 匹配 /a/b 的情况
if(parent.get('*) != null || parent.get('**') != null) {
return true;
}
st = parent.getLeaf(k, str, preIdx, eidx);
if(st == null) {
return false;
}
//支持 /a/** 匹配 /a 的情况
if(st.get('**') != null) {
return true;
}
//匹配 /a/b 匹配 /a/b 的情况
return st.hasValue;
}
特定优化
优化一：hash优化
在定义时已经默认使用 hash 来进行当前层的数据引用. 即针对每层的 /a/b/c，并不实际使用当前层的字符串作判断和使用，而是使用计算好的hash。这样在进行查找时，可以依次计算hash值，并而不需在查找过程中，通过substring，重新构建子字符串，并且在leafs map 中，也不需要再次 通过字符串#hashCode来计算作二次查找处理.
优化二：HashMap优化
在定义中使用了 HashMap 结构，但hash值为 int 基本类型，如果使用jdk自带的HashMap，则会产生 类型包装，以及在内部调用hashCode和equals 等方法。在这里的场景中，如果hash相同，则认为值相同，不再需要其它判断。
可以通过重新定义IntHashMap, 以实现基于 int 的hashMap，并且内部优化判断相等逻辑来处理此问题. 在调整之后，IntHashMap比原生jdk HashMap，大概快 20% 左右.
优化三：*符号优化
定义好的path中，经常会出现 * 或 **. 因此在查找的过程中，经常会判断，叶子中是否有 * 或 **，以决定是否类似于模糊匹配的场景. 优化访问，可以将 * 和 ** 单独设计为独立的字段，以避免通过leafs map 二次查找的问题. 因此，在原字段定义中, 增加以下的定义
boolean star1 = false;
LevelTree star1Tree;
boolean star2 = false;
LevelTree star2Tree;
然后在 add 时，给相应的字段赋值。同时在查找时，使用boolean字段快速地进行判断，同时使用 star1Tree 或 star2Tree 快速地进行引用。比通过原生leafs.get 更快。
hash冲突处理
通过int hash可以快速提升查找效率，但因为是通过字符串的计算hash来存储中间数据，在一定程度上存在着hash冲突问题。即不同的字符串映射到同1个hash值. 解决此问题的作法在于通过使用原生的HashMap 来回滚存储原始数据，并通过标记位判断是否走快速判断还是普通判断逻辑。
可以通过 增加以下的字段来实现此逻辑
boolean fastPath = true; Map<String, LevelTree> slowLeafs;
同时 在进行 addLeaf 中，因为之前存储了相应的str值，可以在此逻辑中进行冲突的检测，即如果 leafs 中存在 hash的映射，但str并不和当前的str相同，则进行 lowLeafs的转换，同时置相应的标记位。
同时，在 getLeaf 中，快速通过标记位决定是否走 leafs 还是 slowLeafs。当然，如果走 slow 途径，则需要进行 str.substring 操作，进一步退化性能.
相应的代码参考如下所示
private LevelTree addLeaf(int hash, String str) {
if(fastPath) {
initLeafTree();
LevelTree leaf = leafs.get(hash);
if(leaf != null) {
if(!leaf.str.equals(str)) {
log.warn("出现冲突，准备slow化");
reStringTreeify();
}
return leaf;
}
leaf = new LevelTree<>(hash, str);
leafs.put(hash, leaf);
return leaf;
}
return slowLeafs.computeIfAbsent(str, noused -> new LevelTree<>(hash, str));
}
性能对比
此算法在 path 为3000+，在本机(i7-7700 4核16G内存) 分别使用 循环PathPattern和当前算法作了简单的jmh测试，其差距可达 2000倍.
后记
详细代码可参考 https://github.com/flym/iflymio/blob/master/iflym-core/src/main/java/io/iflym/core/collection/LevelTree.java
转载请标明出处:i flym
本文地址:https://www.iflym.com/index.php/code/202103220002.html