AN OPTIMAL ALGORITHM FOR GENERATING MINIMAL PERFECT HASH FUNCTIONS

被引：50

作者：

CZECH, ZJ

HAVAS, G

MAJEWSKI, BS

机构：

[1] UNIV QUEENSLAND,KEY CTR SOFTWARE TECHNOL,DEPT COMP SCI,ST LUCIA,QLD 4072,AUSTRALIA

[2] SILESIA TECH UNIV,DEPT COMP SCI,PL-44100 GLIWICE,POLAND

来源：

INFORMATION PROCESSING LETTERS | 1992年 / 43卷 / 05期

基金：

澳大利亚研究理事会;

关键词：

DATA STRUCTURES; PROBABILISTIC ALGORITHMS; ANALYSIS OF ALGORITHMS; HASHING; RANDOM GRAPHS;

D O I：

10.1016/0020-0190(92)90220-P

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A new algorithm for generating order preserving minimal perfect hash functions is presented. The algorithm is probabilistic, involving generation of random graphs. It uses expected linear time and requires a linear number of words to represent the hash function, and thus is optimal up to constant factors. It runs very fast in practice.

引用

页码：257 / 264

页数：8

共 31 条

[1]

BOLLOBAS B, 1985, 17TH P ANN ACM S THE, P224

[2]

Bollobas B., 1985, RANDOM GRAPHS

[3] PERFECT HASHING USING SPARSE-MATRIX PACKING [J].