## 3 Hash-Based Key-Value Data Structures
### Functional Bloom Filter  
A functional Bloom filter (FBF) [20; 21; 22] is a variant of a standard Bloom filter that returns a value corresponding to a key as well as its membership. Figure 1d shows a functional Bloom filter with \(m\) cells and \(k\) hash indexes. As each cell is composed of \(L\) bits, each cell can have a value with range \(\{0,1,\ldots,2^{L}-1\}\). In a functional Bloom filter, the signature of each key is not stored and only a value corresponding to each key is stored in each cell, as various combinations of \(k\) hash indexes can serve as the signatures.  
Every cell in an FBF is initialized to 0. To program set \(S=\{(x_{1},v_{1}),(x_{2},v_{2}),\)\(\ldots,(x_{n},v_{n})\}\) to an FBF, in inserting element \(x_{p}\in S\), \(k\) independent hash functions \(\{h_{1},h_{2},\ldots,h_{k}\}\) are used. The FBF is programmed by setting return value \(v_{p}\) of \(x_{p}\) in all cells pointed by \(h_{i}(x_{p})\)s for \(1\leq i\leq k\). Key \(x_{p}\) is used to obtain hash indexes to access \(k\) cells but not stored, and the return value \(v_{p}\) is only stored.  
An important issue when dealing with a functional Bloom filter is how to resolve collision because a cell cannot store two or more different return values. Collided cells are not used in returning a value in a functional Bloom filter. In other words, in storing an element, if a value different from the return value of the element is already stored in an accessed cell, the cell is set to the maximum value \(2^{L}-1\) to represent the collision. Cells with the maximum value are named _conflict_ cells, denoted with **X** in Figure 1d. Thus, each cell can represent \(2^{L}-2\) return values in a functional Bloom filter, and values in conflict cells are not used in querying.  
In querying, a functional Bloom filter returns three types of results: _negative, positive,_ and _indeterminable_. For input \(y\), if there exists at least one cell with \(c[h_{i}(y)]=0\) for \(1\leq i\leq k\), it obviously means \(y\
otin S\), which is termed _negative_. Additionally, for cells with values other than _conflict_, if there are any cells with \(c[h_{i}(y)]\
eq c[h_{j}(y)]\) for \(1\leq i,j\leq k\), it is also \(y\
otin S\), as these cells are programmed by different keys other than \(y\). For cells with values other than _conflict_, if all \(c[h_{i}(y)]\)s are the same, it would be \(y\in S\) and the FBF returns \(c[h_{i}(y)]\), which is termed _positive_. It should be noted that, as in a standard BF, an FBF can return a _false positive_. For \(1\leq i\leq k\), if all \(c[h_{i}(y)]=2^{L}-1\), which means that _conflicts_ occur in every cell, the FBF fails to return a value, and it is termed _indeterminable_. Search failure of a functional Bloom filter is defined by _false positive_ and _indeterminable_ results.  
If the same amount of memory is used as a multi-hash table, the number of cells (\(m\)) in a functional Bloom filter is calculated by \(\frac{M_{b}}{L}\), as each cell only stores a return value without the signature of a key. As described in the querying procedure, by comparing the values of multiple cells pointed by an input, a functional Bloom filter can determine the return value without storing key \(x_{p}\) (or the signature of \(x_{p}\)).