1///|
2/// 创建新的 Bloomier Filter
3///
4/// # Example
5/// ```
6/// let config = { expected_elements: 1000, false_positive_rate: 0.01, hash_functions: None }
7/// let filter = @BloomierFilter.new(config)
8/// ```
9pub fn (config : BloomierConfig) -> BloomierFilter[K, V]
创建新的 Bloomier Filter
Example
let config = { expected_elements: 1000, false_positive_rate: 0.01, hash_functions: None }
let filter = @BloomierFilter.new(config)
new[K : trait Hash {
hash_combine(Self, Hasher) -> Unit
hash(Self) -> Int
}
Trait for types that can be hashed
Hash + trait Eq {
op_equal(Self, Self) -> Bool
}
Trait for types whose elements can test for equality
Eq, V](BloomierConfig
config : struct BloomierConfig {
expected_elements: Int
false_positive_rate: Double
hash_functions: Int?
}
Bloomier Filter 的配置参数
BloomierConfig) -> struct BloomierFilter[K, V] {
mut table: Array[V?]
mut table_size: Int
hash_count: Int
mut seeds: Array[Int]
mut size: Int
}
Bloomier Filter 数据结构
支持存储键值对并进行快速查询
BloomierFilter[type parameter K
K, type parameter V
V] {
10 // 计算最优表大小
11 let Int
table_size = (expected_elements : Int, false_positive_rate : Double) -> Int
计算最优表大小
calculate_table_size(
12 BloomierConfig
config.Int
预期的元素数量
expected_elements,
13 BloomierConfig
config.Double
误报率（0.0 到 1.0 之间）
false_positive_rate,
14 )
15
16 // 计算哈希函数数量
17 let Int
hash_count = match BloomierConfig
config.Int?
哈希函数数量（可选，如果为None则自动计算）
hash_functions {
18 (Int) -> Int?
Some(Int
count) => Int
count
19 Int?
None => (expected_elements : Int, table_size : Int) -> Int
计算最优哈希函数数量
calculate_optimal_hash_count(BloomierConfig
config.Int
预期的元素数量
expected_elements, Int
table_size)
20 }
21 if Int
hash_count (self_ : Int, other : Int) -> Bool
<= 0 (Bool, Bool) -> Bool
|| Int
table_size (self_ : Int, other : Int) -> Bool
<= 0 {
22 (msg : String) -> Unit
Aborts the program with an error message. Always causes a panic, regardless
of the message provided.
Parameters:
message : A string containing the error message to be displayed when
aborting.
Returns a value of type T. However, this function never actually returns a
value as it always causes a panic.
abort("Invalid hash count or table size")
23 }
24
25 // 生成随机种子
26 let Array[Int]
seeds = (count : Int) -> Array[Int]
使用数学公式生成种子
generate_seeds(Int
hash_count)
27 {
28 Array[V?]
哈希表数组，存储实际的值
table: type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array::(Int, V?) -> Array[V?]
Creates a new array with a specified length and initializes all elements with
the given value.
Parameters:
length : The length of the array to create. Must be a non-negative
integer.initial_value : The value used to initialize all elements in the array.
Returns a new array of type Array[T] with length elements, where each
element is initialized to initial_value.
Throws an error if length is negative.
Example:
let arr = Array::make(3, 42)
inspect(arr, content="[42, 42, 42]")
WARNING: A common pitfall is creating with the same initial value, for example:
let two_dimension_array = Array::make(10, Array::make(10, 0))
two_dimension_array[0][5] = 10
assert_eq(two_dimension_array[5][5], 10)
This is because all the cells reference to the same object (the Array[Int] in this case).
One should use makei() instead which creates an object for each index.
make(Int
table_size, V?
None),
29 Int
table_size,
30 Int
hash_count,
31 Array[Int]
seeds,
32 Int
当前存储的元素数量
size: 0,
33 }
34}
35
36///|
37/// 从键值对数组创建 Bloomier Filter
38///
39/// # Example
40/// ```
41/// let items = [("key1", "value1"), ("key2", "value2")]
42/// let filter = @BloomierFilter.from_array(items, config)
43/// ```
44pub fn (items : Array[(K, V)], config : BloomierConfig) -> BloomierFilter[K, V]
从键值对数组创建 Bloomier Filter
Example
let items = [("key1", "value1"), ("key2", "value2")]
let filter = @BloomierFilter.from_array(items, config)
from_array[K : trait Hash {
hash_combine(Self, Hasher) -> Unit
hash(Self) -> Int
}
Trait for types that can be hashed
Hash + trait Eq {
op_equal(Self, Self) -> Bool
}
Trait for types whose elements can test for equality
Eq, V](
45 Array[(K, V)]
items : type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[(type parameter K
K, type parameter V
V)],
46 BloomierConfig
config : struct BloomierConfig {
expected_elements: Int
false_positive_rate: Double
hash_functions: Int?
}
Bloomier Filter 的配置参数
BloomierConfig
47) -> struct BloomierFilter[K, V] {
mut table: Array[V?]
mut table_size: Int
hash_count: Int
mut seeds: Array[Int]
mut size: Int
}
Bloomier Filter 数据结构
支持存储键值对并进行快速查询
BloomierFilter[type parameter K
K, type parameter V
V] {
48 let BloomierFilter[K, V]
filter = (config : BloomierConfig) -> BloomierFilter[K, V]
创建新的 Bloomier Filter
Example
let config = { expected_elements: 1000, false_positive_rate: 0.01, hash_functions: None }
let filter = @BloomierFilter.new(config)
new(BloomierConfig
config)
49
50 // 尝试构建过滤器
51 (filter : BloomierFilter[K, V], items : Array[(K, V)]) -> Unit
构建过滤器
build_filter(BloomierFilter[K, V]
filter, Array[(K, V)]
items)
52 BloomierFilter[K, V]
filter
53}
54
55///|
56/// 插入键值对
57///
58/// # Example
59/// ```
60/// match filter.insert("key", "value") {
61/// Success => println("插入成功")
62/// Failure => println("插入失败")
63/// NeedRehash => println("需要重新哈希")
64/// }
65/// ```
66pub fn (self : BloomierFilter[K, V], key : K, value : V) -> InsertResult
插入键值对
Example
match filter.insert("key", "value") {
Success => println("插入成功")
Failure => println("插入失败")
NeedRehash => println("需要重新哈希")
}
insert[K : trait Hash {
hash_combine(Self, Hasher) -> Unit
hash(Self) -> Int
}
Trait for types that can be hashed
Hash + trait Eq {
op_equal(Self, Self) -> Bool
}
Trait for types whose elements can test for equality
Eq, V](
67 BloomierFilter[K, V]
self : struct BloomierFilter[K, V] {
mut table: Array[V?]
mut table_size: Int
hash_count: Int
mut seeds: Array[Int]
mut size: Int
}
Bloomier Filter 数据结构
支持存储键值对并进行快速查询
BloomierFilter[type parameter K
K, type parameter V
V],
68 K
key : type parameter K
K,
69 V
value : type parameter V
V
70) -> enum InsertResult {
Success
Failure
NeedRehash
}
插入操作的结果
InsertResult {
71 if BloomierFilter[K, V]
self.Int
当前存储的元素数量
size (self_ : Int, other : Int) -> Bool
>= BloomierFilter[K, V]
self.Int
表的大小
table_size {
72 return InsertResult::InsertResult
插入失败（表已满或冲突）
Failure
73 }
74 let HashResult
hashes = (key : K, seeds : Array[Int], table_size : Int) -> HashResult
计算多个哈希值
compute_hashes(K
key, BloomierFilter[K, V]
self.Array[Int]
用于哈希计算的种子数组
seeds, BloomierFilter[K, V]
self.Int
表的大小
table_size)
75
76 // 检查是否有空槽位
77 let mut Int?
empty_slot = Int?
None
78 for Int
i = 0; Int
i (self_ : Int, other : Int) -> Bool
< HashResult
hashes.Array[Int]
哈希值数组
hashes.(self : Array[Int]) -> Int
Returns the number of elements in the array.
Parameters:
array : The array whose length is to be determined.
Returns the number of elements in the array as an integer.
Example:
let arr = [1, 2, 3]
inspect(arr.length(), content="3")
let empty : Array[Int] = []
inspect(empty.length(), content="0")
length(); Int
i = Int
i (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:
self : The first integer operand.other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
inspect(42 + 1, content="43")
inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ 1 {
79 let Int
index = HashResult
hashes.Array[Int]
哈希值数组
hashes(Array[Int], Int) -> Int
Retrieves an element from the array at the specified index.
Parameters:
array : The array to get the element from.index : The position in the array from which to retrieve the element.
Returns the element at the specified index.
Throws a panic if the index is negative or greater than or equal to the
length of the array.
Example:
let arr = [1, 2, 3]
inspect(arr[1], content="2")
[i]
80 match BloomierFilter[K, V]
self.Array[V?]
哈希表数组，存储实际的值
table(Array[V?], Int) -> V?
Retrieves an element from the array at the specified index.
Parameters:
array : The array to get the element from.index : The position in the array from which to retrieve the element.
Returns the element at the specified index.
Throws a panic if the index is negative or greater than or equal to the
length of the array.
Example:
let arr = [1, 2, 3]
inspect(arr[1], content="2")
[index] {
81 V?
None => {
82 Int?
empty_slot = (Int) -> Int?
Some(Int
index)
83 break
84 }
85 V?
Some(_) => continue
86 }
87 }
88 match Int?
empty_slot {
89 (Int) -> Int?
Some(Int
index) => {
90 BloomierFilter[K, V]
self.Array[V?]
哈希表数组，存储实际的值
table(Array[V?], Int, V?) -> Unit
Sets the element at the specified index in the array to a new value. The
original value at that index is overwritten.
Parameters:
array : The array to modify.index : The position in the array where the value will be set.value : The new value to assign at the specified index.
Throws an error if index is negative or greater than or equal to the length
of the array.
Example:
let arr = [1, 2, 3]
arr[1] = 42
inspect(arr, content="[1, 42, 3]")
[index] = (V) -> V?
Some(V
value)
91 BloomierFilter[K, V]
self.Int
当前存储的元素数量
size (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:
self : The first integer operand.other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
inspect(42 + 1, content="43")
inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+= 1
92 InsertResult::InsertResult
成功插入
Success
93 }
94 Int?
None => InsertResult::InsertResult
需要重新哈希
NeedRehash
95 }
96}
97
98///|
99/// 查询键对应的值
100///
101/// # Example
102/// ```
103/// match filter.get("key") {
104/// Found(value) => println("找到值: \{value}")
105/// NotFound => println("未找到")
106/// Uncertain => println("可能存在")
107/// }
108/// ```
109pub fn (self : BloomierFilter[K, V], key : K) -> QueryResult[V]
查询键对应的值
Example
match filter.get("key") {
Found(value) => println("找到值: \{value}")
NotFound => println("未找到")
Uncertain => println("可能存在")
}
get[K : trait Hash {
hash_combine(Self, Hasher) -> Unit
hash(Self) -> Int
}
Trait for types that can be hashed
Hash + trait Eq {
op_equal(Self, Self) -> Bool
}
Trait for types whose elements can test for equality
Eq, V](
110 BloomierFilter[K, V]
self : struct BloomierFilter[K, V] {
mut table: Array[V?]
mut table_size: Int
hash_count: Int
mut seeds: Array[Int]
mut size: Int
}
Bloomier Filter 数据结构
支持存储键值对并进行快速查询
BloomierFilter[type parameter K
K, type parameter V
V],
111 K
key : type parameter K
K
112) -> enum QueryResult[V] {
Found(V)
NotFound
Uncertain
}
查询操作的结果
QueryResult[type parameter V
V] {
113 let HashResult
hashes = (key : K, seeds : Array[Int], table_size : Int) -> HashResult
计算多个哈希值
compute_hashes(K
key, BloomierFilter[K, V]
self.Array[Int]
用于哈希计算的种子数组
seeds, BloomierFilter[K, V]
self.Int
表的大小
table_size)
114 let Array[V]
found_values = []
115 let mut Bool
has_empty = false
116 for Int
i = 0; Int
i (self_ : Int, other : Int) -> Bool
< HashResult
hashes.Array[Int]
哈希值数组
hashes.(self : Array[Int]) -> Int
Returns the number of elements in the array.
Parameters:
array : The array whose length is to be determined.
Returns the number of elements in the array as an integer.
Example:
let arr = [1, 2, 3]
inspect(arr.length(), content="3")
let empty : Array[Int] = []
inspect(empty.length(), content="0")
length(); Int
i = Int
i (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:
self : The first integer operand.other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
inspect(42 + 1, content="43")
inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ 1 {
117 let Int
index = HashResult
hashes.Array[Int]
哈希值数组
hashes(Array[Int], Int) -> Int
Retrieves an element from the array at the specified index.
Parameters:
array : The array to get the element from.index : The position in the array from which to retrieve the element.
Returns the element at the specified index.
Throws a panic if the index is negative or greater than or equal to the
length of the array.
Example:
let arr = [1, 2, 3]
inspect(arr[1], content="2")
[i]
118 match BloomierFilter[K, V]
self.Array[V?]
哈希表数组，存储实际的值
table(Array[V?], Int) -> V?
Retrieves an element from the array at the specified index.
Parameters:
array : The array to get the element from.index : The position in the array from which to retrieve the element.
Returns the element at the specified index.
Throws a panic if the index is negative or greater than or equal to the
length of the array.
Example:
let arr = [1, 2, 3]
inspect(arr[1], content="2")
[index] {
119 (V) -> V?
Some(V
value) => Array[V]
found_values.(self : Array[V], value : V) -> Unit
Adds an element to the end of the array.
If the array is at capacity, it will be reallocated.
Example
let v = []
v.push(3)
push(V
value)
120 V?
None => Bool
has_empty = true
121 }
122 }
123 if Array[V]
found_values.(self : Array[V]) -> Bool
Tests whether the array contains no elements.
Parameters:
array : The array to check.
Returns true if the array has no elements, false otherwise.
Example:
let empty : Array[Int] = []
inspect(empty.is_empty(), content="true")
let non_empty = [1, 2, 3]
inspect(non_empty.is_empty(), content="false")
is_empty() {
124 QueryResult::QueryResult[V]
未找到
NotFound
125 } else if Array[V]
found_values.(self : Array[V]) -> Int
Returns the number of elements in the array.
Parameters:
array : The array whose length is to be determined.
Returns the number of elements in the array as an integer.
Example:
let arr = [1, 2, 3]
inspect(arr.length(), content="3")
let empty : Array[Int] = []
inspect(empty.length(), content="0")
length() (self : Int, other : Int) -> Bool
Compares two integers for equality.
Parameters:
self : The first integer to compare.other : The second integer to compare.
Returns true if both integers have the same value, false otherwise.
Example:
inspect(42 == 42, content="true")
inspect(42 == -42, content="false")
== 1 (Bool, Bool) -> Bool
&& Bool
has_empty (self : Bool, other : Bool) -> Bool
Compares two boolean values for equality.
Parameters:
self : The first boolean value to compare.other : The second boolean value to compare.
Returns true if both boolean values are equal (either both true or both
false), false otherwise.
Example:
inspect(true == true, content="true")
inspect(false == true, content="false")
inspect(true == false, content="false")
inspect(false == false, content="true")
== false {
126 QueryResult::(V) -> QueryResult[V]
找到值
Found(Array[V]
found_values[0])
127 } else {
128 QueryResult::QueryResult[V]
可能存在但值不确定
Uncertain
129 }
130}
131
132///|
133/// 检查键是否可能存在
134///
135/// # Example
136/// ```
137/// if filter.contains("key") {
138/// println("键可能存在")
139/// } else {
140/// println("键一定不存在")
141/// }
142/// ```
143pub fn (self : BloomierFilter[K, V], key : K) -> Bool
检查键是否可能存在
Example
if filter.contains("key") {
println("键可能存在")
} else {
println("键一定不存在")
}
contains[K : trait Hash {
hash_combine(Self, Hasher) -> Unit
hash(Self) -> Int
}
Trait for types that can be hashed
Hash + trait Eq {
op_equal(Self, Self) -> Bool
}
Trait for types whose elements can test for equality
Eq, V](BloomierFilter[K, V]
self : struct BloomierFilter[K, V] {
mut table: Array[V?]
mut table_size: Int
hash_count: Int
mut seeds: Array[Int]
mut size: Int
}
Bloomier Filter 数据结构
支持存储键值对并进行快速查询
BloomierFilter[type parameter K
K, type parameter V
V], K
key : type parameter K
K) -> Bool
Bool {
144 match BloomierFilter[K, V]
self.(self : BloomierFilter[K, V], key : K) -> QueryResult[V]
查询键对应的值
Example
match filter.get("key") {
Found(value) => println("找到值: \{value}")
NotFound => println("未找到")
Uncertain => println("可能存在")
}
get(K
key) {
145 QueryResult::QueryResult[V]
未找到
NotFound => false
146 _ => true
147 }
148}
149
150///|
151/// 获取过滤器大小
152///
153/// # Example
154/// ```
155/// println("当前存储了 \{filter.size()} 个元素")
156/// ```
157pub fn (self : BloomierFilter[K, V]) -> Int
获取过滤器大小
Example
println("当前存储了 \{filter.size()} 个元素")
size[K, V](BloomierFilter[K, V]
self : struct BloomierFilter[K, V] {
mut table: Array[V?]
mut table_size: Int
hash_count: Int
mut seeds: Array[Int]
mut size: Int
}
Bloomier Filter 数据结构
支持存储键值对并进行快速查询
BloomierFilter[type parameter K
K, type parameter V
V]) -> Int
Int {
158 BloomierFilter[K, V]
self.Int
当前存储的元素数量
size
159}
160
161///|
162/// 检查过滤器是否为空
163///
164/// # Example
165/// ```
166/// if filter.is_empty() {
167/// println("过滤器为空")
168/// }
169/// ```
170pub fn (self : BloomierFilter[K, V]) -> Bool
检查过滤器是否为空
Example
if filter.is_empty() {
println("过滤器为空")
}
is_empty[K, V](BloomierFilter[K, V]
self : struct BloomierFilter[K, V] {
mut table: Array[V?]
mut table_size: Int
hash_count: Int
mut seeds: Array[Int]
mut size: Int
}
Bloomier Filter 数据结构
支持存储键值对并进行快速查询
BloomierFilter[type parameter K
K, type parameter V
V]) -> Bool
Bool {
171 BloomierFilter[K, V]
self.Int
当前存储的元素数量
size (self : Int, other : Int) -> Bool
Compares two integers for equality.
Parameters:
self : The first integer to compare.other : The second integer to compare.
Returns true if both integers have the same value, false otherwise.
Example:
inspect(42 == 42, content="true")
inspect(42 == -42, content="false")
== 0
172}
173
174///|
175/// 清空过滤器
176///
177/// # Example
178/// ```
179/// filter.clear()
180/// assert_eq!(filter.size(), 0)
181/// ```
182pub fn (self : BloomierFilter[K, V]) -> Unit
清空过滤器
Example
filter.clear()
assert_eq!(filter.size(), 0)
clear[K, V](BloomierFilter[K, V]
self : struct BloomierFilter[K, V] {
mut table: Array[V?]
mut table_size: Int
hash_count: Int
mut seeds: Array[Int]
mut size: Int
}
Bloomier Filter 数据结构
支持存储键值对并进行快速查询
BloomierFilter[type parameter K
K, type parameter V
V]) -> Unit
Unit {
183 for Int
i = 0; Int
i (self_ : Int, other : Int) -> Bool
< BloomierFilter[K, V]
self.Array[V?]
哈希表数组，存储实际的值
table.(self : Array[V?]) -> Int
Returns the number of elements in the array.
Parameters:
array : The array whose length is to be determined.
Returns the number of elements in the array as an integer.
Example:
let arr = [1, 2, 3]
inspect(arr.length(), content="3")
let empty : Array[Int] = []
inspect(empty.length(), content="0")
length(); Int
i = Int
i (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:
self : The first integer operand.other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
inspect(42 + 1, content="43")
inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ 1 {
184 BloomierFilter[K, V]
self.Array[V?]
哈希表数组，存储实际的值
table(Array[V?], Int, V?) -> Unit
Sets the element at the specified index in the array to a new value. The
original value at that index is overwritten.
Parameters:
array : The array to modify.index : The position in the array where the value will be set.value : The new value to assign at the specified index.
Throws an error if index is negative or greater than or equal to the length
of the array.
Example:
let arr = [1, 2, 3]
arr[1] = 42
inspect(arr, content="[1, 42, 3]")
[i] = V?
None
185 }
186 BloomierFilter[K, V]
self.Int
当前存储的元素数量
size = 0
187}
188
189///|
190/// 获取统计信息
191///
192/// # Example
193/// ```
194/// let stats = filter.stats()
195/// println("负载因子: \{stats.load_factor}")
196/// ```
197pub fn (self : BloomierFilter[K, V]) -> BloomierStats
获取统计信息
Example
let stats = filter.stats()
println("负载因子: \{stats.load_factor}")
stats[K, V](BloomierFilter[K, V]
self : struct BloomierFilter[K, V] {
mut table: Array[V?]
mut table_size: Int
hash_count: Int
mut seeds: Array[Int]
mut size: Int
}
Bloomier Filter 数据结构
支持存储键值对并进行快速查询
BloomierFilter[type parameter K
K, type parameter V
V]) -> struct BloomierStats {
table_size: Int
stored_elements: Int
load_factor: Double
hash_functions: Int
free_slots: Int
}
统计信息
BloomierStats {
198 let Int
free_slots = BloomierFilter[K, V]
self.Int
表的大小
table_size (self : Int, other : Int) -> Int
Performs subtraction between two 32-bit integers, following standard two's
complement arithmetic rules. When the result overflows or underflows, it
wraps around within the 32-bit integer range.
Parameters:
self : The minuend (the number being subtracted from).other : The subtrahend (the number to subtract).
Returns the difference between self and other.
Example:
let a = 42
let b = 10
inspect(a - b, content="32")
let max = 2147483647 // Int maximum value
inspect(max - -1, content="-2147483648") // Overflow case
- BloomierFilter[K, V]
self.Int
当前存储的元素数量
size
199 let Double
load_factor = BloomierFilter[K, V]
self.Int
当前存储的元素数量
size.(self : Int) -> Double
Converts a 32-bit integer to a double-precision floating-point number. The
conversion preserves the exact value since all integers in the range of Int
can be represented exactly as Double values.
Parameters:
self : The 32-bit integer to be converted.
Returns a double-precision floating-point number that represents the same
numerical value as the input integer.
Example:
let n = 42
inspect(n.to_double(), content="42")
let neg = -42
inspect(neg.to_double(), content="-42")
to_double() (self : Double, other : Double) -> Double
Performs division between two double-precision floating-point numbers.
Follows IEEE 754 standard for floating-point arithmetic, including handling
of special cases like division by zero (returns infinity) and operations
involving NaN.
Parameters:
self : The dividend (numerator) in the division operation.other : The divisor (denominator) in the division operation.
Returns the result of dividing self by other. Special cases follow IEEE
754:
- Division by zero returns positive or negative infinity based on the
dividend's sign
- Operations involving NaN return NaN
- Division of infinity by infinity returns NaN
Example:
inspect(6.0 / 2.0, content="3")
inspect(-6.0 / 2.0, content="-3")
inspect(1.0 / 0.0, content="Infinity")
/ BloomierFilter[K, V]
self.Int
表的大小
table_size.(self : Int) -> Double
Converts a 32-bit integer to a double-precision floating-point number. The
conversion preserves the exact value since all integers in the range of Int
can be represented exactly as Double values.
Parameters:
self : The 32-bit integer to be converted.
Returns a double-precision floating-point number that represents the same
numerical value as the input integer.
Example:
let n = 42
inspect(n.to_double(), content="42")
let neg = -42
inspect(neg.to_double(), content="-42")
to_double()
200 {
201 Int
表大小
table_size: BloomierFilter[K, V]
self.Int
表的大小
table_size,
202 Int
已存储元素数量
stored_elements: BloomierFilter[K, V]
self.Int
当前存储的元素数量
size,
203 Double
load_factor,
204 Int
哈希函数数量
hash_functions: BloomierFilter[K, V]
self.Int
哈希函数的数量
hash_count,
205 Int
free_slots,
206 }
207}
208
209///|
210/// 序列化过滤器
211///
212/// # Example
213/// ```
214/// let serialized = filter.serialize()
215/// ```
216pub fn (self : BloomierFilter[K, V]) -> SerializedBloomier[V]
序列化过滤器
Example
let serialized = filter.serialize()
serialize[K, V : trait Eq {
op_equal(Self, Self) -> Bool
}
Trait for types whose elements can test for equality
Eq](
217 BloomierFilter[K, V]
self : struct BloomierFilter[K, V] {
mut table: Array[V?]
mut table_size: Int
hash_count: Int
mut seeds: Array[Int]
mut size: Int
}
Bloomier Filter 数据结构
支持存储键值对并进行快速查询
BloomierFilter[type parameter K
K, type parameter V
V]
218) -> struct SerializedBloomier[V] {
table_data: Array[V?]
table_size: Int
hash_count: Int
seeds: Array[Int]
version: Int
}
序列化格式
SerializedBloomier[type parameter V
V] {
219 {
220 Array[V?]
表数据
table_data: BloomierFilter[K, V]
self.Array[V?]
哈希表数组，存储实际的值
table.(self : Array[V?]) -> Array[V?]
Creates and returns a new array with a copy of all elements from the input
array.
Parameters:
array : The array to be copied.
Returns a new array containing all elements from the original array.
Example:
let original = [1, 2, 3]
let copied = original.copy()
inspect(copied, content="[1, 2, 3]")
inspect(physical_equal(original, copied), content="false")
copy(),
221 Int
表大小
table_size: BloomierFilter[K, V]
self.Int
表的大小
table_size,
222 Int
哈希函数数量
hash_count: BloomierFilter[K, V]
self.Int
哈希函数的数量
hash_count,
223 Array[Int]
哈希种子
seeds: BloomierFilter[K, V]
self.Array[Int]
用于哈希计算的种子数组
seeds.(self : Array[Int]) -> Array[Int]
Creates and returns a new array with a copy of all elements from the input
array.
Parameters:
array : The array to be copied.
Returns a new array containing all elements from the original array.
Example:
let original = [1, 2, 3]
let copied = original.copy()
inspect(copied, content="[1, 2, 3]")
inspect(physical_equal(original, copied), content="false")
copy(),
224 Int
版本号
version: 1,
225 }
226}
227
228///|
229/// 从序列化数据反序列化
230///
231/// # Example
232/// ```
233/// let filter = @BloomierFilter.deserialize(serialized_data)!
234/// ```
235pub fn (data : SerializedBloomier[V]) -> BloomierFilter[K, V]
从序列化数据反序列化
Example
let filter = @BloomierFilter.deserialize(serialized_data)!
deserialize[K, V](SerializedBloomier[V]
data : struct SerializedBloomier[V] {
table_data: Array[V?]
table_size: Int
hash_count: Int
seeds: Array[Int]
version: Int
}
序列化格式
SerializedBloomier[type parameter V
V]) -> struct BloomierFilter[K, V] {
mut table: Array[V?]
mut table_size: Int
hash_count: Int
mut seeds: Array[Int]
mut size: Int
}
Bloomier Filter 数据结构
支持存储键值对并进行快速查询
BloomierFilter[type parameter K
K, type parameter V
V] {
236 if SerializedBloomier[V]
data.Int
版本号
version (x : Int, y : Int) -> Bool
!= 1 {
237 (msg : String) -> Unit
Aborts the program with an error message. Always causes a panic, regardless
of the message provided.
Parameters:
message : A string containing the error message to be displayed when
aborting.
Returns a value of type T. However, this function never actually returns a
value as it always causes a panic.
abort("Unsupported version")
238 }
239 {
240 Array[V?]
哈希表数组，存储实际的值
table: SerializedBloomier[V]
data.Array[V?]
表数据
table_data,
241 Int
表的大小
table_size: SerializedBloomier[V]
data.Int
表大小
table_size,
242 Int
哈希函数的数量
hash_count: SerializedBloomier[V]
data.Int
哈希函数数量
hash_count,
243 Array[Int]
用于哈希计算的种子数组
seeds: SerializedBloomier[V]
data.Array[Int]
哈希种子
seeds,
244 Int
当前存储的元素数量
size: (table : Array[V?]) -> Int
统计非空槽位数量
count_non_empty_slots(SerializedBloomier[V]
data.Array[V?]
表数据
table_data),
245 }
246}
247
248// ===== 私有辅助函数 =====
249
250///|
251/// 计算最优表大小
252fn (expected_elements : Int, false_positive_rate : Double) -> Int
计算最优表大小
calculate_table_size(
253 Int
expected_elements : Int
Int,
254 Double
false_positive_rate : Double
Double
255) -> Int
Int {
256 let Double
ln2 = 0.693147180559945
257 (-1.0 (self : Double, other : Double) -> Double
Multiplies two double-precision floating-point numbers. This is the
implementation of the * operator for Double type.
Parameters:
self : The first double-precision floating-point operand.other : The second double-precision floating-point operand.
Returns a new double-precision floating-point number representing the product
of the two operands. Special cases follow IEEE 754 standard:
- If either operand is NaN, returns NaN
- If one operand is infinity and the other is zero, returns NaN
- If one operand is infinity and the other is a non-zero finite number,
returns infinity with the appropriate sign
- If both operands are infinity, returns infinity with the appropriate sign
Example:
inspect(2.5 * 2.0, content="5")
inspect(-2.0 * 3.0, content="-6")
let nan = 0.0 / 0.0 // NaN
inspect(nan * 1.0, content="NaN")
* Int
expected_elements.(self : Int) -> Double
Converts a 32-bit integer to a double-precision floating-point number. The
conversion preserves the exact value since all integers in the range of Int
can be represented exactly as Double values.
Parameters:
self : The 32-bit integer to be converted.
Returns a double-precision floating-point number that represents the same
numerical value as the input integer.
Example:
let n = 42
inspect(n.to_double(), content="42")
let neg = -42
inspect(neg.to_double(), content="-42")
to_double() (self : Double, other : Double) -> Double
Multiplies two double-precision floating-point numbers. This is the
implementation of the * operator for Double type.
Parameters:
self : The first double-precision floating-point operand.other : The second double-precision floating-point operand.
Returns a new double-precision floating-point number representing the product
of the two operands. Special cases follow IEEE 754 standard:
- If either operand is NaN, returns NaN
- If one operand is infinity and the other is zero, returns NaN
- If one operand is infinity and the other is a non-zero finite number,
returns infinity with the appropriate sign
- If both operands are infinity, returns infinity with the appropriate sign
Example:
inspect(2.5 * 2.0, content="5")
inspect(-2.0 * 3.0, content="-6")
let nan = 0.0 / 0.0 // NaN
inspect(nan * 1.0, content="NaN")
* Double
false_positive_rate.(self : Double) -> Double
Calculates the natural logarithm of a double-precision floating-point number.
Parameters:
self: The input number.
Returns the natural logarithm of the input number, with the following special
cases:
- Returns NaN if the input is NaN or negative
- Returns negative infinity if the input is zero
- Returns the input if it is positive infinity
Example:
inspect(2.0.ln(), content="0.6931471805599453")
inspect(1.0.ln(), content="0")
inspect((-1.0).ln(), content="NaN")
inspect(0.0.ln(), content="-Infinity")
ln() (self : Double, other : Double) -> Double
Performs division between two double-precision floating-point numbers.
Follows IEEE 754 standard for floating-point arithmetic, including handling
of special cases like division by zero (returns infinity) and operations
involving NaN.
Parameters:
self : The dividend (numerator) in the division operation.other : The divisor (denominator) in the division operation.
Returns the result of dividing self by other. Special cases follow IEEE
754:
- Division by zero returns positive or negative infinity based on the
dividend's sign
- Operations involving NaN return NaN
- Division of infinity by infinity returns NaN
Example:
inspect(6.0 / 2.0, content="3")
inspect(-6.0 / 2.0, content="-3")
inspect(1.0 / 0.0, content="Infinity")
/ (Double
ln2 (self : Double, other : Double) -> Double
Multiplies two double-precision floating-point numbers. This is the
implementation of the * operator for Double type.
Parameters:
self : The first double-precision floating-point operand.other : The second double-precision floating-point operand.
Returns a new double-precision floating-point number representing the product
of the two operands. Special cases follow IEEE 754 standard:
- If either operand is NaN, returns NaN
- If one operand is infinity and the other is zero, returns NaN
- If one operand is infinity and the other is a non-zero finite number,
returns infinity with the appropriate sign
- If both operands are infinity, returns infinity with the appropriate sign
Example:
inspect(2.5 * 2.0, content="5")
inspect(-2.0 * 3.0, content="-6")
let nan = 0.0 / 0.0 // NaN
inspect(nan * 1.0, content="NaN")
* Double
ln2))
258 .(self : Double) -> Double
Returns the smallest integer greater than or equal to the given number.
Parameters:
self : The floating point number to find the ceiling of.
Returns the ceiling value of the input number.
Example:
inspect(3.7.ceil(), content="4")
inspect((-3.7).ceil(), content="-3")
inspect(42.0.ceil(), content="42")
ceil()
259 .(self : Double) -> Int
Converts a double-precision floating-point number to a 32-bit integer.
Handles special cases including NaN and numbers outside the valid Int range.
Parameters:
self : The double-precision floating-point number to be converted.
Returns an 32-bit integer value according to the following rules:
- Returns 0 if the input is NaN
- Returns
@int.max_value (2147483647) if the input is greater than or
equal to @int.max_value
- Returns
@int.min_value (-2147483648) if the input is less than or equal
to @int.min_value
- Otherwise returns the integer part of the input by truncating towards zero
Example:
inspect(42.0.to_int(), content="42")
inspect((-42.5).to_int(), content="-42")
inspect((0.0 / 0.0).to_int(), content="0") // NaN
inspect((1.0 / 0.0).to_int(), content="2147483647") // Infinity
inspect((-1.0 / 0.0).to_int(), content="-2147483648") // -Infinity
to_int()
260}
261
262///|
263/// 计算最优哈希函数数量
264fn (expected_elements : Int, table_size : Int) -> Int
计算最优哈希函数数量
calculate_optimal_hash_count(
265 Int
expected_elements : Int
Int,
266 Int
table_size : Int
Int
267) -> Int
Int {
268 let Double
ln2 = 0.693147180559945
269 let Int
result = (Int
table_size.(self : Int) -> Double
Converts a 32-bit integer to a double-precision floating-point number. The
conversion preserves the exact value since all integers in the range of Int
can be represented exactly as Double values.
Parameters:
self : The 32-bit integer to be converted.
Returns a double-precision floating-point number that represents the same
numerical value as the input integer.
Example:
let n = 42
inspect(n.to_double(), content="42")
let neg = -42
inspect(neg.to_double(), content="-42")
to_double() (self : Double, other : Double) -> Double
Performs division between two double-precision floating-point numbers.
Follows IEEE 754 standard for floating-point arithmetic, including handling
of special cases like division by zero (returns infinity) and operations
involving NaN.
Parameters:
self : The dividend (numerator) in the division operation.other : The divisor (denominator) in the division operation.
Returns the result of dividing self by other. Special cases follow IEEE
754:
- Division by zero returns positive or negative infinity based on the
dividend's sign
- Operations involving NaN return NaN
- Division of infinity by infinity returns NaN
Example:
inspect(6.0 / 2.0, content="3")
inspect(-6.0 / 2.0, content="-3")
inspect(1.0 / 0.0, content="Infinity")
/ Int
expected_elements.(self : Int) -> Double
Converts a 32-bit integer to a double-precision floating-point number. The
conversion preserves the exact value since all integers in the range of Int
can be represented exactly as Double values.
Parameters:
self : The 32-bit integer to be converted.
Returns a double-precision floating-point number that represents the same
numerical value as the input integer.
Example:
let n = 42
inspect(n.to_double(), content="42")
let neg = -42
inspect(neg.to_double(), content="-42")
to_double() (self : Double, other : Double) -> Double
Multiplies two double-precision floating-point numbers. This is the
implementation of the * operator for Double type.
Parameters:
self : The first double-precision floating-point operand.other : The second double-precision floating-point operand.
Returns a new double-precision floating-point number representing the product
of the two operands. Special cases follow IEEE 754 standard:
- If either operand is NaN, returns NaN
- If one operand is infinity and the other is zero, returns NaN
- If one operand is infinity and the other is a non-zero finite number,
returns infinity with the appropriate sign
- If both operands are infinity, returns infinity with the appropriate sign
Example:
inspect(2.5 * 2.0, content="5")
inspect(-2.0 * 3.0, content="-6")
let nan = 0.0 / 0.0 // NaN
inspect(nan * 1.0, content="NaN")
* Double
ln2)
270 .(self : Double) -> Double
Rounds a floating-point number to the nearest integer using "round half up"
rule. In this rule, when a number is halfway between two integers (like 3.5),
it is rounded up to the next integer.
Parameters:
value : The floating-point number to be rounded.
Returns the rounded value as a double-precision floating-point number.
Example:
inspect(3.7.round(), content="4")
inspect(3.2.round(), content="3")
inspect(3.5.round(), content="4")
inspect((-3.5).round(), content="-3")
round()
271 .(self : Double) -> Int
Converts a double-precision floating-point number to a 32-bit integer.
Handles special cases including NaN and numbers outside the valid Int range.
Parameters:
self : The double-precision floating-point number to be converted.
Returns an 32-bit integer value according to the following rules:
- Returns 0 if the input is NaN
- Returns
@int.max_value (2147483647) if the input is greater than or
equal to @int.max_value
- Returns
@int.min_value (-2147483648) if the input is less than or equal
to @int.min_value
- Otherwise returns the integer part of the input by truncating towards zero
Example:
inspect(42.0.to_int(), content="42")
inspect((-42.5).to_int(), content="-42")
inspect((0.0 / 0.0).to_int(), content="0") // NaN
inspect((1.0 / 0.0).to_int(), content="2147483647") // Infinity
inspect((-1.0 / 0.0).to_int(), content="-2147483648") // -Infinity
to_int()
272 if Int
result (self_ : Int, other : Int) -> Bool
< 1 {
273 1
274 } else {
275 Int
result
276 }
277}
278
279///|
280/// 使用数学公式生成种子
281fn (count : Int) -> Array[Int]
使用数学公式生成种子
generate_seeds(Int
count : Int
Int) -> type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[Int
Int] {
282 let Array[Int]
seeds = []
283 for Int
i = 0; Int
i (self_ : Int, other : Int) -> Bool
< Int
count; Int
i = Int
i (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:
self : The first integer operand.other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
inspect(42 + 1, content="43")
inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ 1 {
284 // 使用简单的数学公式生成种子
285 let Int
seed = (Int
i (self : Int, other : Int) -> Int
Multiplies two 32-bit integers. This is the implementation of the *
operator for Int.
Parameters:
self : The first integer operand.other : The second integer operand.
Returns the product of the two integers. If the result overflows the range of
Int, it wraps around according to two's complement arithmetic.
Example:
inspect(42 * 2, content="84")
inspect(-10 * 3, content="-30")
let max = 2147483647 // Int.max_value
inspect(max * 2, content="-2") // Overflow wraps around
* 31 (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:
self : The first integer operand.other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
inspect(42 + 1, content="43")
inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ 17) (self : Int, other : Int) -> Int
Multiplies two 32-bit integers. This is the implementation of the *
operator for Int.
Parameters:
self : The first integer operand.other : The second integer operand.
Returns the product of the two integers. If the result overflows the range of
Int, it wraps around according to two's complement arithmetic.
Example:
inspect(42 * 2, content="84")
inspect(-10 * 3, content="-30")
let max = 2147483647 // Int.max_value
inspect(max * 2, content="-2") // Overflow wraps around
* 1009 (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:
self : The first integer operand.other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
inspect(42 + 1, content="43")
inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ 7919
286 Array[Int]
seeds.(self : Array[Int], value : Int) -> Unit
Adds an element to the end of the array.
If the array is at capacity, it will be reallocated.
Example
let v = []
v.push(3)
push(Int
seed)
287 }
288 Array[Int]
seeds
289}
290
291///|
292/// 计算多个哈希值
293fn (key : K, seeds : Array[Int], table_size : Int) -> HashResult
计算多个哈希值
compute_hashes[K : trait Hash {
hash_combine(Self, Hasher) -> Unit
hash(Self) -> Int
}
Trait for types that can be hashed
Hash](
294 K
key : type parameter K
K,
295 Array[Int]
seeds : type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[Int
Int],
296 Int
table_size : Int
Int
297) -> struct HashResult {
hashes: Array[Int]
}
哈希函数的结果
HashResult {
298 let Array[Int]
hashes = []
299 for Int
i = 0; Int
i (self_ : Int, other : Int) -> Bool
< Array[Int]
seeds.(self : Array[Int]) -> Int
Returns the number of elements in the array.
Parameters:
array : The array whose length is to be determined.
Returns the number of elements in the array as an integer.
Example:
let arr = [1, 2, 3]
inspect(arr.length(), content="3")
let empty : Array[Int] = []
inspect(empty.length(), content="0")
length(); Int
i = Int
i (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:
self : The first integer operand.other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
inspect(42 + 1, content="43")
inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ 1 {
300 let Int
hash_val = (K
key.(K) -> Int
hash() (Int, Int) -> Int
^ Array[Int]
seeds(Array[Int], Int) -> Int
Retrieves an element from the array at the specified index.
Parameters:
array : The array to get the element from.index : The position in the array from which to retrieve the element.
Returns the element at the specified index.
Throws a panic if the index is negative or greater than or equal to the
length of the array.
Example:
let arr = [1, 2, 3]
inspect(arr[1], content="2")
[i]).(self : Int) -> Int
Computes the absolute value of an integer.
Parameters:
self : The integer whose absolute value is to be computed.
Returns the absolute value of the integer.
Example:
inspect(@int.abs(42), content="42")
inspect(@int.abs(-42), content="42")
inspect(@int.abs(0), content="0")
abs() (self : Int, other : Int) -> Int
Calculates the remainder of dividing one integer by another. The result
follows the formula dividend - (dividend / divisor) * divisor, maintaining
the same sign as the dividend.
Parameters:
self : The dividend (the number being divided).other : The divisor (the number to divide by).
Returns the remainder of the division. If other is 0, the behavior is
undefined.
Example:
inspect(7 % 3, content="1")
inspect(-7 % 3, content="-1")
inspect(7 % -3, content="1")
% Int
table_size
301 Array[Int]
hashes.(self : Array[Int], value : Int) -> Unit
Adds an element to the end of the array.
If the array is at capacity, it will be reallocated.
Example
let v = []
v.push(3)
push(Int
hash_val)
302 }
303 { Array[Int]
hashes, }
304}
305
306///|
307/// 构建过滤器
308fn (filter : BloomierFilter[K, V], items : Array[(K, V)]) -> Unit
构建过滤器
build_filter[K : trait Hash {
hash_combine(Self, Hasher) -> Unit
hash(Self) -> Int
}
Trait for types that can be hashed
Hash + trait Eq {
op_equal(Self, Self) -> Bool
}
Trait for types whose elements can test for equality
Eq, V](
309 BloomierFilter[K, V]
filter : struct BloomierFilter[K, V] {
mut table: Array[V?]
mut table_size: Int
hash_count: Int
mut seeds: Array[Int]
mut size: Int
}
Bloomier Filter 数据结构
支持存储键值对并进行快速查询
BloomierFilter[type parameter K
K, type parameter V
V],
310 Array[(K, V)]
items : type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[(type parameter K
K, type parameter V
V)]
311) -> Unit
Unit {
312 let Int
max_attempts = 10
313 for Int
attempt = 0; Int
attempt (self_ : Int, other : Int) -> Bool
< Int
max_attempts; Int
attempt = Int
attempt (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:
self : The first integer operand.other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
inspect(42 + 1, content="43")
inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ 1 {
314 BloomierFilter[K, V]
filter.(self : BloomierFilter[K, V]) -> Unit
清空过滤器
Example
filter.clear()
assert_eq!(filter.size(), 0)
clear()
315 let mut Bool
success = true
316 for (K, V)
item in Array[(K, V)]
items {
317 let (K
key, V
value) = (K, V)
item
318 match BloomierFilter[K, V]
filter.(self : BloomierFilter[K, V], key : K, value : V) -> InsertResult
插入键值对
Example
match filter.insert("key", "value") {
Success => println("插入成功")
Failure => println("插入失败")
NeedRehash => println("需要重新哈希")
}
insert(K
key, V
value) {
319 InsertResult::InsertResult
成功插入
Success => continue
320 _ => {
321 Bool
success = false
322 break
323 }
324 }
325 }
326 if Bool
success {
327 return
328 }
329
330 // 重新生成种子
331 BloomierFilter[K, V]
filter.Array[Int]
用于哈希计算的种子数组
seeds = (count : Int) -> Array[Int]
使用数学公式生成种子
generate_seeds(BloomierFilter[K, V]
filter.Int
哈希函数的数量
hash_count)
332 }
333 (msg : String) -> Unit
Aborts the program with an error message. Always causes a panic, regardless
of the message provided.
Parameters:
message : A string containing the error message to be displayed when
aborting.
Returns a value of type T. However, this function never actually returns a
value as it always causes a panic.
abort("Failed to build filter after maximum attempts")
334}
335
336///|
337/// 统计非空槽位数量
338fn (table : Array[V?]) -> Int
统计非空槽位数量
count_non_empty_slots[V](Array[V?]
table : type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[type parameter V
V?]) -> Int
Int {
339 let mut Int
count = 0
340 for V?
item in Array[V?]
table {
341 match V?
item {
342 V?
Some(_) => Int
count (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:
self : The first integer operand.other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
inspect(42 + 1, content="43")
inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+= 1
343 V?
None => continue
344 }
345 }
346 Int
count
347}
348
349///|
350/// 批量插入
351pub fn (self : BloomierFilter[K, V], items : Array[(K, V)]) -> Array[InsertResult]
批量插入
insert_all[K : trait Hash {
hash_combine(Self, Hasher) -> Unit
hash(Self) -> Int
}
Trait for types that can be hashed
Hash + trait Eq {
op_equal(Self, Self) -> Bool
}
Trait for types whose elements can test for equality
Eq, V](
352 BloomierFilter[K, V]
self : struct BloomierFilter[K, V] {
mut table: Array[V?]
mut table_size: Int
hash_count: Int
mut seeds: Array[Int]
mut size: Int
}
Bloomier Filter 数据结构
支持存储键值对并进行快速查询
BloomierFilter[type parameter K
K, type parameter V
V],
353 Array[(K, V)]
items : type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[(type parameter K
K, type parameter V
V)]
354) -> type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[enum InsertResult {
Success
Failure
NeedRehash
}
插入操作的结果
InsertResult] {
355 let Array[InsertResult]
results = []
356 for (K, V)
item in Array[(K, V)]
items {
357 let (K
key, V
value) = (K, V)
item
358 Array[InsertResult]
results.(self : Array[InsertResult], value : InsertResult) -> Unit
Adds an element to the end of the array.
If the array is at capacity, it will be reallocated.
Example
let v = []
v.push(3)
push(BloomierFilter[K, V]
self.(self : BloomierFilter[K, V], key : K, value : V) -> InsertResult
插入键值对
Example
match filter.insert("key", "value") {
Success => println("插入成功")
Failure => println("插入失败")
NeedRehash => println("需要重新哈希")
}
insert(K
key, V
value))
359 }
360 Array[InsertResult]
results
361}
362
363///|
364/// 批量查询
365pub fn (self : BloomierFilter[K, V], keys : Array[K]) -> Array[QueryResult[V]]
批量查询
get_all[K : trait Hash {
hash_combine(Self, Hasher) -> Unit
hash(Self) -> Int
}
Trait for types that can be hashed
Hash + trait Eq {
op_equal(Self, Self) -> Bool
}
Trait for types whose elements can test for equality
Eq, V](
366 BloomierFilter[K, V]
self : struct BloomierFilter[K, V] {
mut table: Array[V?]
mut table_size: Int
hash_count: Int
mut seeds: Array[Int]
mut size: Int
}
Bloomier Filter 数据结构
支持存储键值对并进行快速查询
BloomierFilter[type parameter K
K, type parameter V
V],
367 Array[K]
keys : type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[type parameter K
K]
368) -> type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[enum QueryResult[V] {
Found(V)
NotFound
Uncertain
}
查询操作的结果
QueryResult[type parameter V
V]] {
369 let Array[QueryResult[V]]
results = []
370 for K
key in Array[K]
keys {
371 Array[QueryResult[V]]
results.(self : Array[QueryResult[V]], value : QueryResult[V]) -> Unit
Adds an element to the end of the array.
If the array is at capacity, it will be reallocated.
Example
let v = []
v.push(3)
push(BloomierFilter[K, V]
self.(self : BloomierFilter[K, V], key : K) -> QueryResult[V]
查询键对应的值
Example
match filter.get("key") {
Found(value) => println("找到值: \{value}")
NotFound => println("未找到")
Uncertain => println("可能存在")
}
get(K
key))
372 }
373 Array[QueryResult[V]]
results
374}
375
376///|
377/// 获取所有可能的值
378pub fn (self : BloomierFilter[K, V], key : K) -> Array[V]
获取所有可能的值
get_all_values[K : trait Hash {
hash_combine(Self, Hasher) -> Unit
hash(Self) -> Int
}
Trait for types that can be hashed
Hash + trait Eq {
op_equal(Self, Self) -> Bool
}
Trait for types whose elements can test for equality
Eq, V](
379 BloomierFilter[K, V]
self : struct BloomierFilter[K, V] {
mut table: Array[V?]
mut table_size: Int
hash_count: Int
mut seeds: Array[Int]
mut size: Int
}
Bloomier Filter 数据结构
支持存储键值对并进行快速查询
BloomierFilter[type parameter K
K, type parameter V
V],
380 K
key : type parameter K
K
381) -> type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[type parameter V
V] {
382 let HashResult
hashes = (key : K, seeds : Array[Int], table_size : Int) -> HashResult
计算多个哈希值
compute_hashes(K
key, BloomierFilter[K, V]
self.Array[Int]
用于哈希计算的种子数组
seeds, BloomierFilter[K, V]
self.Int
表的大小
table_size)
383 let Array[V]
values = []
384 for Int
i = 0; Int
i (self_ : Int, other : Int) -> Bool
< HashResult
hashes.Array[Int]
哈希值数组
hashes.(self : Array[Int]) -> Int
Returns the number of elements in the array.
Parameters:
array : The array whose length is to be determined.
Returns the number of elements in the array as an integer.
Example:
let arr = [1, 2, 3]
inspect(arr.length(), content="3")
let empty : Array[Int] = []
inspect(empty.length(), content="0")
length(); Int
i = Int
i (self : Int, other : Int) -> Int
Adds two 32-bit signed integers. Performs two's complement arithmetic, which
means the operation will wrap around if the result exceeds the range of a
32-bit integer.
Parameters:
self : The first integer operand.other : The second integer operand.
Returns a new integer that is the sum of the two operands. If the
mathematical sum exceeds the range of a 32-bit integer (-2,147,483,648 to
2,147,483,647), the result wraps around according to two's complement rules.
Example:
inspect(42 + 1, content="43")
inspect(2147483647 + 1, content="-2147483648") // Overflow wraps around to minimum value
+ 1 {
385 let Int
index = HashResult
hashes.Array[Int]
哈希值数组
hashes(Array[Int], Int) -> Int
Retrieves an element from the array at the specified index.
Parameters:
array : The array to get the element from.index : The position in the array from which to retrieve the element.
Returns the element at the specified index.
Throws a panic if the index is negative or greater than or equal to the
length of the array.
Example:
let arr = [1, 2, 3]
inspect(arr[1], content="2")
[i]
386 match BloomierFilter[K, V]
self.Array[V?]
哈希表数组，存储实际的值
table(Array[V?], Int) -> V?
Retrieves an element from the array at the specified index.
Parameters:
array : The array to get the element from.index : The position in the array from which to retrieve the element.
Returns the element at the specified index.
Throws a panic if the index is negative or greater than or equal to the
length of the array.
Example:
let arr = [1, 2, 3]
inspect(arr[1], content="2")
[index] {
387 (V) -> V?
Some(V
value) => Array[V]
values.(self : Array[V], value : V) -> Unit
Adds an element to the end of the array.
If the array is at capacity, it will be reallocated.
Example
let v = []
v.push(3)
push(V
value)
388 V?
None => continue
389 }
390 }
391 Array[V]
values
392}
393
394///|
395/// 获取负载因子
396pub fn (self : BloomierFilter[K, V]) -> Double
获取负载因子
load_factor[K, V](BloomierFilter[K, V]
self : struct BloomierFilter[K, V] {
mut table: Array[V?]
mut table_size: Int
hash_count: Int
mut seeds: Array[Int]
mut size: Int
}
Bloomier Filter 数据结构
支持存储键值对并进行快速查询
BloomierFilter[type parameter K
K, type parameter V
V]) -> Double
Double {
397 BloomierFilter[K, V]
self.Int
当前存储的元素数量
size.(self : Int) -> Double
Converts a 32-bit integer to a double-precision floating-point number. The
conversion preserves the exact value since all integers in the range of Int
can be represented exactly as Double values.
Parameters:
self : The 32-bit integer to be converted.
Returns a double-precision floating-point number that represents the same
numerical value as the input integer.
Example:
let n = 42
inspect(n.to_double(), content="42")
let neg = -42
inspect(neg.to_double(), content="-42")
to_double() (self : Double, other : Double) -> Double
Performs division between two double-precision floating-point numbers.
Follows IEEE 754 standard for floating-point arithmetic, including handling
of special cases like division by zero (returns infinity) and operations
involving NaN.
Parameters:
self : The dividend (numerator) in the division operation.other : The divisor (denominator) in the division operation.
Returns the result of dividing self by other. Special cases follow IEEE
754:
- Division by zero returns positive or negative infinity based on the
dividend's sign
- Operations involving NaN return NaN
- Division of infinity by infinity returns NaN
Example:
inspect(6.0 / 2.0, content="3")
inspect(-6.0 / 2.0, content="-3")
inspect(1.0 / 0.0, content="Infinity")
/ BloomierFilter[K, V]
self.Int
表的大小
table_size.(self : Int) -> Double
Converts a 32-bit integer to a double-precision floating-point number. The
conversion preserves the exact value since all integers in the range of Int
can be represented exactly as Double values.
Parameters:
self : The 32-bit integer to be converted.
Returns a double-precision floating-point number that represents the same
numerical value as the input integer.
Example:
let n = 42
inspect(n.to_double(), content="42")
let neg = -42
inspect(neg.to_double(), content="-42")
to_double()
398}
399
400///|
401/// 检查是否需要扩容
402pub fn (self : BloomierFilter[K, V], threshold : Double) -> Bool
检查是否需要扩容
needs_resize[K, V](
403 BloomierFilter[K, V]
self : struct BloomierFilter[K, V] {
mut table: Array[V?]
mut table_size: Int
hash_count: Int
mut seeds: Array[Int]
mut size: Int
}
Bloomier Filter 数据结构
支持存储键值对并进行快速查询
BloomierFilter[type parameter K
K, type parameter V
V],
404 Double
threshold : Double
Double
405) -> Bool
Bool {
406 BloomierFilter[K, V]
self.(self : BloomierFilter[K, V]) -> Double
获取负载因子
load_factor() (self_ : Double, other : Double) -> Bool
> Double
threshold
407}
408
409///|
410/// 带外部数据的重哈希
411pub fn (self : BloomierFilter[K, V], items : Array[(K, V)]) -> Unit
带外部数据的重哈希
rehash_with_items[K : trait Hash {
hash_combine(Self, Hasher) -> Unit
hash(Self) -> Int
}
Trait for types that can be hashed
Hash + trait Eq {
op_equal(Self, Self) -> Bool
}
Trait for types whose elements can test for equality
Eq, V](
412 BloomierFilter[K, V]
self : struct BloomierFilter[K, V] {
mut table: Array[V?]
mut table_size: Int
hash_count: Int
mut seeds: Array[Int]
mut size: Int
}
Bloomier Filter 数据结构
支持存储键值对并进行快速查询
BloomierFilter[type parameter K
K, type parameter V
V],
413 Array[(K, V)]
items : type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[(type parameter K
K, type parameter V
V)]
414) -> Unit
Unit {
415 (filter : BloomierFilter[K, V], items : Array[(K, V)]) -> Unit
构建过滤器
build_filter(BloomierFilter[K, V]
self, Array[(K, V)]
items)
416}
417
418///|
419/// 动态调整表大小
420pub fn (self : BloomierFilter[K, V], new_size : Int, items : Array[(K, V)]) -> Unit
动态调整表大小
resize[K : trait Hash {
hash_combine(Self, Hasher) -> Unit
hash(Self) -> Int
}
Trait for types that can be hashed
Hash + trait Eq {
op_equal(Self, Self) -> Bool
}
Trait for types whose elements can test for equality
Eq, V](
421 BloomierFilter[K, V]
self : struct BloomierFilter[K, V] {
mut table: Array[V?]
mut table_size: Int
hash_count: Int
mut seeds: Array[Int]
mut size: Int
}
Bloomier Filter 数据结构
支持存储键值对并进行快速查询
BloomierFilter[type parameter K
K, type parameter V
V],
422 Int
new_size : Int
Int,
423 Array[(K, V)]
items : type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[(type parameter K
K, type parameter V
V)]
424) -> Unit
Unit {
425 if Int
new_size (self_ : Int, other : Int) -> Bool
<= 0 {
426 (msg : String) -> Unit
Aborts the program with an error message. Always causes a panic, regardless
of the message provided.
Parameters:
message : A string containing the error message to be displayed when
aborting.
Returns a value of type T. However, this function never actually returns a
value as it always causes a panic.
abort("Invalid table size")
427 }
428 BloomierFilter[K, V]
self.Int
表的大小
table_size = Int
new_size
429 BloomierFilter[K, V]
self.Array[V?]
哈希表数组，存储实际的值
table = type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array::(Int, V?) -> Array[V?]
Creates a new array with a specified length and initializes all elements with
the given value.
Parameters:
length : The length of the array to create. Must be a non-negative
integer.initial_value : The value used to initialize all elements in the array.
Returns a new array of type Array[T] with length elements, where each
element is initialized to initial_value.
Throws an error if length is negative.
Example:
let arr = Array::make(3, 42)
inspect(arr, content="[42, 42, 42]")
WARNING: A common pitfall is creating with the same initial value, for example:
let two_dimension_array = Array::make(10, Array::make(10, 0))
two_dimension_array[0][5] = 10
assert_eq(two_dimension_array[5][5], 10)
This is because all the cells reference to the same object (the Array[Int] in this case).
One should use makei() instead which creates an object for each index.
make(Int
new_size, V?
None)
430 BloomierFilter[K, V]
self.Int
当前存储的元素数量
size = 0
431 (filter : BloomierFilter[K, V], items : Array[(K, V)]) -> Unit
构建过滤器
build_filter(BloomierFilter[K, V]
self, Array[(K, V)]
items)
432}
433
434///|
435/// 迭代所有非空值
436pub fn (self : BloomierFilter[K, V], f : (V) -> Unit) -> Unit
迭代所有非空值
iter_values[K, V](BloomierFilter[K, V]
self : struct BloomierFilter[K, V] {
mut table: Array[V?]
mut table_size: Int
hash_count: Int
mut seeds: Array[Int]
mut size: Int
}
Bloomier Filter 数据结构
支持存储键值对并进行快速查询
BloomierFilter[type parameter K
K, type parameter V
V], (V) -> Unit
f : (type parameter V
V) -> Unit
Unit) -> Unit
Unit {
437 for V?
item in BloomierFilter[K, V]
self.Array[V?]
哈希表数组，存储实际的值
table {
438 match V?
item {
439 (V) -> V?
Some(V
value) => (V) -> Unit
f(V
value)
440 V?
None => continue
441 }
442 }
443}
444
445///|
446/// 收集所有值到数组
447pub fn (self : BloomierFilter[K, V]) -> Array[V]
收集所有值到数组
values[K, V](BloomierFilter[K, V]
self : struct BloomierFilter[K, V] {
mut table: Array[V?]
mut table_size: Int
hash_count: Int
mut seeds: Array[Int]
mut size: Int
}
Bloomier Filter 数据结构
支持存储键值对并进行快速查询
BloomierFilter[type parameter K
K, type parameter V
V]) -> type Array[T]
An Array is a collection of values that supports random access and can
grow in size.
Array[type parameter V
V] {
448 let Array[V]
result = []
449 BloomierFilter[K, V]
self.(self : BloomierFilter[K, V], f : (V) -> Unit) -> Unit
迭代所有非空值
iter_values(fn(V
value) { Array[V]
result.(self : Array[V], value : V) -> Unit
Adds an element to the end of the array.
If the array is at capacity, it will be reallocated.
Example
let v = []
v.push(3)
push(V
value) })
450 Array[V]
result
451}
452