数据流重组中Hash-Splay查找算法

Hash-splay search algorithm in data-stream reassembling

针对高速网络取证目前所面临的问题,围绕提高网络数据流重组效率,在数据流重组算法中分析比较了几种典型的查找算法,并将Hash表和Splay树组合成Hash-Splay查找算法.该算法首先建立Hash表,然后将所有的TCP连接结点分配到各个表项,每个表项用Splay树将该表项的所有连接结点组织起来.查找时,根据连接标识通过Hash函数计算出Hash地址,再对该Hash地址对应的Splay树进行查找,找到后按照Splay树的操作规则进行查找、插入和删除等操作.由于根据连接标识找到对应Splay树的时间开销很小,可以忽略不计,因此Hash-Splay算法的复杂度可以看作是每棵Splay树操作的平均复杂度,算法同时具有Hash表和Splay树的优点,查找效率比Hash表和Splay树的都高.

Against problems existed in high-speed network forensics, data-stream reassembling algorithm is discussed in terms of improving performance of reassembling. Combining the merits of hash table and splay tree, Hash-Splay search algorithm is given out based on analysis of several search algorithms to improve performance. Firstly, Hash table is established, and all TCP（transmission control protocol） connection points are assigned to individual table item, Then, all connection points of the table item will be organized with the Splay tree. While searching, the operations such as search, insertion and deletion et al will be based on the splay tree corresponding to a hash address that is acquired by using hash function according to the connection marked flag. Because the time for finding the corresponding splay tree is very small that can be ignored, therefore the Hash-Splay search algorithm＇s complexity can be regarded as the Splay tree algorithm＇s complexity. The algorithm has the advantages of Hash table and Splay tree. However, its efficiency is higher than both.