文献类型：期刊文章

作　　者：张朝霞[1] 刘耀军[1]

机构地区：[1]太原师范学院计算机系,太原030012

出　　处：《计算机应用》

年　　份：2010

卷　　号：30

期　　号：11

起止页码：2965-2966

语　　种：中文

收录情况：AJ、BDHX、BDHX2008、CSA、CSA-PROQEUST、CSCD、CSCD2011_2012、IC、INSPEC、JST、RCCSE、ZGKJHX、ZMATH、核心刊

摘　　要：为了提高解决哈希冲突的效率,在冲突解决机制和数据元素被查找的先验概率的基础上,结合堆排序的优点,提出了一种更有效的处理哈希冲突的方法,称其为以先验概率为基础的哈希大顶堆查找。该方法首先依据关键字被查的先验概率的大小建立相应的哈希大顶堆,然后利用哈希大顶堆进行查找。最后通过严密的效率分析可看出:该方法在最坏的情况下的时间复杂度才为O(nlogn),不但降低了冲突时执行查询的查找长度,从而降低查询响应的时间复杂度,而且该方法对于记录数越大的文件越适用。

关 键 词：链地址法  哈希冲突 先验概率 哈希查找 哈希平衡树  

分 类 号：TP311.13]