基于线性探测再散列的哈希表查找效率浅析

哈希表的理想情况是无需比较一次存取便能找到所查的记录,但是在实际应用中,哈希表通常存在冲突的情况,这就需要反复查找处理冲突。一般的搜索方法,在搜索时需进行关键字的比较。这一类建立在比较基础上的搜索方法,其效率依赖于搜索过程中所进行的比较次数。而通过使用哈希表人们可以不经任何比较,一次存取便能得到所需的信息,从而大大提高了搜索的效率。然而,建立哈希表不可能没有冲突,解决冲突则会产生诸如堆积、二次聚集等现象,降低了查找效率。文中通过举例阐明了线性探测再散列构造哈希表的方法,并详细地分析了查找成功时和查找失败时的ASL。

改进的国际数据加密算法的子密钥扩展算法

提出了一种改进的国际数据加密算法(International data encryption algorithm,IDE-A)子密钥扩展算法。该算法采用伪随机序列产生具有无序性的子密钥,令攻击者无法有效地分析子密钥中初始密钥位的位置,也无法确定弱密钥的位置。无序的子密钥破坏了针对性攻击的攻击条件,使这些攻击无效。在只有伪随机序列产生的子密钥中,对初始密钥使用频率的不同会导致新弱密钥类的产生,因此引入线性探测再散列来防止该现象的发生。对该算法进行的验证性攻击实验及安全性、效率性分析都表明该算法是安全高效的。

二叉树CreateBTree算法的改进

在分析二叉树的 Create BTree算法的基础上 ,利用线性探测再散列方法对 Create B-Tree算法的中序遍历序列进行预处理来改进 Create BTree算法 ,使得改进后的 Create BTree算法在最差情况下 ,时间复杂度由 O(N 2 )降为 O(N )。