PtrHash

https://docs.rs/ptr_hash/1.1.0/
Admin
PtrHash is a Rust library that builds minimal perfect hash functions, mapping fixed sets of keys to...
Tokens:309,572
Snippets:2,062
Trust Score:9.1
Update:3 months ago
Show doc for...
Tokens:
Raw
### Example Searches for KeyT

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/trait.KeyT.html?search=

Illustrative examples of how types satisfying the KeyT trait might be searched or used.

```rust
  * std::vec
```

```rust
  * u32 -> bool
```

```rust
  * Option<T>, (T -> U) -> Option<U>
```

--------------------------------

### PtrHash Usage Example

Source: https://docs.rs/ptr_hash/1.1.0/src/ptr_hash/lib.rs.html?search=u32+-%3E+bool

Demonstrates how to generate keys, build a PtrHash datastructure, and query for key indices. It also shows how to use index_no_remap, index_stream, and index_batch for different query scenarios. Note the recommendation to use PtrHashParams::default_fast() for smaller key sets.

```rust
#![cfg_attr(feature = "unstable", feature(iter_array_chunks))]
//! # PtrHash: Minimal Perfect Hashing at RAM Throughput
//!
//! PtrHash builds a _minimal perfect hash function_, that is,
//! a hash function that maps a fixed set of keys to `{0, ..., n-1}`.
//!
//! PtrHash was developed for large key sets of at least 1 million keys, and has been tested up to 10^11 keys.
//! It only uses 2.4 bits per key.
//!
//! It can also be used for arbitrary small sets.
//! In this case, the space efficiency will be less due to a relatively large constant overhead.
//!
//! See the GitHub [readme](https://github.com/ragnargrootkoerkamp/ptrhash)
//! or paper ([arXiv](https://arxiv.org/abs/2502.15539), [blog version](https://curiouscoding.nl/posts/ptrhash/))
//! for details on the algorithm and performance.
//!
//! Usage example:
//! ```rust
//! use ptr_hash::{PtrHash, PtrHashParams};
//!
//! // Generate some random keys.
//! let n = 1_000_000;
//! let keys = ptr_hash::util::generate_keys(n);
//!
//! // Build the datastructure.
//! // NOTE: For small sets, say <1M keys, use `PtrHashParams::default_fast()` instead.
//! // The default parameters are optimized for large sets, and need large (>100k or so) inputs
//! // to ensure internal bucket sizes don't deviate too much from their expectation.
//! let mphf = <PtrHash>::new(&keys, PtrHashParams::default());
//!
//! // Get the index of a key.
//! let key = 0;
//! let idx = mphf.index(&key);
//! assert!(idx < n);
//!
//! // Get the non-minimal index of a key.
//! // Can be slightly faster returns keys up to `n/alpha ~ 1.01*n`.
//! let _idx = mphf.index_no_remap(&key);
//!
//! // An iterator over the indices of the keys.
//! // 32: number of iterations ahead to prefetch.
//! // true: remap to a minimal key in [0, n).
//! // _: placeholder to infer the type of keys being iterated.
//! let indices = mphf.index_stream::<32, true, _>(&keys);
//! assert_eq!(indices.sum::<usize>(), (n * (n - 1)) / 2);
//!
//! // Query a batch of keys.
//! let keys = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];
//! let mut indices = mphf.index_batch::<16, true, _>(keys);
//! indices.sort();
//! for i in 0..indices.len()-1 {
//!     assert!(indices[i] != indices[i+1]);
//! }
//!
//! // Test that all items map to different indices
//! let mut taken = vec![false; n];
//! for key in keys {
//!     let idx = mphf.index(&key);
//!     assert!(!taken[idx]);
//!     taken[idx] = true;
//! }
//! ```
//!
//! ## Partitioning
//!
//! By default, PtrHash partitions the keys into multiple parts.
//! This speeds up construction in two ways:
//! - smaller parts have better cache locality, and
//! - parts can be constructed in parallel.
//!
//! However, at query time there is a small overhead to compute the part of each key.
//! To achieve slightly faster queries, set [`PtrHashParams::single_part`] to `true`,
//! and then use [`PtrHash::index_single_part()`] instead of [`PtrHash::index()`].

```

--------------------------------

### Example Search: Option<T>, (T -> U) -> Option<U>

Source: https://docs.rs/ptr_hash/1.1.0/src/ptr_hash/stats.rs.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Illustrates a common type transformation pattern in Rust, often used with Option types and closures for mapping values.

```rust
Option<T>, (T -> U) -> Option<U>
```

--------------------------------

### Skewed Bucket Function Test

Source: https://docs.rs/ptr_hash/1.1.0/src/ptr_hash/bucket_fn.rs.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Tests the Skewed bucket function implementation. This example demonstrates how to initialize and use the Skewed bucket function with custom parameters and print the results.

```rust
#[test]
    fn test_skewed() {
        use super::Skewed;
        let mut skewed = Skewed::new(0.6, 0.3);
        skewed.set_buckets_per_part(1000000000);

        let n = 100;
        for i in 0..100 {
            let x = u64::MAX / n * i;
            let y = skewed.call(x);
            println!({"x:>20} => {y:>20}");
        }
    }
```

--------------------------------

### index_no_remap

Source: https://docs.rs/ptr_hash/1.1.0/src/ptr_hash/lib.rs.html

Gets a non-minimal index for the given key, within the range `[0, n/alpha)`. Use `index` to get a key in `[0, n)`.

```APIDOC
## index_no_remap

### Description
Get a non-minimal index of the given key, in `[0, n/alpha)`. Use `index` to get a key in `[0, n)`.

### Method
`PtrHash::index_no_remap`

### Parameters
#### Path Parameters
- **key** (`&Key`): The key to find the index for.

### Return Value
- `usize`: A non-minimal index for the key.
```

--------------------------------

### PtrHash::index_no_remap

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/struct.PtrHash.html?search=u32+-%3E+bool

Gets a non-minimal index for the given key, within the range `[0, n/alpha)`. Use `index()` to get an index within `[0, n)`.

```APIDOC
## PtrHash::index_no_remap

### Description
Get a non-minimal index of the given key, in `[0, n/alpha)`. Use `index` to get a key in `[0, n)`.

### Signature
`pub fn index_no_remap<Key: KeyT, BF: BucketFn, F: Packed, Hx: Hasher<Key>, V: AsRef<[u8]>>(&self, key: &Key) -> usize`
```

--------------------------------

### Pointable::init

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/pack/struct.EliasFano.html?search=

Initializes a with the given initializer.

```APIDOC
## unsafe fn init(init: <T as Pointable>::Init) -> usize

### Description
Initializes a with the given initializer.

### Signature
`unsafe fn init(init: <T as Pointable>::Init) -> usize`
```

--------------------------------

### Build and Query PtrHash

Source: https://docs.rs/ptr_hash/1.1.0/index.html

Demonstrates generating keys, building a PtrHash datastructure with default parameters optimized for large sets, and querying key indices.

```rust
use ptr_hash::{PtrHash, PtrHashParams};

// Generate some random keys.
let n = 1_000_000;
let keys = ptr_hash::util::generate_keys(n);

// Build the datastructure.
// NOTE: For small sets, say <1M keys, use `PtrHashParams::default_fast()` instead.
// The default parameters are optimized for large sets, and need large (>100k or so) inputs
// to ensure internal bucket sizes don't deviate too much from their expectation.
let mphf = <PtrHash>::new(&keys, PtrHashParams::default());

// Get the index of a key.
let key = 0;
let idx = mphf.index(&key);
assert!(idx < n);

// Get the non-minimal index of a key.
// Can be slightly faster returns keys up to `n/alpha ~ 1.01*n`.
let _idx = mphf.index_no_remap(&key);

// An iterator over the indices of the keys.
// 32: number of iterations ahead to prefetch.
// true: remap to a minimal key in [0, n).
// _: placeholder to infer the type of keys being iterated.
let indices = mphf.index_stream::<32, true, _>(&keys);
assert_eq!(indices.sum::<usize>(), (n * (n - 1)) / 2);

// Query a batch of keys.
let keys = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];
let mut indices = mphf.index_batch::<16, true, _>(keys);
indices.sort();
for i in 0..indices.len()-1 {
    assert!(indices[i] != indices[i+1]);
}

// Test that all items map to different indices
let mut taken = vec![false; n];
for key in keys {
    let idx = mphf.index(&key);
    assert!(!taken[idx]);
    taken[idx] = true;
}

```

--------------------------------

### impl<T> Any for T

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/bucket_fn/struct.Skewed.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Provides the `type_id` method to get the `TypeId` of a type.

```APIDOC
## fn type_id(&self) -> TypeId

### Description
Gets the `TypeId` of `self`.

### Method
`type_id`

### Parameters
None

### Returns
- `TypeId`: The unique identifier for the type of `self`.
```

--------------------------------

### PtrHash Initialization and Logging

Source: https://docs.rs/ptr_hash/1.1.0/src/ptr_hash/lib.rs.html

After determining the optimal parameters, this section logs the calculated values for debugging and performance analysis. It then initializes the PtrHash struct with these parameters.

```rust
trace!("        keys: {n:>10}");
        trace!("      shards: {shards:>10}");
        trace!("       parts: {parts:>10}");
        trace!("   slots/prt: {slots_per_part:>10}");
        trace!("   slots tot: {slots_total:>10}");
        trace!("  real alpha: {:>10.4}", n as f64 / slots_total as f64);
        trace!(" buckets/prt: {buckets_per_part:>10}");
        trace!(" buckets tot: {buckets_total:>10}");
        trace!("keys/ bucket: {:>13.2}", n as f64 / buckets_total as f64);

        params
            .bucket_fn
            .set_buckets_per_part(buckets_per_part as u64);

        Self {
            params,
            n,
            parts,
            shards,
            parts_per_shard,
            slots_total,
            slots: slots_per_part,
            buckets_total,
            buckets: buckets_per_part,
            rem_shards: Rp::new(shards),
            rem_parts: Rp::new(parts),
            rem_buckets: Rb::new(buckets_per_part),
            rem_buckets_total: Rb::new(buckets_total),
            rem_slots: Rp::new(slots_per_part),
            seed: 0,
            pilots: Default::default(),
            remap: F::default(),
            _key: PhantomData,
            _hx: PhantomData,
        }
```

--------------------------------

### Any Trait

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/bucket_fn/struct.Linear.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Provides the `type_id` method to get the `TypeId` of the instance.

```APIDOC
## fn type_id(&self) -> TypeId

Gets the `TypeId` of `self`.
```

--------------------------------

### impl<T> Any for T

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/bucket_fn/struct.CubicEps.html?search=u32+-%3E+bool

Provides the `type_id` method to get the `TypeId` of an object.

```APIDOC
## fn type_id(&self) -> TypeId

### Description
Gets the `TypeId` of `self`.

### Method
`type_id`

### Parameters
None

### Response
#### Success Response
- **TypeId**: The unique identifier for the type of `self`.
```

--------------------------------

### CloneToUninit

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/hash/struct.NoHash.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Experimental implementation for cloning to uninitialized memory.

```APIDOC
## impl<T> CloneToUninit for T

### Description
Experimental implementation for cloning to uninitialized memory. This is a nightly-only API.

### Method
`unsafe fn clone_to_uninit(&self, dest: *mut u8)`

### Endpoint
N/A (Trait Implementation)

### Parameters
- `dest` (*mut u8): A mutable pointer to the destination uninitialized memory.

### Request Example
N/A

### Response
None (operates via pointer manipulation).
```

--------------------------------

### Testing Skewed BucketFn

Source: https://docs.rs/ptr_hash/1.1.0/src/ptr_hash/bucket_fn.rs.html?search=u32+-%3E+bool

Demonstrates how to test the Skewed BucketFn implementation by creating an instance, setting parameters, and calling the call method with various inputs.

```rust
#[cfg(test)]
mod test {
    use crate::bucket_fn::BucketFn;

    #[test]
    fn test_skewed() {
        use super::Skewed;
        let mut skewed = Skewed::new(0.6, 0.3);
        skewed.set_buckets_per_part(1000000000);

        let n = 100;
        for i in 0..100 {
            let x = u64::MAX / n * i;
            let y = skewed.call(x);
            println!("{x:>20} => {y:>20}");
        }
    }
}
```

--------------------------------

### Any Trait Implementation

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/bucket_fn/struct.Optimal.html?search=u32+-%3E+bool

Provides the `type_id` method to get the `TypeId` of the type.

```APIDOC
## impl<T> Any for T

### fn type_id(&self) -> TypeId

Gets the `TypeId` of `self`.
```

--------------------------------

### Sort Hashes and Determine Part Starts

Source: https://docs.rs/ptr_hash/1.1.0/src/ptr_hash/sort_buckets.rs.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Sorts hash values using radix sort, checks for duplicates, and calculates the start indices for each part within a shard. Returns None if duplicate hashes are found. This function is crucial for distributing hashes across different parts efficiently.

```rust
use super::*;
use crate::bucket_idx::BucketIdx;
use rdst::RadixSort;
use std::time::Instant;

impl<Key: KeyT, BF: BucketFn, F: Packed, Hx: Hasher<Key>> PtrHash<Key, BF, F, Hx, Vec<u8>> {
    /// Returns:
    /// 1. Hashes
    /// 2. Start indices of each bucket.
    /// 3. Order of the buckets within each part.
    ///
    /// This returns None if duplicate hashes are found.
    #[must_use]
    pub(super) fn sort_parts(
        &self,
        shard: usize,
        mut hashes: Vec<Hx::H>,
    ) -> Option<(Vec<Hx::H>, Vec<u32>)> {
        // For FastReduce methods, we can just sort by hash directly
        // instead of sorting by bucket id: For FR32L, first partition by those
        // <self.p1 and those >=self.p1, and then sort each group using the low
        // 32 bits.
        // NOTE: This does not work for other reduction methods.

        let start = Instant::now();
        // 2. Radix sort hashes.
        // HOT: This takes half the time for 128bit hashes.
        // TODO: Just append each hash to its part directly, where each part has
        //       space for exactly its number of slots.
        //
        // TODO: Write robinhood sort that inserts in the right place directly.
        // A) Sort L1 sized ranges.
        // B) Splat the front of each range to the next part of the target interval.
        hashes.radix_sort_unstable();
        let start = log_duration("┌ radix sort", start);

        // 3. Check duplicates.
        let distinct = hashes.par_windows(2).all(|w| w[0] != w[1]);
        let start = log_duration("├ check dups", start);
        if !distinct {
            eprintln!("Hashes are not distinct!");
            return None;
        }

        // 4. Find the start of each part using binary search.
        if !hashes.is_empty() {
            assert!(shard * self.parts_per_shard <= self.part(hashes[0]));
            assert!(self.part(*hashes.last().unwrap()) < (shard + 1) * self.parts_per_shard);
        }
        let mut part_starts = vec![0u32; self.parts_per_shard + 1];
        for part_in_shard in 1..=self.parts_per_shard {
            part_starts[part_in_shard] = hashes
                .binary_search_by(|h| {
                    if self.part(*h) < shard * self.parts_per_shard + part_in_shard {
                        std::cmp::Ordering::Less
                    } else {
                        std::cmp::Ordering::Greater
                    }
                })
                .unwrap_err() as u32;
        }

        // Check max part len.
        let mut max_part_len = 0;
        for (start, end) in part_starts.iter().tuple_windows() {
            let len = (end - start) as usize;
            max_part_len = max_part_len.max(len);
        }
        let exp = self.n / self.parts;
        let stddev = exp.isqrt();

        // https://math.stackexchange.com/a/89147/91741:
        // expected max of N (here #parts) samples of a random variable is
        // exp + sigma * sqrt(2 * ln N).
        let exp_max = exp + stddev * ((self.parts as f32).ln() * 2.).sqrt() as usize;
        trace!("exp key/part: {exp:>10} stddev {stddev:>10}");
        trace!(
            "exp max k/pt: {exp_max:>10}        {:>10} {:>8.2}",
            exp_max - exp,
            (exp_max - exp) as f32 / stddev as f32
        );
        trace!(
            "    max k/pt: {max_part_len:>10}        {:>10} {:>8.2}",
            max_part_len - exp,
            (max_part_len - exp) as f32 / stddev as f32
        );
        trace!(
            "    slots/pt: {:>10}        {:>10} {:>8.2}",
            self.slots,
            self.slots - exp,
            (self.slots - exp) as f32 / stddev as f32
        );
        trace!("exp    alpha: {:>13.2}%", 100. * self.params.alpha);
        trace!(
            "max    alpha: {:>13.2}%",
            100. * max_part_len as f32 / self.slots as f32
        );

        if max_part_len as usize > self.slots {
            trace!(
                    "Shard {shard}: Part has more elements than slots! elements {max_part_len} > {} slots",
                    self.slots
                );
            return None;
        }

        log_duration("├part starts", start);

        Some((hashes, part_starts))
    }

    // Sort the buckets in the given part and corresponding range of hashes.
    pub(super) fn sort_buckets(&self, part: usize, hashes: &[Hx::H]) -> (Vec<u32>, Vec<BucketIdx>) {
        // Where each bucket starts in hashes.
        let mut bucket_starts = Vec::with_capacity(self.buckets + 1);

        // The order of buckets, from large to small.

```

--------------------------------

### Provided Methods

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/bucket_fn/trait.BucketFn.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

The `set_buckets_per_part` method is provided with a default implementation, allowing customization of bucket configurations.

```APIDOC
## Provided Methods

Source
#### fn set_buckets_per_part(&mut self, _b: u64)
```

--------------------------------

### index

Source: https://docs.rs/ptr_hash/1.1.0/src/ptr_hash/lib.rs.html?search=std%3A%3Avec

Gets the minimal index for the key, within the range `[0, n)`.

```APIDOC
## index

### Description
Calculates and returns the minimal index for the given key, ensuring the index falls within the range `[0, n)`. This method accounts for remapping if necessary.

### Method
`pub fn index(&self, key: &Key) -> usize`

### Parameters
*   `key` (*Key*) - The key for which to compute the index.

### Returns
The minimal index for the key in the range `[0, n)`.
```

--------------------------------

### Pointable

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/bucket_fn/struct.Square.html?search=std%3A%3Avec

Provides methods for managing memory pointers and initialization.

```APIDOC
## const ALIGN: usize

### Description
The alignment requirement for pointers managed by this type.

### Returns
- usize - The alignment value.
```

```APIDOC
## type Init = T

### Description
Defines the type used for initializers when creating new instances.

### Returns
- T - The type of the initializer.
```

```APIDOC
## unsafe fn init(init: <T as Pointable>::Init) -> usize

### Description
Initializes a new instance of the type using the provided initializer and returns a pointer to the allocated memory.

### Parameters
- **init** (<T as Pointable>::Init) - The initializer value for the new instance.

### Returns
- usize - A pointer to the newly initialized instance.
```

```APIDOC
## unsafe fn deref<'a>(ptr: usize) -> &'a T

### Description
Dereferences a raw pointer to obtain an immutable reference to the object.

### Parameters
- **ptr** (usize) - The raw pointer to dereference.

### Returns
- &'a T - An immutable reference to the object.
```

```APIDOC
## unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T

### Description
Dereferences a raw pointer to obtain a mutable reference to the object.

### Parameters
- **ptr** (usize) - The raw pointer to dereference.

### Returns
- &'a mut T - A mutable reference to the object.
```

```APIDOC
## unsafe fn drop(ptr: usize)

### Description
Drops the object pointed to by the given raw pointer, deallocating its memory.

### Parameters
- **ptr** (usize) - The raw pointer to the object to drop.
```

--------------------------------

### Pointable Methods

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/bucket_fn/struct.CubicEps.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Methods for pointer manipulation and initialization.

```APIDOC
## const ALIGN: usize

### Description
The alignment of pointer.

## type Init = T

### Description
The type for initializers.

## unsafe fn init(init: <T as Pointable>::Init) -> usize

### Description
Initializes a with the given initializer.

## unsafe fn deref<'a>(ptr: usize) -> &'a T

### Description
Dereferences the given pointer.

## unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T

### Description
Mutably dereferences the given pointer.

## unsafe fn drop(ptr: usize)

### Description
Drops the object pointed to by the given pointer.

```

--------------------------------

### Get Number of Elements

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/struct.PtrHash.html

Returns the number of elements (`n`) stored in the PtrHash.

```rust
pub fn n(&self) -> usize
```

--------------------------------

### EliasFano type_id Method

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/pack/struct.EliasFano.html

Gets the `TypeId` of `self`. This is part of the `Any` trait implementation.

```rust
fn type_id(&self) -> TypeId
```

--------------------------------

### BucketFn Implementations

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/bucket_fn/trait.BucketFn.html?search=

Demonstrates various implementations of the BucketFn trait, showcasing different hashing strategies.

```APIDOC
## Implementors of BucketFn

The `BucketFn` trait is implemented by several types, each offering a distinct hashing approach:

* `Cubic`
* `CubicEps`
* `Linear`
  * `const LINEAR: bool = true`
* `Optimal`
* `Skewed`
  * `const B_OUTPUT: bool = true`
* `Square`
* `SquareEps`
```

--------------------------------

### fn load_mem<'a>(path: impl AsRef<Path>) -> Result<MemCase<Self::DeserType<'a>>, Error>

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/hash/struct.Xx64.html

Loads a file into heap-allocated memory and ε-deserializes a data structure from it.

```APIDOC
## fn load_mem<'a>(path: impl AsRef<Path>) -> Result<MemCase<Self::DeserType<'a>>, Error>

### Description
Load a file into heap-allocated memory and ε-deserialize a data structure from it, returning a `MemCase` containing the data structure and the memory. Excess bytes are zeroed out.

### Method
`load_mem`

### Parameters
- **path** (impl AsRef<Path>): The path to the file.

### Response
#### Success Response
- **MemCase<Self::DeserType<'a>>**: A `MemCase` containing the deserialized data structure and its memory.
#### Error Response
- **Error**: An error occurred during deserialization.
```

--------------------------------

### Cubic Default Implementation

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/bucket_fn/struct.Cubic.html?search=

Shows how to get the default value for the Cubic struct.

```rust
impl Default for Cubic {
    fn default() -> Cubic {
        // Implementation details omitted for brevity
        unimplemented!()
    }
}
```

--------------------------------

### Pointable Implementations

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/bucket_fn/struct.Optimal.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Provides methods for low-level pointer manipulation and initialization.

```APIDOC
## const ALIGN: usize

### Description
Represents the required alignment for pointers of this type.
```

```APIDOC
## type Init = T

### Description
Defines the type used for initializing objects of this type.
```

```APIDOC
## unsafe fn init(init: <T as Pointable>::Init) -> usize

### Description
Initializes an object of type `T` using the provided initializer and returns a pointer (as `usize`) to the newly created object.

### Parameters
- **init** (<T as Pointable>::Init) - The initializer value for the object.
```

```APIDOC
## unsafe fn deref<'a>(ptr: usize) -> &'a T

### Description
Dereferences a raw pointer (represented as `usize`) to obtain an immutable reference to an object of type `T`.

### Parameters
- **ptr** (usize) - The raw pointer to dereference.
```

```APIDOC
## unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T

### Description
Dereferences a raw pointer (represented as `usize`) to obtain a mutable reference to an object of type `T`.

### Parameters
- **ptr** (usize) - The raw pointer to dereference.
```

```APIDOC
## unsafe fn drop(ptr: usize)

### Description
Drops the object pointed to by the given raw pointer (represented as `usize`).

### Parameters
- **ptr** (usize) - The raw pointer to the object to be dropped.
```

--------------------------------

### index_no_remap

Source: https://docs.rs/ptr_hash/1.1.0/src/ptr_hash/lib.rs.html?search=std%3A%3Avec

Gets a non-minimal index for the given key, within the range `[0, n/alpha)`.

```APIDOC
## index_no_remap

### Description
Calculates and returns a non-minimal index for the given key. The index will be within the range `[0, n/alpha)`. For an index within `[0, n)`, use the `index` method.

### Method
`pub fn index_no_remap(&self, key: &Key) -> usize`

### Parameters
*   `key` (*Key*) - The key for which to compute the index.

### Returns
A non-minimal index for the key.
```

--------------------------------

### Get Number of Elements (n)

Source: https://docs.rs/ptr_hash/1.1.0/src/ptr_hash/lib.rs.html?search=u32+-%3E+bool

Returns the total number of elements stored in the PtrHash structure.

```rust
pub fn n(&self) -> usize {
        self.n
    }
```

--------------------------------

### PtrHash::index

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/struct.PtrHash.html?search=u32+-%3E+bool

Gets the minimal index for the given key, within the range `[0, n)`.

```APIDOC
## PtrHash::index

### Description
Get the index for `key` in `[0, n)`.

### Signature
`pub fn index<Key: KeyT, BF: BucketFn, F: Packed, Hx: Hasher<Key>, V: AsRef<[u8]>>(&self, key: &Key) -> usize`
```

--------------------------------

### fn load_full(path: impl AsRef<Path>) -> Result<Self, Error>

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/hash/struct.Xx64.html

Convenience method to fully deserialize from a file.

```APIDOC
## fn load_full(path: impl AsRef<Path>) -> Result<Self, Error>

### Description
Convenience method to fully deserialize from a file.

### Method
`load_full`

### Parameters
- **path** (impl AsRef<Path>): The path to the file.

### Response
#### Success Response
- **Self**: The deserialized structure.
#### Error Response
- **Error**: An error occurred during deserialization.
```

--------------------------------

### Get Slots Per Part

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/struct.PtrHash.html

Returns the number of slots per part in the PtrHash structure.

```rust
pub fn slots_per_part(&self) -> usize
```

--------------------------------

### CloneToUninit Trait Implementation

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/bucket_fn/struct.Linear.html?search=

Documentation for the experimental 'CloneToUninit' trait, enabling cloning to uninitialized memory.

```APIDOC
## impl<T> CloneToUninit for T

### Description
This is a nightly-only experimental API that allows cloning a value into uninitialized memory.

### Method
#### unsafe fn clone_to_uninit(&self, dest: *mut u8)
Performs copy-assignment from `self` to `dest`.
```

--------------------------------

### From Trait

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/bucket_fn/struct.Linear.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Provides a method to create an instance from itself.

```APIDOC
## fn from(t: T) -> T

Returns the argument unchanged.
```

--------------------------------

### index

Source: https://docs.rs/ptr_hash/1.1.0/src/ptr_hash/lib.rs.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Gets the index for the given key, within the range `[0, n)`. This method handles remapping.

```APIDOC
## index

### Description
Get the index for `key` in `[0, n)`. This method accounts for remapping.

### Method
`pub fn index(&self, key: &Key) -> usize`

### Parameters
#### Path Parameters
- **key** (*Key*) - The key to find the index for.

### Returns
The index (`usize`) for the key in the range `[0, n)`.
```

--------------------------------

### Get Minimal Index

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/struct.PtrHash.html

Calculates the minimal index for the given key, within the range `[0, n)`.

```rust
pub fn index(&self, key: &Key) -> usize
```

--------------------------------

### Handle Bucket Evictions and Resize

Source: https://docs.rs/ptr_hash/1.1.0/src/ptr_hash/build.rs.html?search=

Manages bucket evictions during the build process. If evictions exceed a threshold, it logs detailed statistics and potentially aborts if the situation is unrecoverable, suggesting parameter adjustments.

```rust
            if evictions > self.slots && evictions.is_power_of_two() {
                // log = true;
                let num_taken_slots = taken.count_ones();
                // if self.params.print_stats {
                //     eprintln!(
                //         "part {part:>6} alpha {:>5.2}% bucket size {} ({}/{}, {:>5.2}%) slots filled {}/{} ({:>5.2}%) chain: {evictions:>9}",
                //         100. * hashes.len()  as f32 / slots.len() as f32,
                //         new_b_len,
                //         i, self.buckets,
                //         100. * i as f32 / self.buckets as f32,
                //         num_taken_slots,
                //         taken.len(),
                //         100. * num_taken_slots as f32 / taken.len() as f32,
                //     );
                // }
                if evictions >= 10 * self.slots {
                    trace!(
                        \
Too many evictions. Aborting!\n
When the current bucket has size >=2, try decreasing lambda to use fewer elements per buckets.\n
When the current bucket has size 1 (or maybe 2), try decreasing alpha to have more empty slots for the last few buckets.\n
\nCurrent part: {part:>6} with load factor alpha={:>5.2}%\n
Current bucket: size {} ({}/{}, {:>5.2}%)\n
Slots filled so far: {}/{} ({:>5.2}%)\n
Eviction chain length: {evictions:>9}\n
                            ",
                        100. * hashes.len()  as f32 / slots.len() as f32,
                        new_b_len,
                        i, self.buckets,
                        100. * i as f32 / self.buckets as f32,
                        num_taken_slots,
                        taken.len(),
                        100. * num_taken_slots as f32 / taken.len() as f32,
                    );
                    return None;
                }
            }
```

--------------------------------

### Get Non-Minimal Index

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/struct.PtrHash.html

Calculates a non-minimal index for the given key, within the range `[0, n/alpha)`.

```rust
pub fn index_no_remap(&self, key: &Key) -> usize
```

--------------------------------

### Sharding and Writing Hashes to Disk

Source: https://docs.rs/ptr_hash/1.1.0/src/ptr_hash/shard.rs.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

This snippet demonstrates the process of sharding keys, writing them to temporary files, and then reading them back. It handles both hybrid and on-disk sharding scenarios based on memory availability. Temporary files are automatically cleaned up.

```rust
        if mem < usize::MAX {
            info!("Hybrid sharding: writing hashes to disk for {shards_on_disk} shards at a time, for total {} shards each of ~{} keys.", self.shards, self.n / self.shards);
        } else {
            info!(
                "On-disk sharding: writing hashes to disk for all {} shards at a time, each of ~{} keys.",
                self.shards,
                self.n / self.shards
            );
        }

        let it = (0..self.shards)
            .step_by(shards_on_disk)
            .flat_map(move |first_shard| {
                let temp_dir = tempfile::TempDir::new().unwrap();
                info!("TMP PATH: {:?}", temp_dir.path());

                let shard_range = first_shard..(first_shard + shards_on_disk).min(self.shards);
                info!("Writing keys for shards {:?}/{}", shard_range, self.shards);

                let start = std::time::Instant::now();

                // Create a file writer and count for each shard.
                let writers = shard_range
                    .clone()
                    .map(|shard| {
                        Mutex::new((
                            BufWriter::new(
                                File::options()
                                    .read(true)
                                    .write(true)
                                    .create(true)
                                    .open(temp_dir.path().join(format!("{}.tmp", shard)))
                                    .unwrap(),
                            ),
                            0,
                        ))
                    })
                    .collect_vec();

                // Each thread has a local buffer per shard.
                let init = || writers.iter().map(ThreadLocalBuf::new).collect_vec();
                // Iterate over keys.
                keys.clone()
                    .map(|key| self.hash_key(key.borrow()))
                    .for_each_init(init, |bufs, h| {
                        let shard = self.shard(h);
                        if shard_range.contains(&shard) {
                            bufs[shard - shard_range.start].push(h);
                        }
                    });
                let start = log_duration("Writing files", start);

                // Flush writers and convert to files.
                let files = writers
                    .into_iter()
                    .map(|w| {
                        let (mut w, cnt) = w.into_inner().unwrap();
                        w.flush().unwrap();
                        let mut file = w.into_inner().unwrap();
                        file.seek(SeekFrom::Start(0)).unwrap();
                        (file, cnt)
                    })
                    .collect_vec();
                log_duration("Flushing writers", start);

                files
                    .into_iter()
                    .zip(shard_range)
                    .map(move |((f, cnt), _shard)| {
                        let start = std::time::Instant::now();
                        let mut v = vec![Hx::H::default(); cnt];
                        let mut reader = BufReader::new(f);
                        let (pre, data, post) = unsafe { v.align_to_mut::<u8>() };
                        assert!(pre.is_empty());
                        assert!(post.is_empty());
                        Read::read_exact(&mut reader, data).unwrap();
                        log_duration("Read shard", start);
                        v
                    })

                // Files are cleaned up automatically when tmpdir goes out of scope.
            });
        Box::new(it)
    }
}
```

--------------------------------

### Experimental API: clone_to_uninit

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/bucket_fn/struct.Optimal.html

An experimental, nightly-only API for performing copy-assignment to uninitialized memory.

```APIDOC
## unsafe fn clone_to_uninit(&self, dest: *mut u8)

### Description
🔬This is a nightly-only experimental API. (`clone_to_uninit`)
Performs copy-assignment from `self` to `dest`.

### Method
`clone_to_uninit`

### Parameters
- `dest`: A mutable raw pointer to the destination memory location.

### Safety
This function is unsafe because it operates on raw pointers and assumes the destination memory is valid and uninitialized.

### Read more
[Link to documentation for clone_to_uninit]
```

--------------------------------

### Get Bits Per Element

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/struct.PtrHash.html

Returns the number of bits used per element for pilots and remapping.

```rust
pub fn bits_per_element(&self) -> (f64, f64)
```

--------------------------------

### index_no_remap

Source: https://docs.rs/ptr_hash/1.1.0/src/ptr_hash/lib.rs.html?search=

Gets a non-minimal index for the given key, within the range `[0, n/alpha)`. This method does not apply remapping.

```APIDOC
## index_no_remap

### Description
Calculates and returns a non-minimal index for the given key. The index is guaranteed to be within the range `[0, n/alpha)`, and this method does not apply any remapping.

### Method
`PtrHash::index_no_remap`

### Parameters
#### Path Parameters
- **key** (`&Key`) - The key for which to compute the index.

### Return Value
`usize` - A non-minimal index for the key.

### Example
```rust
let index = ptr_hash.index_no_remap(&my_key);
```
```

--------------------------------

### impl<T> CloneToUninit for T

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/bucket_fn/struct.CubicEps.html?search=u32+-%3E+bool

Provides the `clone_to_uninit` method for cloning to uninitialized memory (nightly-only).

```APIDOC
## unsafe fn clone_to_uninit(&self, dest: *mut u8)

### Description
Performs copy-assignment from `self` to `dest`. This is a nightly-only experimental API.

### Method
`clone_to_uninit`

### Parameters
- **dest** (*mut u8): A mutable pointer to the destination memory.

### Response
None
```

--------------------------------

### index

Source: https://docs.rs/ptr_hash/1.1.0/src/ptr_hash/lib.rs.html

Gets the minimal index for the given key, within the range `[0, n)`. This method handles remapping if necessary.

```APIDOC
## index

### Description
Get the index for `key` in `[0, n)`.

### Method
`PtrHash::index`

### Parameters
#### Path Parameters
- **key** (`&Key`): The key to find the index for.

### Return Value
- `usize`: The minimal index for the key.
```

--------------------------------

### PtrHash Initialization Helper

Source: https://docs.rs/ptr_hash/1.1.0/src/ptr_hash/lib.rs.html?search=

Internal helper function to initialize PtrHash parameters without computing pilots. It asserts the number of keys is within the supported limit (less than 2^40) and calculates initial sharding and parts based on parameters and key count.

```rust
fn init(n: usize, mut params: PtrHashParams<BF>) -> Self {
    assert!(n < (1 << 40), "Number of keys must be less than 2^40.");

    let shards = match params.sharding {
        Sharding::None => 1,
        _ => n.div_ceil(params.keys_per_shard),
    };

    let mut keys_per_part;
    let mut parts_per_shard;
    let mut buckets_per_part;

    let mut parts;
    let mut buckets_total;
    let mut slots_total;
    let mut slots_per_part;

    // Avoid overly small parts.
    parts = (n / 1024).next_power_of_two().next_multiple_of(shards);
    if params.single_part {
        parts = 1;
    }

    // Compute the optimal number of parts and slots per part.
    // - Smaller parts have better cache locality and hence faster construction.
    // - Larger parts have more uniform sizes, and hence fewer outliers with load factor close to 1.
}
```

--------------------------------

### fn load_mmap<'a>(path: impl AsRef<Path>, flags: Flags) -> Result<MemCase<Self::DeserType<'a>>, Error>

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/hash/struct.Xx64.html

Loads a file into `mmap()`-allocated memory and ε-deserializes a data structure from it.

```APIDOC
## fn load_mmap<'a>(path: impl AsRef<Path>, flags: Flags) -> Result<MemCase<Self::DeserType<'a>>, Error>

### Description
Load a file into `mmap()`-allocated memory and ε-deserialize a data structure from it, returning a `MemCase` containing the data structure and the memory. Excess bytes are zeroed out.

### Method
`load_mmap`

### Parameters
- **path** (impl AsRef<Path>): The path to the file.
- **flags** (Flags): Flags to control memory mapping behavior.

### Response
#### Success Response
- **MemCase<Self::DeserType<'a>>**: A `MemCase` containing the deserialized data structure and its memory mapping.
#### Error Response
- **Error**: An error occurred during deserialization.
```

--------------------------------

### Get Non-Minimal Index with PtrHash

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash?search=u32+-%3E+bool

Retrieves a non-minimal index for a key, which can be slightly faster and returns indices up to approximately `n/alpha`.

```rust
// Get the non-minimal index of a key.
// Can be slightly faster returns keys up to `n/alpha ~ 1.01*n`.
let _idx = mphf.index_no_remap(&key);
```

--------------------------------

### Get Max Index in PtrHash

Source: https://docs.rs/ptr_hash/1.1.0/src/ptr_hash/lib.rs.html?search=

Returns the maximum possible index value, which is `slots_total`. This bound is always greater than or equal to 'n'.

```rust
pub fn max_index(&self) -> usize {
        self.slots_total
    }

```

--------------------------------

### TryConv Method

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash/bucket_fn/struct.Optimal.html

Provides a method to attempt conversion into another type using `TryInto`.

```APIDOC
## TryConv Method

### `try_conv<T>(self) -> Result<T, Self::Error> where Self: TryInto<T>`
Attempts to convert `self` into `T` using `TryInto<T>`.
```

--------------------------------

### Default Fast Parameters for Linear Bucket Function

Source: https://docs.rs/ptr_hash/1.1.0/src/ptr_hash/lib.rs.html?search=std%3A%3Avec

Use these parameters for fast construction and for small inputs (<1M keys). They offer up to 2x faster queries than the default version.

```rust
pub fn default_fast() -> Self {
        Self {
            remap: true,
            alpha: 0.99,
            lambda: 3.0,
            bucket_fn: Linear,
            keys_per_shard: 1 << 31,
            sharding: Sharding::None,
            single_part: false,
        }
    }
```

--------------------------------

### Get Index of a Key with PtrHash

Source: https://docs.rs/ptr_hash/1.1.0/ptr_hash?search=u32+-%3E+bool

Retrieves the minimal perfect hash index for a given key. Asserts that the index is within the expected range.

```rust
// Get the index of a key.
let key = 0;
let idx = mphf.index(&key);
assert!(idx < n);
```

--------------------------------

### Iterate over keys and get indices in batches

Source: https://docs.rs/ptr_hash/1.1.0/src/ptr_hash/lib.rs.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Queries keys in batches of size K and returns an iterator over their indices. Does not process the remainder of the input iterator.

```rust
    /// Takes an iterator over keys and returns an iterator over the indices of the keys.
    ///
    /// Queries in batches of size K.
    ///
    /// NOTE: Does not process the remainder
    #[doc(hidden)]
    #[cfg(feature = "unstable")]
    #[inline]
    pub fn index_batch_exact<'a, const K: usize, const MINIMAL: bool>(
        &'a self,
        xs: impl IntoIterator<Item = &'a Key> + 'a,
    ) -> impl Iterator<Item = usize> + 'a {
        let mut buckets: [usize; K] = [0; K];

        // Work on chunks of size K.
        let mut f = {
            #[inline(always)]
            move |hx: [Hx::H; K]| {
                // Prefetch.
                for idx in 0..K {
                    buckets[idx] = self.bucket(hx[idx]);
                    crate::util::prefetch_index(self.pilots.as_ref(), buckets[idx]);
                }
                // Query.
                (0..K).map(
                    #[inline(always)]
                    move |idx| {
                        let pilot = self.pilots.as_ref().index(buckets[idx]);
                        let slot = self.slot(hx[idx], pilot);
                        if MINIMAL && slot >= self.n {
                            self.remap.index(slot - self.n) as usize
                        } else {
                            slot
                        }
                    },
                )
            }
        };
        let array_chunks = xs.into_iter().map(|x| self.hash_key(x)).array_chunks::<K>();
        array_chunks.into_iter().flat_map(
            #[inline(always)]
            move |chunk| f(chunk),
        )
        // .chain(f(&array_chunks
        //     .into_remainder()
        //     .unwrap_or_default()
        //     .into_iter()))
    }
```

--------------------------------

### Optimal Bucket Function Implementation (PHOBIC)

Source: https://docs.rs/ptr_hash/1.1.0/src/ptr_hash/bucket_fn.rs.html

Implements the optimal bucket function from PHOBIC, which uses a variable epsilon to skew the hash distribution. This function is designed for optimal performance in specific hashing scenarios.

```rust
pub struct Optimal {
    pub eps: f64,
}

impl BucketFn for Optimal {
    fn call(&self, x: u64) -> u64 {
        let p32 = (1u64 << 32) as f64;
        let p64 = p32 * p32;
        let p64inv = 1. / p64;
        let x = (x as f64) * p64inv;
        let y = x + (1. - self.eps) * (1. - x) * (1. - x).ln();

        (y * p64) as u64
    }
}
```

--------------------------------

### PtrHash Initialization Helper

Source: https://docs.rs/ptr_hash/1.1.0/src/ptr_hash/lib.rs.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E

Internal helper function to initialize PtrHash parameters before computing pilots. It asserts the number of keys and calculates initial sharding and parts based on parameters.

```rust
fn init(n: usize, mut params: PtrHashParams<BF>) -> Self {
    assert!(n < (1 << 40), "Number of keys must be less than 2^40.");

    let shards = match params.sharding {
        Sharding::None => 1,
        _ => n.div_ceil(params.keys_per_shard),
    };

    let mut keys_per_part;
    let mut parts_per_shard;
    let mut buckets_per_part;

    let mut parts;
    let mut buckets_total;
    let mut slots_total;
    let mut slots_per_part;

    // Avoid overly small parts.
    parts = (n / 1024).next_power_of_two().next_multiple_of(shards);
    if params.single_part {
        parts = 1;
    }

    // Compute the optimal number of parts and slots per part.
    // - Smaller parts have better cache locality and hence faster construction.
    // - Larger parts have more uniform sizes, and hence fewer outliers with load factor close to 1.
    // ... (rest of the function body is omitted in the source)
```
Tokens:
Raw