<p>Denote $[n] \triangleq \{1,2,\ldots,n\}$.</p>

<p>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).</p>

<p>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..</p>

<p>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&lt;&lt;k$.</p>

<p>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]$.</p>

<p>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).</p>

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

CC BY-SA 3.0
2014-11-27T08:04:14.523Z
Looks like standard open chaining hash table to me with hash table size cm and h being the hash function.
antti.huima
CC BY-SA 3.0
2014-11-29T00:55:29.117Z
What exactly is your question, RB?
jbapple
CC BY-SA 3.0
2014-12-16T20:44:25.107Z
This seems related to https://cs.stackexchange.com/questions/24118/is-there-an-anti-bloom-filter and the various questions it links to.
András Salamon
<reference-request><ds.data-structures><succinct>
What is the name of this data structure? (hash table with a limit on the number of entries)
R B
# What is the name of this data structure? (hash table with a limit on the number of entries)

(Asked by: username_0 on 2014-11-26)

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<

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.

**Tags:** reference-request, ds.data-structures, succinct
> **Comments:**
> **username_1**: Looks like standard open chaining hash table to me with hash table size cm and h being the hash function.  
> **username_2**: What exactly is your question, RB?  
> **username_3**: This seems related to https://cs.stackexchange.com/questions/24118/is-there-an-anti-bloom-filter and the various questions it links to.  

---

## 0 answers

