A backtracking method for constructing perfect hash functions from a set of mapping functions

DOI10.1007/BF01934995MaRDI QIDQ1059411zbMATH OpenOpenAlexFDO

Authors J. Blot

Publication date 1985

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01934995

zbMATH Keywords

backtrackingperfect hashing

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20)

Review text

Given a set of mapping functions \(h_ j(k)\) from key space to address space (AS) the problem of constructing a perfect hashing scheme is to find a hash indicator table (HIT): iff HIT \([h_ j(k)]=j\) then k is stored in AS \([h_ j(k)].\) A backtracking method superior to those proposed previously (single-pass and multipass methods) is presented, which can always find for given mapping functions a perfect hash function when such a function does exist.

Recommendations

• Collections of Functions for Perfect Hashing
• Perfect hashing
• scientific article; zbMATH DE number 1875411
• A new practical algorithm for the construction of a perfect hash function
• Simple and Space-Efficient Minimal Perfect Hash Functions

Cites work

• Backtrack Programming
• Backtrack programming techniques
• Comments on perfect hashing functions
• scientific article; zbMATH DE number 3690676 (Why is no real title available?)
• scientific article; zbMATH DE number 3466515 (Why is no real title available?)
• scientific article; zbMATH DE number 3471582 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• Perfect hashing functions
• Reciprocal hashing

Cited in

(5)

• Perfect hashing
• An algebraic approach to Cichelli's perfect hashing
• Construct a perfect word hash function in time independent of the size of integers
• Graphs, hypergraphs and hashing
• Combined search and encoding for seeds, with an application to minimal perfect hashing

This page was built for publication: A backtracking method for constructing perfect hash functions from a set of mapping functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1059411)