qht

A Rust implementation of Quotient Hash Tables, a reasonably efficient approximate duplicate detection algorithm. See paper here.

How to use

```rust extern crate qht; extern crate rand;

use qht::*; use rand::rngs::StdRng; use rand::{FromEntropy, Rng};

fn main() { // Creates a new quotient hash table with 1 bucket and a fingerpint size of 3 let mut f = QuotientHashTable::new(1024, 8, 3); // Initialize PRNG let mut rng = StdRng::from_entropy();

let mut measured_collisions = 0;
let mut actual_collisions = 0;
let mut elements : Vec<u64> = Vec::with_capacity(1000);

for _ in 0..10000 {
    // We generate a random element
    let element = rng.gen_range(0, 1000);

    // Check if it's in the Hash Table
    if f.lookup(element) {
        measured_collisions+=1;
    } else {
        // Insert it if it's not
        f.insert(element);
    }

    // Check if the element has been generated
    if elements.contains(&element) {
        actual_collisions+=1;
    } else {
        // Record it if it's not
        elements.push(element);
    }
}

println!("Measured Collisions {}, Actual Collisions {} ", measured_collisions, actual_collisions);

}

```

Running the tests

Public functions are tested in their documentation. Other miscellaneous tests are written in lib.rs. Run the tests with

cargo test

Running the benchmarks

The Criterion dependency is used to provide precise benchmarkings. Benchmarks can be run with cargo bench

Documentation

Generate the documentation with

cargo doc --no-deps

License

This project is licensed under the MIT License - see the LICENSE file for details