基于多级相关图的大规模词典完美哈希函数构造算法

摘要

在哈希函数中,如果两个不同的单词被映射到同一个槽,那么我们称为冲突.当哈希函数存在冲突时,将降低词典查找的速度.由于完美哈希函数完全避免了冲突,因此在许多对查找性能要求较高的应用中广泛使用.本文就此提出了一种基于多级相关图的大规模词典完美哈希函数的构造算法.词典单词的每个字符(首字母除外)都用两个平滑函数平滑为两个字符,构建平滑后词典对应的多级相关图,多级相关图的结点度都比较小,而且分布比较均匀,因此更容易生成完美哈希函数.实验表明:基于多级相关图的哈希函数构造算法适用于大规模词典,填充因子接近1,同时工作空间比已有算法都要小.