论文部分内容阅读
提出了一种反向Hash链遍历的时间、空间复杂度优化算法．采用堆栈操作实现了高效的反向Hash链遍历，并将Hash链遍历过程映射到了二叉树的后序遍历过程，利用二叉树性质对存储和计算性能进行了理论化分析和证明．分析证明结果表明，遍历对长为n的反向Hash链时，算法只需要存储[lbn1＋1个节点值，并且进行不多于（[bn]／2＋1）n次Hash计算次数．相比同类其他算法，该算法并不要求链长为2的整数次方．通过对算法进行基于k叉树（k≥3）的扩展，进一步将存储空间降低到[logk[（k-1）n＋1]l，但总计算次