分类：数据结构

一种使用多级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存储路径字符串并优化访问的方法”

fastjson 反序列化源码解析

fastjson从0.X版本到最新版本，由于其特殊的编码(即特别编码优化)，让人对其实现思路很难处理，加上没有注释，因此在学习了解时也很困难。因此，本篇即从基本概念入手，忽略其一些特殊处理点(对实际结果无意义)，了解其反序列化实现思路。
本文基于fastjson版本 1.2.4

1 基本概念

  • token-词法标记      用于标识当前在解析过程中解析到的对象的一个标记，具体的值参考 JSONToken。比如 {，即表示当前正在解析的是一个类似map或对象的格式，而}，则表示当前对象已经到底了。
  • ch-当前字符    用于表示当前已经读取到的字符是什么，如 abc，当位置为1时，则当前字符为 b
  • bp-解析字符位置    用于表示当前字符所位于原始字符串中的哪一个位置，与ch是相对应的，它始终表示最新的一个位置，如果需要记录一些历史位置。如字符串起始位置，数字起始位置等，则需要使用其它标记，如np。
  • sbuf-字符缓冲    在解析字符串时的特殊存储区域，主要是用于解析转义字符时的临时存储区。即如果原字符串为 a\\t，则实际解析的字符串应该为a\t，那么原字符串为3位长，解析之后为2位长。即需要另行存储。字符缓冲区如名所示，为一个字符数组，需要需要单独的定义来存储长度信息，如使用sp。
  • sp-字符缓冲区位置    这个用于表示在字符缓冲区之间记录当前字符串(或数字串)等的长度信息，同时也等同于当前的一个位置(如果坐标从0开始)。
  • np-数字解析位置    用于实际表示在解析到常量信息时起始点的标记位置。通过np + sp,即计算得出相应的区间值了。

继续阅读“fastjson 反序列化源码解析”

java内部类final语义实现

本文描述在java内部类中，经常会引用外部类的变量信息。但是这些变量信息是如何传递给内部类的，在表面上并没有相应的线索。本文从字节码层描述在内部类中是如何实现这些语义的。

本地临时变量 基本类型

final int x = 10;

new Runnable() {
    @Override
    public void run() {
        System.out.println(x);
    }
}.run();

当输出内部类字节码(javap -p -s -c -v)时，如下所示：

         0: getstatic     #2                  // Field java/lang/System.out:Ljava/io/PrintStream;
         3: bipush        10
         5: invokevirtual #3                  // Method java/io/PrintStream.println:(I)V
         8: return

可以看出，此常量值直接被写在内部类的临时变量中，即相当于进行了一次变量copy。

继续阅读“java内部类final语义实现”

guava中的FinalizableReferenceQueue解析

1 引用队列的监控和回调
当创建一个引用队列时，我们需要对这个队列进行监控，即开启一个新的线程来循环判断此队列信息，并从中获取相应的数据信息。在guava中，也是通过创建一个线程然后在循环中进行判断，如下所示(类com.google.common.base.internal.Finalizer)：

    Thread thread = new Thread(finalizer);
    thread.setName(Finalizer.class.getName());
    thread.setDaemon(true);

    thread.start();

即创建一个以finalizer runnable对象的线程，然后启动之，为避免阻止进程结束，采用了后台线程的模式。那在这个finalizer中，其运行如下所示：

while (true) {
      try {
        if (!cleanUp(queue.remove())) {
          break;
        }
      } catch (InterruptedException e) { /* ignore */ }
    }

即不断地获取队列中的数据，然后调用cleanUp方法.而在cleanUp方法中，其实就是调用相应对象的回调方法，即当一个对象已经被gc时的回调。

在guava中，从队列中移除的是一个是reference对象。在java体系中，并没有在reference对象中定义相应的回调方法，因此guava为jdk的reference增加了新的定义接口，称之为FinalizableReference。在这个接口中，即定义了一个相应的回调函数，如下所示：

/** 当引用被gc之后，此方法会被触发调用 */
  void finalizeReferent();

因为增加了新的接口，因此我们自己来使用的话，就即要继承于jdk的weakReference，又要实现此接口。为方便，guava定义了3套与jdk兼容的引用对象。即FinalizableWeakReference，FinalizableSoftReference和FinalizablePhantomReference。可以理解为就是一个对jdk原类型的一个适配。

继续阅读“guava中的FinalizableReferenceQueue解析”

ReferenceQueue的使用

1 何为ReferenceQueue

在java的引用体系中，存在着强引用，软引用，虚引用，幽灵引用，这4种引用类型。在正常的使用过程中，我们定义的类型都是强引用的，这种引用类型在回收中，只有当其它对象没有对这个对象的引用时，才会被GC回收掉。简单来说，对于以下定义：

Object obj = new Object();
Ref ref = new Ref(obj);

在这种情况下，如果ref没有被GC，那么obj这个对象肯定不会GC的。因为ref引用到了obj。如果obj是一个大对象呢，多个这种对象的话，应用肯定一会就挂掉了。

那么，如果我们希望在这个体系中，如果obj没有被其它对象引用，只是在这个Ref中存在引用时，就把obj对象gc掉。这时候就可以使用这里提到的Reference对象了。

我们希望当一个对象被gc掉的时候通知用户线程，进行额外的处理时，就需要使用引用队列了。ReferenceQueue即这样的一个对象，当一个obj被gc掉之后，其相应的包装类，即ref对象会被放入queue中。我们可以从queue中获取到相应的对象信息，同时进行额外的处理。比如反向操作，数据清理等。

2 使用队列进行数据监控

一个简单的例子，通过往map中放入10000个对象，每个对象大小为1M字节数组。使用引用队列监控被放入的key的回收情况。代码如下所示：

继续阅读“ReferenceQueue的使用”

Java字节码中的一些特定处理

我们在阅读JAVA字节码时，应该会对其中的一些设定有疑问。为什么是这样的呢，这里从我个人的理解对其中的一些名词进行理解，同时也方便在阅读此书的读者参考。书名为《Java虚拟机规范(Java SE 7版)》

本文包括的一些描述为以下列表

  • 常量池大小设定
  • stackMapTable属性
  • new指令后的dup
  • attribute属性
  • long和double的特殊处理
  • monitorenter和monitorexit的使用场景
  • enclosingMethod属性
  • localVariableTable和localVariableTypeTable
  • constantValue属性

常量池大小设定
常量池的大小的虽然为N，但实际的常量数量即为N-1，但并不是说它的下标值为0到N-1，它的下标是从1到N-1。这里面省略了下标值为0的值，虽然字节码中没有此值。我们可以认为下标为0的值即代表某一种null值。包括其它地方进行引用时，也采用的这个位置处理。如字节码中常量池大小为26，那么最后一个下标肯定为25.

继续阅读“Java字节码中的一些特定处理”