We show how to implement a dynamic array $A[1, n]$ with symbols from a fixed alphabet $\Sigma$, while supporting $O(1)$-time queries and updates, and using a total space of $$ \log \binom{|\Sigma|}{m} + \left(1 + O\left(\frac{\log \log n}{\log n}\right)\right) \cdot \left(\sum_{\sigma \in \Sigma} f_\sigma \log (n / f_\...
G. Blelloch, Yang Hu, William Kuszmaul et al.· 2 citations
A dynamic dictionary is constructed that supports operations in $O(\log\varepsilon^{-1}/\log\log\varepsilon^{-1})$ expected amortized time and uses bits of space, and proves a matching lower bound, showing that the time-space tradeoff is optimal even in the \emph{static} case.
G. Blelloch, Yang Hu, William Kuszmaul et al.· 1 citation
First proposed in 1968, quadratic probing has stood for more than half a century as one of the simplest and most widely used hash-table designs in computer science. It is conjectured that, at load factor $1 - \epsilon$, the hash table achieves $O(\epsilon^{-1})$ expected insertion time. But even proving a bound of the...
Yang Hu, William Kuszmaul, Jingxun Liang et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
