Struct ShardedMap 

pub struct ShardedMap<K, V>
where
    K: OHash + Pod + Default + Debug + Send + Ord,
    V: Cmov + Pod + Default + Debug + Send + Eq,
    BatchBlock<K, V>: Ord + Send,
{ /* private fields */ }

A sharded hashmap implementation. The map is split across multiple partitions and each partition is a separate hashmap. Queries are resolved in batches, to not leak the number of queries that go to each partition.

Parameters

• K: The type of the keys in the map.
• V: The type of the values in the map.
• P: The number of partitions in the map.
• B: The maximum number of non-distinct keys in any partition in a batch.

Implementations

impl<K, V> ShardedMap<K, V>

where K: OHash + Default + Debug + Send + Ord + Pod + Sized, V: Cmov + Pod + Default + Debug + Send + Eq, BatchBlock<K, V>: Ord + Send,

pub fn new(capacity: usize) -> Self

Creates a new ShardedMap with the given number of partitions.

pub const fn compute_safe_batch_size(&self, n: usize) -> usize

Computes a safe batch size B for a given number of distinct queries N.

Preconditions

• N >= P log P

pub fn get_batch_distinct(&mut self, keys: &[K], b: usize) -> Vec<OOption<V>>

Reads N values from the map, leaking only N and B, but not any information about the keys (doesn’t leak the number of keys to each partition).

Preconditions

• No repeated keys in the input array.
• There are at most b queries to each partition.

pub fn get_batch(&mut self, keys: &[K], b: usize) -> Vec<OOption<V>>

Reads N values from the map, leaking only N and B, but not any information about the keys (doesn’t leak the number of keys to each partition).

Preconditions

• There are at most b queries to each partition (statistically likely).

pub unsafe fn get_batch_leaky(&mut self, keys: &[K]) -> Vec<OOption<V>>

👎Deprecated: This function is unsafe because it can potentially leak information about keys to partition mapping. Use get_batch_distinct instead.

Leaky version of get_batch_distinct, which will return values for repeated keys and leak the size of the largest partition.

Safety

• This function will leak the size of the largest partition, which with repeated queries can be used to infer the mapping of keys to partitions.

pub fn insert_batch_distinct(&mut self, keys: &[K], values: &[V], b: usize)

Inserts a batch of N distinct key-value pairs into the map, distributing them across partitions.

Preconditions

• No repeated keys in the input array.
• All of the inserted keys are not already present in the map.
• There is enough space in the map to insert all N keys.
• There are at most b queries to each partition.

pub fn insert_batch(&mut self, keys: &[K], values: &[V], b: usize)

Reads N values from the map, leaking only N and B, but not any information about the keys (doesn’t leak the number of keys to each partition).

Preconditions

• There are at most b queries to each partition (statistically likely).

Behavior

• If a key appears multiple times in the input array, only the value corresponding to its first occurrence is used.

Trait Implementations

impl<K, V> Debug for ShardedMap<K, V>

where K: OHash + Pod + Default + Debug + Send + Ord + Debug, V: Cmov + Pod + Default + Debug + Send + Eq + Debug, BatchBlock<K, V>: Ord + Send,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.