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

Abstract: 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.

Key words: chain addressing, hash collision, prior probability, hash search, hash AVL tree