有效的哈希冲突解决办法  

Effective solution to Hash collision

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

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

出　　处：《计算机应用》2010年第11期2965-2966,3004,共3页journal of Computer Applications

摘　　要：为了提高解决哈希冲突的效率,在冲突解决机制和数据元素被查找的先验概率的基础上,结合堆排序的优点,提出了一种更有效的处理哈希冲突的方法,称其为以先验概率为基础的哈希大顶堆查找。该方法首先依据关键字被查的先验概率的大小建立相应的哈希大顶堆,然后利用哈希大顶堆进行查找。最后通过严密的效率分析可看出:该方法在最坏的情况下的时间复杂度才为O(nlogn),不但降低了冲突时执行查询的查找长度,从而降低查询响应的时间复杂度,而且该方法对于记录数越大的文件越适用。To improve the efficiency of Hash conflict-solving, a more effective method to deal with Hash collision was proposed based on a conflict-solving mechanism and the prior probability of the searched elements and combined with the advantages of heap sort. This method was defined as a prior probability-based Hash heap big top, which established a corresponding Hash heap big top based on the prior probability of the searched elements and then began the research with it. The time complexity of searching is O（n log n） at worst. Hence, this algorithm can not only reduce the searching length when conflicts occur so as to shorten the time complexity of searching, but also be applicable to huge sets of keys.

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

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]