jmeter源码学习二

hash树

理想的情况是希望不经过任何比较，一次存取便能得到所查的记录，那就必须在记的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和一个唯一的存储位置相对应。因而在查找时，只要根据这个对应关系f找到给定值K的像f(K)。由此，不需要进行比较便可直接取得所查记录。在此，我们称这个对应关系为哈希（Hash）函数，按这个思想建立的表为哈希表。

在哈希表中对于不同的关键字可能得到同一哈希地址，这种现象称做冲突。在一般情况下，冲突只能尽可能地减少，而不能完全避免。因为哈希函数是从关键字集合到地址集合的映像。通常关键字的集合比较大，它的元素包括所有可能的关键字，而地址集合的元素仅为哈希表中的地址值。在一般情况下，哈希函数是一个压缩映像函数，这就不可避免的要产生冲突。

哈希树的理论基础

【质数分辨定理】
简单地说就是：n个不同的质数可以“分辨”的连续整数的个数和他们的乘积相等。“分辨”就是指这些连续的整数不可能有完全相同的余数序列。
avatar
例如：
从2起的连续质数，连续10个质数就可以分辨大约M(10) =23571113171923*29= 6464693230 个数，已经超过计算机中常用整数（32bit）的表达范围。连续100个质数就可以分辨大约M(100) = 4.711930 乘以10的219次方。

插入

我们选择质数分辨算法来建立一棵哈希树。
选择从2开始的连续质数来建立一个十层的哈希树。第一层结点为根结点，根结点下有2个结点；第二层的每个结点下有3个结点；依此类推，即每层结点的子节点数目为连续的质数。到第十层，每个结点下有29个结点。
同一结点中的子结点，从左到右代表不同的余数结果。
例如：第二层结点下有三个子节点。那么从左到右分别代表：除3余0，除3余1，除3余2.
对质数进行取余操作得到的余数决定了处理的路径。

下面我们以随机的10个数的插入为例，来图解HashTree的插入过程
avatar

优点

– 结构简单
从 HashTree 的结构来说，非常的简单。每层节点的子节点个数为连续的质数。子节点可以随时创建。因此 HashTree 的结构是动态的，也不像某些 Hash 算法那样需要长时间的初始化过程。HashTree 也没有必要为不存在的关键字提前分配空间。需要注意的是 HashTree 是一个单向增加的结构，即随着所需要存储的数据量增加而增大。即使数据量减少到原来的数量，但是 HashTree 的总节点数不会减少。这样做的目的是为了避免结构的调整带来的额外消耗。

– 查找迅速
从算法过程我们可以看出，对于整数，HashTree 层级最多能增加到10。因此最多只需要十次取余和比较操作，就可以知道这个对象是否存在。这个在算法逻辑上决定了 HashTree 的优越性。一般的树状结构，往往随着层次和层次中节点数的增加而导致更多的比较操作。操作次数可以说无法准确确定上限。而 HashTree 的查找次数和元素个数没有关系。如果元素的连续关键字总个数在计算机的整数（32bit）所能表达的最大范围内，那么比较次数就最多不会超过10次，通常低于这个数值。

– 结构不变
HashTree 在删除的时候，并不做任何结构调整。这个也是它的一个非常好的优点。常规树结构在增加元素和删除元素的时候都要做一定的结构调整，否则他们将可能退化为链表结构，而导致查找效率的降低。HashTree 采取的是一种“见缝插针”的算法，从来不用担心退化的问题，也不必为优化结构而采取额外的操作，因此大大节约了操作时间。

缺点

非排序性
HashTree 不支持排序，没有顺序特性。如果在此基础上不做任何改进的话并试图通过遍历来实现排序，那么操作效率将远远低于其他类型的数据结构。

应用

HashTree 可以广泛应用于那些需要对大容量数据进行快速匹配操作的地方。例如：数据库索引系统、短信息中的收条匹配、大量号码路由匹配、信息过滤匹配。HashTree 不需要额外的平衡和防止退化的操作，效率十分理想。

Trie树

字典树（Trie）可以保存一些字符串->值的对应关系。基本上，它跟 Java 的 HashMap 功能相同，都是 key-value 映射，只不过 Trie 的 key 只能是字符串。Trie 的强大之处就在于它的时间复杂度。它的插入和查询时间复杂度都为 O(k) ，其中 k 为 key 的长度，与 Trie 中保存了多少个元素无关。Hash 表号称是 O(1) 的，但在计算 hash 的时候就肯定会是 O(k) ，而且还有碰撞之类的问题；Trie 的缺点是空间消耗很高。
Trie树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
以英文单词构建的字典树为例，这棵Trie树中每个结点包括26个孩子结点，因为总共有26个英文字母(假设单词都是小写字母组成)。
下面我们有and,as,at,cn,com这些关键词，那么如何构建trie树呢？
avatar
avatar
从上面的图中，我们或多或少的可以发现一些好玩的特性。
第一：根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
第二：从根节点到某一节点，路径上经过的字符连接起来，就是该节点对应的字符串。
第三：每个单词的公共前缀作为一个字符节点保存。

源码分析

项目位置

HashTree 类用于创建测试对象的树结构。树中的每个元素也是树下一个节点的键。它提供了许多方法来添加对象和分支，以及许多检索的方法。HashTree 为了方便的原因实现了映射接口。特别是 traverse(HashTreeTraverser)方法，它提供了一种方便的方法，通过实现 HashTreeTraverser 接口来遍历任何 HashTree，以便在树上执行一些操作，或者从树中提取信息。

JMX文件

 <hashTree>
    <TestPlan ...>
    </TestPlan>
    <hashTree>
    <ThreadGroup ...>
    </ThreadGroup>
    <hashTree/>
    </hashTree>
</hashTree>

示例

<?xml version="1.0" encoding="UTF-8"?>
<jmeterTestPlan version="1.2" properties="5.0" jmeter="5.0">
  <hashTree>
    <TestPlan guiclass="TestPlanGui" testclass="TestPlan" testname="测试计划" enabled="true">
      <stringProp name="TestPlan.comments"></stringProp>
      <boolProp name="TestPlan.functional_mode">false</boolProp>
      <boolProp name="TestPlan.tearDown_on_shutdown">true</boolProp>
      <boolProp name="TestPlan.serialize_threadgroups">false</boolProp>
      <elementProp name="TestPlan.user_defined_variables" elementType="Arguments" guiclass="ArgumentsPanel" testclass="Arguments" testname="用户定义的变量" enabled="true">
        <collectionProp name="Arguments.arguments"/>
      </elementProp>
      <stringProp name="TestPlan.user_define_classpath"></stringProp>
    </TestPlan>
    <hashTree>
      <ThreadGroup guiclass="ThreadGroupGui" testclass="ThreadGroup" testname="线程组" enabled="true">
        <stringProp name="ThreadGroup.on_sample_error">continue</stringProp>
        <elementProp name="ThreadGroup.main_controller" elementType="LoopController" guiclass="LoopControlPanel" testclass="LoopController" testname="循环控制器" enabled="true">
          <boolProp name="LoopController.continue_forever">false</boolProp>
          <stringProp name="LoopController.loops">1</stringProp>
        </elementProp>
        <stringProp name="ThreadGroup.num_threads">100</stringProp>
        <stringProp name="ThreadGroup.ramp_time">5</stringProp>
        <boolProp name="ThreadGroup.scheduler">false</boolProp>
        <stringProp name="ThreadGroup.duration"></stringProp>
        <stringProp name="ThreadGroup.delay"></stringProp>
      </ThreadGroup>
      <hashTree>
        <HTTPSamplerProxy guiclass="HttpTestSampleGui" testclass="HTTPSamplerProxy" testname="HTTP请求" enabled="true">
          <elementProp name="HTTPsampler.Arguments" elementType="Arguments" guiclass="HTTPArgumentsPanel" testclass="Arguments" testname="用户定义的变量" enabled="true">
            <collectionProp name="Arguments.arguments"/>
          </elementProp>
          <stringProp name="HTTPSampler.domain">www.baidu.com</stringProp>
          <stringProp name="HTTPSampler.port"></stringProp>
          <stringProp name="HTTPSampler.protocol">https</stringProp>
          <stringProp name="HTTPSampler.contentEncoding"></stringProp>
          <stringProp name="HTTPSampler.path"></stringProp>
          <stringProp name="HTTPSampler.method">GET</stringProp>
          <boolProp name="HTTPSampler.follow_redirects">true</boolProp>
          <boolProp name="HTTPSampler.auto_redirects">false</boolProp>
          <boolProp name="HTTPSampler.use_keepalive">true</boolProp>
          <boolProp name="HTTPSampler.DO_MULTIPART_POST">false</boolProp>
          <stringProp name="HTTPSampler.embedded_url_re"></stringProp>
          <stringProp name="HTTPSampler.connect_timeout"></stringProp>
          <stringProp name="HTTPSampler.response_timeout"></stringProp>
        </HTTPSamplerProxy>
        <hashTree/>
        <ResultCollector guiclass="ViewResultsFullVisualizer" testclass="ResultCollector" testname="察看结果树" enabled="true">
          <boolProp name="ResultCollector.error_logging">false</boolProp>
          <objProp>
            <name>saveConfig</name>
            <value class="SampleSaveConfiguration">
              <time>true</time>
              <latency>true</latency>
              <timestamp>true</timestamp>
              <success>true</success>
              <label>true</label>
              <code>true</code>
              <message>true</message>
              <threadName>true</threadName>
              <dataType>true</dataType>
              <encoding>false</encoding>
              <assertions>true</assertions>
              <subresults>true</subresults>
              <responseData>false</responseData>
              <samplerData>false</samplerData>
              <xml>false</xml>
              <fieldNames>true</fieldNames>
              <responseHeaders>false</responseHeaders>
              <requestHeaders>false</requestHeaders>
              <responseDataOnError>false</responseDataOnError>
              <saveAssertionResultsFailureMessage>true</saveAssertionResultsFailureMessage>
              <assertionsResultsToSave>0</assertionsResultsToSave>
              <bytes>true</bytes>
              <sentBytes>true</sentBytes>
              <url>true</url>
              <threadCounts>true</threadCounts>
              <idleTime>true</idleTime>
              <connectTime>true</connectTime>
            </value>
          </objProp>
          <stringProp name="filename"></stringProp>
        </ResultCollector>
        <hashTree/>
      </hashTree>
    </hashTree>
  </hashTree>
</jmeterTestPlan>

HashTree 的结构一般是 TestPlan–>ThreadGroup–>Sampler–>ResultCollector

源代码

HashTree(Map<Object, HashTree> _map, Object key)：若 HashTree 不为空则使用 HashTree，若 key 不为空则设为 top-level（root）节点，也可能是空。这个构造函数是最为主要的构造函数，它还有几个变形体都是调用它
 private HashTree(Map<Object, HashTree> _map, Object key) {
        if(_map != null) {
            data = _map;
        } else {
            data = new HashMap<>();
        }
        if(key != null) {
            data.put(key, new HashTree());
        }
}
public HashTree getTree(Object[] treePath) {
	if (treePath != null) {
		return getTree(Arrays.asList(treePath));
	}
	return this;
}
traverseInto 完成树遍历和执行的递归方法对 HashTreeTraverser 的回调。使用深度优先遍历 hashTree
public void traverse(HashTreeTraverser visitor) {
	for (Object item : list()) {
		visitor.addNode(item, getTree(item));
		getTree(item).traverseInto(visitor);
	}
}	
traverse(HashTreeTraverser visitor)：允许 HashTreeTraverser 接口的任何实现轻松遍历（深度优先）HashTree 的所有节点。
private void traverseInto(HashTreeTraverser visitor) {
	if (list().isEmpty()) {
		visitor.processPath();
	} else {
		for (Object item : list()) {
			final HashTree treeItem = getTree(item);
			visitor.addNode(item, treeItem);
			treeItem.traverseInto(visitor);
		}
	}
	visitor.subtractNode();
}

clear：清除所有内容的 HashTree
clone：创建此 HashTree 的克隆
createNewTree：从名字可看出，该函数创建一个 tree，也存在多个重载函数，供多种访问方式。
getArray：获取当前HashTree节点的所有keys，同样存在多个重载函数，提供多种访问方式
remove：删除指定分支
replaceKey：替换指定 key
search：在 HashTree 中搜索指定关键字，返回 map 对应的 HashTree 或者null
list：获取 HashTree 中的节点的集合，同样存在多个重载函数，提供多种访问方式
还有对 map 的一些操作，如：hashCode、equals、keySet、size、toString
综上所述，加载 jmx 脚本，本身这个操作非常复杂。jmx 脚本中通常会包含参数化文件，用户自定义的参数化，JMeter 自定义函数，各种 Sampler 的实现，断言，甚至用户自定义的插件等等。
同时还有各种监听接口的初始化。这些都是要找到实现类加载的，HashTree 源码中包含非常多的实现类。遍历任何 HashTree，以便在树上执行一些操作，或者从树中提取信息，去掉没用的节点元素，替换掉可以替换的控制器，这些都是通过递归实现的。

参考文献

https://blog.csdn.net/zuozewei/article/details/86748517