Denote $[n] \triangleq \{1,2,\ldots,n\}$.

Assume we would like to have a data structure $S$ which kinda works as a dictionary from $[k]$ to $[v]$, and supports add/remove/update/query functionality, without any dynamic memory allocation (everything has to be pre-allocated).

In general, one cannot do better than using $\Omega(k\log\frac{v}{k})$ bits in a succinct implementation or $k\log v$ bits in a simple array/hash table..

But if we assume that no more than $m$ items may be added to $S$ (assume you may ignore any additional add operation until some item is removed), we can improve the memory requirements, especially if $m<<k$.

Without getting into succinct implementation (is such known (which takes $m$ into consideration)?), one may simply allocate an array of $c\cdot m$ (where $c$ is a space/time performance parameter) linked lists, and whenever key $x$ is added to the structure, place it in list $h(x)$ for some function $h:[k]\to [cm]$.

If $h$ spread the actual keys (about) evenly, then the structure may still perform operations in $O(1)$ time for constant $c$ (as $\frac{1}{c}$ is the expected list length), while reducing the space requirement to $O(m(c+\log (vk)))$ (this can be done without any need for dynamic allocation).

I'm currently working on a succinct implementation of such structure for some application, and was wondering if there is a name for it.

  • $\begingroup$ Looks like standard open chaining hash table to me with hash table size cm and h being the hash function. $\endgroup$ – antti.huima Nov 27 '14 at 8:04
  • 1
    $\begingroup$ What exactly is your question, RB? $\endgroup$ – jbapple Nov 29 '14 at 0:55
  • $\begingroup$ This seems related to cs.stackexchange.com/questions/24118/… and the various questions it links to. $\endgroup$ – András Salamon Dec 16 '14 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.