This is an automated email from the ASF dual-hosted git repository.
tisonkun pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git
The following commit(s) were added to refs/heads/main by this push:
new aa4e070 perf(bloom): simplify insertion and clarify hash functions
(#311)
aa4e070 is described below
commit aa4e070c35f7b4cd97710cb382d91879c1d8ff22
Author: tison <[email protected]>
AuthorDate: Tue Oct 27 15:50:47 2026 +0800
perf(bloom): simplify insertion and clarify hash functions (#311)
---
datasketches/src/bloom/mod.rs | 9 +++++----
datasketches/src/bloom/sketch.rs | 18 ++++++++----------
tests-integration/tests/bloom_test/sketch.rs | 2 +-
3 files changed, 14 insertions(+), 15 deletions(-)
diff --git a/datasketches/src/bloom/mod.rs b/datasketches/src/bloom/mod.rs
index ff49e3f..5b2fbce 100644
--- a/datasketches/src/bloom/mod.rs
+++ b/datasketches/src/bloom/mod.rs
@@ -65,7 +65,7 @@
//!
//! ## By Accuracy (Recommended)
//!
-//! Derive the size and hash-function count from an expected distinct-item
count and a target
+//! Derive the size and number of hash functions from an expected
distinct-item count and a target
//! false-positive probability:
//!
//! ```
@@ -88,7 +88,8 @@
//!
//! ## By Size (Manual)
//!
-//! Specify requested bit count and hash functions (rounded up to a multiple
of 64 bits):
+//! Specify the requested bit count and number of hash functions. Capacity is
rounded up to a
+//! multiple of 64 bits:
//!
//! ```
//! use datasketches::bloom::BloomFilterBuilder;
@@ -138,8 +139,8 @@
//!
//! # Implementation Details
//!
-//! * Uses XXHash64 for hashing
-//! * Implements double hashing (Kirsch-Mitzenmacher method) for k hash
functions
+//! * Derives `k` hash functions from two XXHash64 hashes using double hashing
+//! (Kirsch-Mitzenmacher).
//! * Bits packed efficiently in `u64` words
//! * Compatible serialization format (family ID: 21)
//!
diff --git a/datasketches/src/bloom/sketch.rs b/datasketches/src/bloom/sketch.rs
index 020f7a4..4dce8ab 100644
--- a/datasketches/src/bloom/sketch.rs
+++ b/datasketches/src/bloom/sketch.rs
@@ -42,7 +42,7 @@ const EMPTY_FLAG_MASK: u8 = 1 << 2;
pub struct BloomFilter {
/// Hash seed for all hash functions
seed: u64,
- /// Number of hash functions to use (k)
+ /// Number of hash functions (k).
num_hashes: u16,
/// Count of bits set to 1 (for statistics)
num_bits_set: u64,
@@ -136,12 +136,6 @@ impl BloomFilter {
/// assert!(filter.contains(&"apple"));
/// ```
pub fn insert<T: Hash>(&mut self, item: T) {
- // Reuse the conditional path when skipping writes on repeats is
cheaper.
- if self.num_hashes == 1 {
- let _ = self.contains_and_insert(&item);
- return;
- }
-
let (h0, h1) = self.compute_hash(&item);
for i in 1..=self.num_hashes {
let bit_index = self.compute_bit_index(h0, h1, i);
@@ -359,7 +353,10 @@ impl BloomFilter {
self.bit_array.len() * 64
}
- /// Returns the number of hash functions used.
+ /// Returns the number of hash functions (`k`).
+ ///
+ /// The `k` hash functions are derived from two base hashes using double
hashing.
+ /// Their bit positions may repeat.
pub fn num_hashes(&self) -> u16 {
self.num_hashes
}
@@ -656,7 +653,8 @@ impl BloomFilter {
/// Provides two construction modes:
/// * [`with_accuracy()`](Self::with_accuracy): Specify target items and false
positive rate
/// (recommended)
-/// * [`with_size()`](Self::with_size): Specify requested bit count and hash
functions (manual)
+/// * [`with_size()`](Self::with_size): Specify requested bit count and number
of hash functions
+/// (manual)
///
/// Configuration is stored without validation and checked when
[`build()`](Self::build) is called.
/// Accuracy construction treats `max_items` as a sizing assumption, not an
insertion limit. The
@@ -735,7 +733,7 @@ impl BloomFilterBuilder {
/// # Arguments
///
/// * `num_bits`: Total number of bits in the filter.
- /// * `num_hashes`: Number of hash functions to use.
+ /// * `num_hashes`: Number of hash functions (`k`); see
[`BloomFilter::num_hashes`].
///
/// # Examples
///
diff --git a/tests-integration/tests/bloom_test/sketch.rs
b/tests-integration/tests/bloom_test/sketch.rs
index fe0a0a7..11c27c4 100644
--- a/tests-integration/tests/bloom_test/sketch.rs
+++ b/tests-integration/tests/bloom_test/sketch.rs
@@ -71,7 +71,7 @@ fn test_insert_matches_membership_and_insert() {
#[test]
fn test_collisions_and_repeated_inserts_do_not_overcount_bits() {
- // Cover the single-hash path and force within-item collisions: 65 hashes
cannot
+ // Exercise one hash and force within-item collisions: 65 hashes cannot
// select distinct positions in a 64-bit filter.
for num_hashes in [1, 65] {
let mut inserted = BloomFilterBuilder::with_size(64, num_hashes)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
