On Universal Classes of Extremely Random Constant-Time Hash Functions
From MaRDI portal
Publication:4651478
DOI10.1137/S0097539701386216zbMath1082.68129MaRDI QIDQ4651478
Publication date: 21 February 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
universal hash functions; hashing; hash functions; limited independence; optimal speedup; PRAM emulation; storage-time tradeoff
68W40: Analysis of algorithms
68R10: Graph theory (including graph drawing) in computer science
68W10: Parallel algorithms in computer science
68P20: Information storage and retrieval of data
68W20: Randomized algorithms
Related Items
Explicit and efficient hash families suffice for cuckoo hashing with a stash, Balanced allocation and dictionaries with tightly packed constant size bins, Derandomized constructions of \(k\)-wise (almost) independent permutations