# qht
[![Latest version](https://img.shields.io/crates/v/qht.svg)](https://crates.io/crates/qht)
[![Documentation](https://docs.rs/qht/badge.svg)](https://docs.rs/qht)
[![Build Status](https://travis-ci.org/ovheurdrive/qht-rs.svg?branch=master)](https://travis-ci.org/ovheurdrive/qht-rs)
![Long time support rustc version](https://img.shields.io/badge/rustc-1.31%2B-green.svg)
![License](https://img.shields.io/badge/License-MIT-blue.svg)
A Rust implementation of Quotient Hash Tables, a reasonably efficient approximate duplicate detection algorithm. [See paper here](https://arxiv.org/abs/1901.04358).
## 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](LICENSE) file for details