Linear Hashing Is Awesome

descriptionPublicationkeyboard_double_arrow_right Article , Preprint , Conference object 01 Oct 2016Embargo end date: 01 Jan 2017 Denmark Publisher:IEEEJournal:2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)Funded by:IRFD | unidentified

Authors: Mathias Bæk Tejs Knudsen;

doi: 10.1109/focs.2016.45 , 10.1137/17m1126801 , 10.48550/arxiv.1706.02783

arXiv: 1706.02783

Linear Hashing Is Awesome

- Summary
- Subjects
- Metrics

Abstract

We consider the hash function $h(x) = ((ax+b) \bmod p) \bmod n$ where $a,b$ are chosen uniformly at random from $\{0,1,\ldots,p-1\}$. We prove that when we use $h(x)$ in hashing with chaining to insert $n$ elements into a table of size $n$ the expected length of the longest chain is $\tilde{O}\!\left(n^{1/3}\right)$. The proof also generalises to give the same bound when we use the multiply-shift hash function by Dietzfelbinger et al. [Journal of Algorithms 1997].

A preliminary version appeared at FOCS'16

Country

Denmark

Related Organizations

Keywords

FOS: Computer and information sciences, Data structures, Analysis of algorithms and problem complexity, Randomized algorithms, Hashing with chaining, hashing with chaining, hashing, linear hashing, Hashing, Computer Science - Data Structures and Algorithms, additive combinatorics, Analysis of algorithms, Data Structures and Algorithms (cs.DS), Linear hashing

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	3
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average