一种自适应二级散列算法

计算机70%以上的时间在进行查找工作。传统散列算法[1]具有很好的平均时间复杂性,但最坏时间复杂性为O(k),(k为关键字总数)。完美散列算法查找的时间复杂性一般较小,但插入后解决冲突的最坏时间复杂性均在O(k2)以上。本文结合完美散列算法gperf[2],传统散列算法、平衡树[1]等的优点,提出一种自适应二级散列算法,其查找、插入和删除的最坏时间复杂性远低于O(log2k),接近常数,其最坏空间复杂性为O(k).