Minimala perfekta hashfunktioner används för minneseffektiv lagring och snabb hämtning av objekt från statiska uppsättningar. Vi presenterar en oändlig familj av effektiva och praktiska algoritmer för att skapa ordning bevara minimala perfekta hashfunktioner. Vi visar att nästan alla medlemmar av familjen konstruerar utrymme och tid optimal ordning bevara minimala perfekta hash funktioner, och vi identifierar den med minimala konstanter. Familjemedlemmar skapar en hashfunktion i två steg. Först en speciell typ av funktion i en r-graf beräknas probabilistiskt. Sedan förfinas denna funktion deterministiskt till en minimal perfekt hashfunktion. Vi ger starka teoretiska bevis för att det första steget använder linjär slumpmässig tid. Det andra steget löper i linjär deterministisk tid. Familjen har inte bara teoretisk betydelse, utan erbjuder också den snabbaste kända metoden för att generera perfekta hashfunktioner.
I synnerhet kan MWHC REF generera orderbevarande minimala perfekta hashfunktioner med hjälp av en slumpmässig hypergraf.
A Family of Perfect Hashing Methods
{'venue': 'Comput. J.', 'journal': 'Comput. J.', 'mag_field_of_study': ['Computer Science']}