4 stable releases
2.3.0 | Mar 25, 2023 |
---|---|
2.2.0 | Mar 12, 2022 |
2.0.0 | Apr 17, 2021 |
1.0.0 | Mar 9, 2021 |
#1211 in Data structures
251 downloads per month
155KB
2.5K
SLoC
mc-oblivious-map
This crate provides an implementation of an oblivious hashmap on top of oblivious RAM,
meeting the requirements in the trait described in mc-oblivious-traits
.
In crate right now:
- An implementation of Cuckoo hashing with buckets, using Oblivious RAM as the
cuckoo hashing arena.
See wikipedia for background.
This is close to or the same as CUCKOO-DISJOINT algorithm described by
this paper, except for the use of Oblivious RAM.
The
access-or-insert
method is novel in this work, see code comments for discussion.
For more background, see also "power of two choices" hashing (ABKU99, Mitzenmacher). And wikipedia for additional background. This is conceptually an ancestor of cuckoo hashing. The main reason to use this, or cuckoo hashing, in our context, is that it guarantees that reads make exactly two accesses to the table, which makes the constant-time property easy to verify. Cuckoo hashing achieves good memory utilization, better than "power of two choices", which is what we tried first.
Dependencies
~435KB