I was thinking about incorporating rayon in certain sections of the code behind a feature flag.
For instance
pub fn most_common_tiebreaker<F>
could be changed as follows

pub fn most_common_tiebreaker<F>(&self, mut tiebreaker: F) -> Vec<(T, N)>
where
    F: FnMut(&T, &T) -> ::std::cmp::Ordering + Send + Sync,
{
    let mut items = self
        .map
        .iter() // i'm not sure if changing this into par_iter() would be more useful or needless complication
        .map(|(key, count)| (key.clone(), count.clone()))
        .collect::<Vec<_>>();
    #[cfg(feature = "use_rayon")]
    {
        use rayon::prelude::*;
        items.par_sort_unstable_by(|(a_item, a_count), (b_item, b_count)| {
            b_count
                .cmp(a_count)
                .then_with(|| tiebreaker(a_item, b_item))
        });
    }
    #[cfg(not(feature = "use_rayon"))]
    {
        items.sort_unstable_by(|(a_item, a_count), (b_item, b_count)| {
            b_count
                .cmp(a_count)
                .then_with(|| tiebreaker(a_item, b_item))
        });
    }
    items
}

Similar feature flag based dependencies would be set in Cargo.toml as well.
Overall, this would be integrated in a way that preserves default behavior unless a feature flag is set (likely as rayon)

If you are open to this, I would first begin by initiating a bit of refactoring first.
Most if not all of the code is situated inside lib.rs which is now pushing 2k loc.
I think the unit tests can be extracted into /src/lib/tests.rs as a separate file.
This is in contrast to /tests/integration_tests.rs which would be for integration tests.
Of course, if any specific test is identified to be more suitable for integration tests I would extract them and organise them as such.

What do you feel about each?

• Refactoring the code, especially for the tests.
• Adding rayon (behind a feature flag to preserve default behavior)