Bounds for c-Ideal Hashing
Authors:
Preprint
Abstract
In this paper, we analyze hashing from a worst-case perspective. To this end, we study a new property of hash families that is strongly related to d-perfect hashing, namely c-ideality. On the one hand, this notion generalizes the definition of perfect hashing, which has been studied extensively; on the other hand, it provides a direct link to the notion of c-approximativity. We focus on the usually neglected case where the average load αis at least 1 and prove upper and lower parametrized bounds on the minimal size of c-ideal hash families. As an aside, we show how c-ideality helps to analyze the advice complexity of hashing. The concept of advice, introduced a decade ago, lets us measure the information content of an online problem. We prove hashing's advice complexity to be linear in the hash table size.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Beating Fredman-Komlós for perfect k-hashingJournal of Combinatorial Theory, Series A, 2022
- An Introduction to Online Computation2016
- Algorithmen und Datenstrukturen2014
- Algorithms and Data Structures2008
- Splitters and near-optimal derandomization2002
- Perfect Hash Families: Probabilistic Methods and Explicit ConstructionsJournal of Combinatorial Theory, Series A, 2000
- “Balls into Bins” — A Simple and Tight Analysis1998
- The Spatial Complexity of Oblivious k-Probe Hash FunctionsSIAM Journal on Computing, 1990
- Data Structures and Algorithms 11984
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979