# A Write-friendly Store for SILT: Part II

Learn how to design a key-value store for fast writing.

## Indexing for reduced per-key memory consumption

Since this store contains the least amount of keys, the overall impact of using the hash table on per-key memory consumption will be low. However, since reduced per-key memory consumption is our goal, we should find ways to reduce the impact of the above hash table. We can reduce per-key memory used by the write-friendly store by:

Ensuring high occupancy of the hash table

Using a partial key instead of the full key

### Partial-key cuckoo hashing for higher occupancy

The technique we will use for hashing is **partial-key cuckoo hashing**. The **partial-key** means we will use a part of the key.

#### Hash functions

Cuckoo hashing requires two hash functions, `h1`

, and `h2`

. Both map a key `K`

to two candidate buckets, `h1(K)`

and `h2(K)`

, on the same table.

#### Insertion algorithm

To insert a new key, `K1`

, we will compute its candidate buckets `h1(K1)`

and `h2(K1)`

and check if one, both, or none of the two buckets are empty.

If both buckets are empty, store

`K1`

in one of the buckets.If one bucket is empty, check if

`K1`

is stored in the occupied bucket.If

`K1`

is already stored, update the offset.Otherwise, store

`K1`

in the empty bucket.

If neither bucket is empty, check if

`K1`

is stored in one of the occupied buckets.If

`K1`

is already stored, update the offset.Otherwise,

`K1`

displaces`K2`

in one of the`K1`

candidate buckets. We will insert`K2`

into its other candidate bucket.If the other candidate bucket for

`K2`

is empty, it is stored there.If the other candidate bucket is not empty,

`K2`

displaces`K3`

, which resides in its other candidate bucket.We will repeat the process in

*3(II)*for`K3`

until we find an empty bucket for a limited number of displacements. If we reach our allowed number of displacements and cannot find an empty bucket, we will initialize a new write-friendly store and store the displaced key in one of its candidate buckets in the new store.

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.