关键词: 完美哈希函数, 多极相关图, 大规模词典, 平滑

Abstract:

In the hash function, if there are two different words are  mapped into the same slot, we call it a conflict. When the hash function appears in the conflict, it slows the dictionary’s finding speed. Since the perfect hash function completely avoids the conflict, it is used popularly in the application of high function demands. So a perfect hash function based on multistage dependency graphs is presented in this paper. Each character (except for the first one) of a key is smoothed into two smoothed characters using two different smoothing functions. A multistage dependency graph is constructed. The degree of the vertices in the multistage dependency graph of the smoothed keyset is much more evenly distributed, so that a perfect hash function is easier to obtain. The perfect hash function is promising to give solution to large keysets. The load factor remains still high even for huge keysets over large charactersets. Experiments indicate that the load factor is competitive, and meanwhile its working space is less than that of the existing hash functions.

Key words: perfect hash function;multistage dependency graph;lagerscale