摘要
散列函数在查询算法中起着重要作用,基于此的查询算法在理论上可达到常数级时间复杂度。提出了双次线性映射散列函数,和除留余数法、平方取中法、折叠法等常用的散列函数相比,该函数具有单调性,并在一定程度上消除了堆积现象;和线性散列函数相比,该函数具有受数据分布特性影响小,易推广的特点。通过该散列函数,一个待查元素可以在有序序列中被定位到离真实位置偏差很小的范围之内。基于此提出了一种高效的查询算法。
Hash function plays an important role in the query algorithm, and the query algorithms based on it achieves a constant time complexity in theory. This paper proposes a new hash function, which is called double linear mapping hash function, compared with the prior ways, such as division, mid-square, folding, it has the character of monotonic, and reduce the probability of clustering, which is thought to be one of the major drags of hash query. Compared with linear hash functions, it＇s insensitive to data distribution, which make it easier to generalize. Moreover, with the help of this new kind of hash function, the element can be located in a small range beside its real position in sorted sequence.
出处
《南京邮电大学学报（自然科学版）》
2006年第2期92-96,共5页
Journal of Nanjing University of Posts and Telecommunications：Natural Science Edition
关键词
查询算法
散列函数
散列排序
二次线性映射散列函数
堆积
数据分布
Query algorithm
Hash function
Hash sort
Double linear mapping hash function
Clustering
Data distribution
