概述
HashTree 是 JMeter 执行测试依赖的数据结构，在执行测试之前进行配置测试数据，HashTree 将数据组织到一个递归树结构中，并提供了操作该结构的方法。
API地址： http://jmeter.apache.org/api/org/apache/jorphan/collections/HashTree.html
HashTree数据结构
理论基础
在各种介绍里的都比较抽象，其实没有那么难，这里进行一个最简单的说明。
【质数分辨定理】
简单地说就是：n个不同的质数可以“分辨”的连续整数的个数和他们的乘积相等。“分辨”就是指这些连续的整数不可能有完全相同的余数序列。
在将一个数进行 Hash 的时候，对于数，当一个质数不够用的时候，可以加上第二个质数，用两个 mod 来确定该数据在库中的位置。那么这里需要简单的解释一下，对于一个质数 x，它的 mod 有 [ 0 .. x - 1 ] x 种；所以对于两个质数 x 和 y，能存储的无一重复的数据有 x y 个，其实也就是开一个 xy 的二维数组。但是当数据极其多时，用两个质数去 mod 显然也是有不够的时候，就还要再加一个。
为了便于查找，选取最小的十个质数，也就是 2，3，5，7，11，13，17，23，29，31 来mod，能包括的数就有 10555815270 个，已经远超出 longint 了。
也就是说，如果我们开一个十维数组，那么取到一个数的效率就是 O( 1 )！但是那样显然太浪费空间了，就可以用到树。
同一节点中的子节点，从左到右代表不同的余数结果。
例如：第二层节点下有三个子节点。那么从左到右分别代表：除 3 余 0，除 3 余 1 和除 3 余 2。
对质数的余数决定了处理的路径。
例如：某个数来到第二层子节点，那么它要做取余操作，然后再决定从哪个子节点向下搜寻。如果这个数是 12 那么它需要从第一个子节点向下搜索；如果这个数是7那么它需要从第二个子节点向下搜索；如果这个数是32那么它需要从第三个子节点向下搜索。
这就是一个 HashTree 了。
优点
结构简单
从 HashTree 的结构来说，非常的简单。每层节点的子节点个数为连续的质数。子节点可以随时创建。因此 HashTree 的结构是动态的，也不像某些 Hash 算法那样需要长时间的初始化过程。HashTree 也没有必要为不存在的关键字提前分配空间。
需要注意的是 HashTree 是一个单向增加的结构，即随着所需要存储的数据量增加而增大。即使数据量减少到原来的数量，但是 HashTree 的总节点数不会减少。这样做的目的是为了避免结构的调整带来的额外消耗。
查找迅速
从算法过程我们可以看出，对于整数，HashTree 层级最多能增加到10。因此最多只需要十次取余和比较操作，就可以知道这个对象是否存在。这个在算法逻辑上决定了 HashTree 的优越性。
一般的树状结构，往往随着层次和层次中节点数的增加而导致更多的比较操作。操作次数可以说无法准确确定上限。而 HashTree 的查找次数和元素个数没有关系。如果元素的连续关键字总个数在计算机的整数（32bit）所能表达的最大范围内，那么比较次数就最多不会超过10次，通常低于这个数值。
结构不变
HashTree 在删除的时候，并不做任何结构调整。这个也是它的一个非常好的优点。常规树结构在增加元素和删除元素的时候都要做一定的结构调整，否则他们将可能退化为链表结构，而导致查找效率的降低。HashTree 采取的是一种“见缝插针”的算法，从来不用担心退化的问题，也不必为优化结构而采取额外的操作，因此大大节约了操作时间。
缺点
非排序性
HashTree 不支持排序，没有顺序特性。如果在此基础上不做任何改进的话并试图通过遍历来实现排序，那么操作效率将远远低于其他类型的数据结构。
应用
HashTree 可以广泛应用于那些需要对大容量数据进行快速匹配操作的地方。例如：数据库索引系统、短信息中的收条匹配、大量号码路由匹配、信息过滤匹配。HashTree 不需要额外的平衡和防止退化的操作，效率十分理想。
源码分析
项目位置
HashTree 类用于创建测试对象的树结构。树中的每个元素也是树下一个节点的键。它提供了许多方法来添加对象和分支，以及许多检索的方法。HashTree 为了方便的原因实现了映射接口。特别是 traverse(HashTreeTraverser)方法，它提供了一种方便的方法，通过实现 HashTreeTraverser 接口来遍历任何 HashTree，以便在树上执行一些操作，或者从树中提取信息。
实现的接口
public class HashTree implements Serializable, Map<Object, HashTree>, Cloneable {
}
实现Serializable接口
该接口仅为标记接口,不包含任何方法定义,表示该类可以序列化。
/**
* Method readObject.
*
* 序列化的目的是将一个实现了Serializable接口的对象转换成一个字节序列,可以把该字节序列保存起来(例如:保存在一个文件里),以后可以随时将该字节序列恢复为原来的对象。
* 甚至可以将该字节序列放到其他计算机上或者通过网络传输到其他计算机上恢复，只要该计算机平台存在相应的类就可以正常恢复为原来的对象
*
* @param ois
* the stream to read the objects from
* @throws ClassNotFoundException
* when the class for the deserialization can not be found
* @throws IOException
* when I/O error occurs
*/
private void readObject(ObjectInputStream ois) throws ClassNotFoundException, IOException {
ois.defaultReadObject();
}
private void writeObject(ObjectOutputStream oos) throws IOException {
oos.defaultWriteObject();
}
实现Map接口
Map 和 HashTree 之间的主要区别在于 HashTree 将数据组织成递归树结构，并提供操作该结构的方法。
实现Cloneable接口
在此你需要了解Java对象深浅拷贝的概念
具体参考API：
https://docs.oracle.com/javase/7/docs/api/java/lang/Cloneable.html
JMX文件
JMeterEngine 只依赖 HashTree，可以从创建的 jmx 文件中获知，hashtree 贯穿整个 jmx 文件中
gui.jmx 的 xml 结构如下:
<hashTree>
<TestPlan ...>
...
</TestPlan>
<hashTree>
<ThreadGroup ...>
...
</ThreadGroup>
**<hashTree/>**
</hashTree>
</hashTree>
请注意 HashTree 元素的嵌套。当在 JMeter GUI 中打开时，元素彼此嵌套。
一个示例：
<?xml version="1.0" encoding="UTF-8"?>
<jmeterTestPlan version="1.2" properties="5.0" jmeter="5.0 r1840935">
<hashTree>
<TestPlan guiclass="TestPlanGui" testclass="TestPlan" testname="TestBaidu.Com" 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="User Defined Variables" enabled="true">
<collectionProp name="Arguments.arguments"/>
</elementProp>
<stringProp name="TestPlan.user_define_classpath"></stringProp>
</TestPlan>
<hashTree>
<ThreadGroup guiclass="ThreadGroupGui" testclass="ThreadGroup" testname="Thread Group" enabled="true">
<stringProp name="ThreadGroup.on_sample_error">continue</stringProp>
<elementProp name="ThreadGroup.main_controller" elementType="LoopController" guiclass="LoopControlPanel" testclass="LoopController" testname="Loop Controller" enabled="true">
<boolProp name="LoopController.continue_forever">false</boolProp>
<stringProp name="LoopController.loops">1</stringProp>
</elementProp>
<stringProp name="ThreadGroup.num_threads">1</stringProp>
<stringProp name="ThreadGroup.ramp_time">1</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 Request" enabled="true">
<elementProp name="HTTPsampler.Arguments" elementType="Arguments" guiclass="HTTPArgumentsPanel" testclass="Arguments" enabled="true">
<collectionProp name="Arguments.arguments"/>
</elementProp>
<stringProp name="HTTPSampler.domain">www.baidu.com</stringProp>
<stringProp name="HTTPSampler.port">80</stringProp>
<stringProp name="HTTPSampler.protocol">http</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="View Results Tree" 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>
code.jmx 的 xml 结构如下:
<org.apache.jorphan.collections.HashTree>
<TestPlan ...>
...
</TestPlan>
**<org.apache.jorphan.collections.HashTree/>**
<ThreadGroup ...>
...
</ThreadGroup>
**<org.apache.jorphan.collections.HashTree/>**
</org.apache.jorphan.collections.HashTree>
一个示例：
<?xml version="1.0" encoding="UTF-8"?>
<jmeterTestPlan version="1.2" properties="4.0" jmeter="4.0 r1823414">
<org.apache.jorphan.collections.HashTree>
<TestPlan guiclass="TestPlanGui" testclass="TestPlan" testname="创建JMeter脚本">
<elementProp name="TestPlan.user_defined_variables" elementType="Arguments" guiclass="ArgumentsPanel" testclass="Arguments" testname="User Defined Variables" enabled="true">
<collectionProp name="Arguments.arguments"/>
</elementProp>
</TestPlan>
<org.apache.jorphan.collections.HashTree>
<ThreadGroup guiclass="ThreadGroupGui" testclass="ThreadGroup" testname="Example Thread Group">
<intProp name="ThreadGroup.num_threads">1</intProp>
<intProp name="ThreadGroup.ramp_time">1</intProp>
<elementProp name="ThreadGroup.main_controller" elementType="LoopController" guiclass="LoopControlPanel" testclass="LoopController">
<boolProp name="LoopController.continue_forever">false</boolProp>
<intProp name="LoopController.loops">1</intProp>
</elementProp>
</ThreadGroup>
<org.apache.jorphan.collections.HashTree>
<HTTPSamplerProxy guiclass="HttpTestSampleGui" testclass="HTTPSamplerProxy" testname="Open qq.com">
<elementProp name="HTTPsampler.Arguments" elementType="Arguments">
<collectionProp name="Arguments.arguments"/>
</elementProp>
<stringProp name="HTTPSampler.domain">qq.com</stringProp>
<intProp name="HTTPSampler.port">80</intProp>
<stringProp name="HTTPSampler.path">/</stringProp>
<stringProp name="HTTPSampler.method">GET</stringProp>
</HTTPSamplerProxy>
<org.apache.jorphan.collections.HashTree/>
<HTTPSamplerProxy guiclass="HttpTestSampleGui" testclass="HTTPSamplerProxy" testname="Open baidu.com">
<elementProp name="HTTPsampler.Arguments" elementType="Arguments">
<collectionProp name="Arguments.arguments"/>
</elementProp>
<stringProp name="HTTPSampler.domain">baidu.com</stringProp>
<intProp name="HTTPSampler.port">80</intProp>
<stringProp name="HTTPSampler.path">/</stringProp>
<stringProp name="HTTPSampler.method">GET</stringProp>
</HTTPSamplerProxy>
<org.apache.jorphan.collections.HashTree/>
</org.apache.jorphan.collections.HashTree>
</org.apache.jorphan.collections.HashTree>
</org.apache.jorphan.collections.HashTree>
</jmeterTestPlan>
HashTree 的结构一般是 TestPlan-->ThreadGroup-->Sampler-->ResultCollector
构造函数
构造函数有多种形式：
HashTree(Map _map, Object key)：若 HashTree 不为空则使用 HashTree，若 key 不为空则设为 top-level（root）节点，也可能是空。这个构造函数是最为主要的构造函数，它还有几个变形体都是调用它
/**
* Uses the new HashTree if not null and adds the given object as a
* top-level node if not null
*
* 构造函数
* 若HashTree不为空则使用HashTree
* 若key不为空则设为top-level（root）节点，也可能是空。
* 这个构造函数是最为主要的构造函数，它还有几个变形体都是调用它
*
* @param _map
* the map to be used. If <code>null</code> a new {@link HashMap}
* will be created
* @param key
* the object to be used as the key for the root node (may be
* <code>null</code>, in which case no root node will be created)
*/
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());
}
}
HashTree()：创建空 HashTree，实际调用 HashTree（null，null）
/**
* Creates an empty new HashTree.
*
* 创建空HashTree，实际调用hashTree（null，null）
*/
public HashTree() {
this(null, null);
}
HashTree(Map _map)：允许子类提供 Map 作为参数
/**
* Allow subclasses to provide their own Map.
*
* 允许子类提供Map作为参数
*
* @param _map {@link Map} to use
*/
protected HashTree(Map<Object, HashTree> _map) {
this(_map, null);
}
HashTree(Object key)：创建 HashTree 并将 key 设为 top-level 节点
/**
* Creates a new HashTree and adds the given object as a top-level node.
*
* 创建HashTree并将key设为top-level节点
*
* @param key
* name of the new top-level node
*/
public HashTree(Object key) {
this(new HashMap<Object, HashTree>(), key);
}
HashTree(Collection<?> keys)：创建 HashTree 并且将 keys 中的所有对象设为 top-level 节点
/**
* Creates a new HashTree and adds all the objects in the given collection
* as top-level nodes in the tree.
*
* 创建HashTree并且将keys中的所有对象设为top-level节点
*
* @param keys
* a collection of objects to be added to the created HashTree.
*/
public HashTree(Collection<?> keys) {
data = new HashMap<>();
for (Object o : keys) {
data.put(o, new HashTree());
}
}
HashTree(Object[] keys)：创建 HashTree 并且将 keys 中的所有对象设为 top-level节点
/**
* Creates a new HashTree and adds all the objects in the given array as
* top-level nodes in the tree.
*
* 创建HashTree并且将keys中的所有对象设为top-level节点
*
* @param keys
* array with names for the new top-level nodes
*/
public HashTree(Object[] keys) {
data = new HashMap<>();
for (Object key : keys) {
data.put(key, new HashTree());
}
}
主要方法
putAll
public void putAll(Map<?, ? extends HashTree> map):参数提供的 map 必须是 HashTree 否则会抛出 UnsupportedOperationException 异常。如果 map 是 HashTree 相当于调用 add(HashTree)
/**
* The Map given must also be a HashTree, otherwise an
* UnsupportedOperationException is thrown. If it is a HashTree, this is
* like calling the add(HashTree) method.
*
* 参数提供的map必须是HashTree否则会抛出UnsupportedOperationException异常。
* 如果map是HashTree相当于调用add(HashTree)
*
* @see #add(HashTree)
* @see java.util.Map#putAll(Map)
*/
@Override
public void putAll(Map<?, ? extends HashTree> map) {
if (map instanceof HashTree) {
this.add((HashTree) map);
} else {
throw new UnsupportedOperationException("can only putAll other HashTree objects");
}
}
containsValue
containsValue(Object value):是否包含值。实际调用的是 map 的containsKey，此函数并没有多大用处；
/**
* Implemented as required by the Map interface, but is not very useful
* here. All 'values' in a HashTree are HashTree's themselves.
*
* 是否包含值。实际调用的是map的containsKey，此函数并没有多大用处
*
* @param value
* Object to be tested as a value.
* @return True if the HashTree contains the value, false otherwise.
* @see java.util.Map#containsValue(Object)
*/
@Override
public boolean containsValue(Object value) {
return data.containsValue(value);
}
put
put(Object key, HashTree value):相当于调用 add(key,value)，参考 map 的 V put(K key, V value)
/**
* This is the same as calling HashTree.add(key,value).
*
* 相当于调用add(key,value)，参考map的V put(K key, V value)；
*
* @param key
* to use
* @param value
* to store against key
* @see java.util.Map#put(Object, Object)
*/
@Override
public HashTree put(Object key, HashTree value) {
HashTree previous = data.get(key);
add(key, value);
return previous;
}
add
添加，存在多个重载函数，提供不同的途径进行添加。
add(java.util.Collection<?> keys): 在当前级别向 HashTree 添加一堆 keys。
/**
* Adds a bunch of keys into the HashTree at the current level.
*
* @param keys
* Collection of Keys to be added to HashTree.
*/
public void add(Collection<?> keys) {
for (Object o : keys) {
add(o);
}
}
add(java.util.Collection<?> treePath, java.util.Collection<?> values)：使用给定路径将一系列节点添加到 HashTree 中。
/**
* Adds a series of nodes into the HashTree using the given path. The first
* argument is an array that represents a path to a specific node in the
* tree. If the path doesn't already exist, it is created (the objects are
* added along the way). At the path, all the objects in the second argument
* are added as nodes.
*
* @param treePath
* an array of objects representing a path
* @param values
* collection of values to be added as keys to bottom-most node
*/
public void add(Object[] treePath, Collection<?> values) {
if (treePath != null) {
add(Arrays.asList(treePath), values);
}
}
add(HashTree newTree)：将给定树的所有节点和分支添加到此树。
/**
* Adds all the nodes and branches of the given tree to this tree. Is like
* merging two trees. Duplicates are ignored.
*
* @param newTree the tree to be added
*/
public void add(HashTree newTree) {
for (Object item : newTree.list()) {
add(item).add(newTree.getTree(item));
}
}
...还有好几个，就不一一列举了
set
设置，存在多个重载函数，提供不同的途径进行设置
set(java.util.Collection<?> values)：将当前树的节点设置为给定集合的对象。
/**
* Sets the nodes of the current tree to be the objects of the given
* collection. Any nodes previously in the tree are removed.
*
* @param values
* Collection of objects to set as nodes.
*/
public void set(Collection<?> values) {
clear();
this.add(values);
}
...还有好几个，就不一一列举了
getTree
获取树的 map，也存在多个重载
getTree(java.util.Collection<?> treePath):通过一次一个键地递归 HashTree 结构，获取映射到 SortedSet 中 最后一个键的 HashTree 对象。
/**
* Gets the HashTree object mapped to the last key in the SortedSet by
* recursing through the HashTree structure one key at a time.
*
* @param treePath
* Collection of keys
* @return HashTree at the end of the recursion
*/
public HashTree getTree(Collection<?> treePath) {
return getTreePath(treePath);
}
getTree(java.lang.Object key):获取映射到给定键的 HashTree。
/**
* Gets the HashTree mapped to the given key.
*
* 获取树的map，也存在多个重载
*
* @param key
* Key used to find appropriate HashTree()
* @return the HashTree for <code>key</code>
*/
public HashTree getTree(Object key) {
return data.get(key);
}
getTree(java.lang.Object[] treePath):通过一次一个键地递归 HashTree 结构，获取映射到数组中最后一个键的 HashTree 对象。
/**
* Gets the HashTree object mapped to the last key in the array by recursing
* through the HashTree structure one key at a time.
*
* @param treePath
* array of keys.
* @return HashTree at the end of the recursion.
*/
public HashTree getTree(Object[] treePath) {
if (treePath != null) {
return getTree(Arrays.asList(treePath));
}
return this;
}
traverseInto
完成树遍历和执行的递归方法对 HashTreeTraverser 的回调。使用深度优先遍历 hashTree
traverse(HashTreeTraverser visitor)：允许 HashTreeTraverser 接口的任何实现轻松遍历（深度优先）HashTree 的所有节点。
/**
* Allows any implementation of the HashTreeTraverser interface to easily
* traverse (depth-first) all the nodes of the HashTree. The Traverser
* implementation will be given notification of each node visited.
*
* @see HashTreeTraverser
* @param visitor
* the visitor that wants to traverse the tree
*/
public void traverse(HashTreeTraverser visitor) {
for (Object item : list()) {
visitor.addNode(item, getTree(item));
getTree(item).traverseInto(visitor);
}
}
/**
* The recursive method that accomplishes the tree-traversal and performs
* the callbacks to the HashTreeTraverser.
*
* 完成树遍历和执行的递归方法对HashTreeTraverser的回调。使用深度优先遍历hashTree
*
* @param visitor
* the {@link HashTreeTraverser} to be notified
*/
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，以便在树上执行一些操作，或者从树中提取信息，去掉没用的节点元素，替换掉可以替换的控制器，这些都是通过递归实现的。
参考资料：
