Crate odht

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

FxHashFn

Implements the hash function from the rustc-hash crate.

HashTable

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.

HashTableOwned

A HashTableOwned keeps the underlying data on the heap and can resize itself on demand.

Iter

UnHashFn

A hash function that simply takes the last 4 bytes of a given key as the hash value.

Traits

Config

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.

HashFn

This trait represents hash functions as used by HashTable and HashTableOwned.

Functions

bytes_needed

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.