Crate odht[−][src]
Expand description
This crate implements a hash table that can be used as is in its binary, on-disk format. The goal is to provide a high performance data structure that can be used without any significant up-front decoding. The implementation makes no assumptions about alignment or endianess of the underlying data, so a table encoded on one platform can be used on any other platform and the binary data can be mapped into memory at arbitrary addresses.
Usage
In order to use the hash table one needs to implement the Config
trait.
This trait defines how the table is encoded and what hash function is used.
With a Config
in place the HashTableOwned
type can be used to build and serialize a hash table.
The HashTable
type can then be used to create an almost zero-cost view of the serialized hash table.
use odht::{HashTable, HashTableOwned, Config, FxHashFn};
struct MyConfig;
impl Config for MyConfig {
type Key = u64;
type Value = u32;
type EncodedKey = [u8; 8];
type EncodedValue = [u8; 4];
type H = FxHashFn;
#[inline] fn encode_key(k: &Self::Key) -> Self::EncodedKey { k.to_le_bytes() }
#[inline] fn encode_value(v: &Self::Value) -> Self::EncodedValue { v.to_le_bytes() }
#[inline] fn decode_key(k: &Self::EncodedKey) -> Self::Key { u64::from_le_bytes(*k) }
#[inline] fn decode_value(v: &Self::EncodedValue) -> Self::Value { u32::from_le_bytes(*v)}
}
fn main() {
let mut builder = HashTableOwned::<MyConfig>::with_capacity(3, 95);
builder.insert(&1, &2);
builder.insert(&3, &4);
builder.insert(&5, &6);
let serialized = builder.raw_bytes().to_owned();
let table = HashTable::<MyConfig, &[u8]>::from_raw_bytes(
&serialized[..]
).unwrap();
assert_eq!(table.get(&1), Some(2));
assert_eq!(table.get(&3), Some(4));
assert_eq!(table.get(&5), Some(6));
}
Structs
Implements the hash function from the rustc-hash crate.
The HashTable type provides a cheap way to construct a non-resizable view
of a persisted hash table. If the underlying data storage D
implements
BorrowMut<[u8]>
then the table can be modified in place.
A HashTableOwned keeps the underlying data on the heap and can resize itself on demand.
A hash function that simply takes the last 4 bytes of a given key as the hash value.
Traits
This trait provides a complete “configuration” for a hash table, i.e. it defines the key and value types, how these are encoded and what hash function is being used.
This trait represents hash functions as used by HashTable and HashTableOwned.
Functions
Computes the exact number of bytes needed for storing a HashTable with the given max item count and load factor. The result can be used for allocating storage to be passed into HashTable::init_in_place.