Content deleted Content added
LouScheffer (talk | contribs) →Minimum spanning trees: Add a hash table scheme that is great in theory but too complex to be used in practice |
LouScheffer (talk | contribs) →Hash tables: Add reference for provably best |
||
Line 47:
=== 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
| last = Bender
| first = Michael
| |||