Content deleted Content added
LouScheffer (talk | contribs) →Hash tables: Add reference for provably best |
LouScheffer (talk | contribs) →Hash tables: Add authors for paper |
||
Line 48:
=== Hash tables ===
Researchers have found an algorithm that achieves the provably best-possible<ref>{{cite web |url=https://www.cs.princeton.edu/~hy2/files/dynamic_succinct_dictionary_lower_bound.pdf |title=Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries |author=Tianxiao Li, Jingxun Liang, Huacheng Yu, and Renfei Zhou}}</ref> asymptotic performance in terms of time-space tradeoff.<ref>{{cite arXiv
|
|
| last2 = Farach-Colton
| first2 = Martin
| last3 = Kuszmaul
| first3 =John
| last4 = Kuszmaul
| first4 = William
| last5 = Mingmou
| first5 = Liu
| date = 4 Nov 2021
| title = On the Optimal Time/Space Tradeoff for Hash Tables
| |||