1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
use crate::fast_hash_trait::FastHash;
/// A hash function implementation using the Fibonacci hashing technique.
///
/// Fibonacci hashing is a multiplication-based hashing method that uses the golden ratio
/// to achieve a good distribution of hash values. It works particularly well for integer keys
/// and provides good performance characteristics due to its simplicity.
///
/// # Examples
///
/// Basic usage:
/// ```
/// use toolbox_rs::fibonacci_hash::FibonacciHash;
/// use toolbox_rs::fast_hash_trait::FastHash;
///
/// let hasher = FibonacciHash::new();
/// let hash = hasher.hash(42);
/// assert!(hash <= u16::MAX);
/// ```
///
/// Different inputs produce different hashes:
/// ```
/// use toolbox_rs::fibonacci_hash::FibonacciHash;
/// use toolbox_rs::fast_hash_trait::FastHash;
///
/// let hasher = FibonacciHash::new();
/// let hash1 = hasher.hash(1);
/// let hash2 = hasher.hash(2);
/// assert_ne!(hash1, hash2);
/// ```
#[derive(Default)]
pub struct FibonacciHash;
impl FibonacciHash {
/// Creates a new FibonacciHash instance with the specified shift amount.
///
/// The shift amount determines how many bits to shift during the hashing process.
/// A typical value is 16, which produces good distribution for most use cases.
///
/// # Examples
///
/// ```
/// use toolbox_rs::fibonacci_hash::FibonacciHash;
///
/// let hasher = FibonacciHash::new();
/// ```
pub fn new() -> Self {
Self {}
}
}
impl FastHash for FibonacciHash {
/// Computes a 16-bit hash value for a 32-bit input using Fibonacci hashing.
///
/// # Algorithm
///
/// 1. XORs the input with a shifted version of itself
/// 2. Multiplies by the golden ratio constant (≈ (√5-1)/2 * 2⁶⁴)
/// 3. Shifts the result right to get the final hash
///
/// # Arguments
///
/// * `key` - 32-bit unsigned integer to hash
///
/// # Returns
///
/// A 16-bit hash value
///
/// # Examples
///
/// ```
/// use toolbox_rs::fibonacci_hash::FibonacciHash;
/// use toolbox_rs::fast_hash_trait::FastHash;
///
/// let hasher = FibonacciHash::new();
///
/// // Same input produces same hash
/// assert_eq!(hasher.hash(42), hasher.hash(42));
///
/// // Values are within u16 range
/// for i in 0..10 {
/// assert!(hasher.hash(i) <= u16::MAX);
/// }
/// ```
fn hash(&self, key: u32) -> u16 {
// First XOR the high bits with the low bits
let mut hash = key as u64;
hash ^= hash >> 16;
// Multiply by the golden ratio constant (approximately (√5-1)/2 * 2⁶⁴)
const GOLDEN_RATIO: u64 = 11400714819323198485;
let result = (GOLDEN_RATIO.wrapping_mul(hash)) >> 16;
result as u16
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_fibonacci_hash_deterministic() {
let hasher = FibonacciHash::new();
let hash1 = hasher.hash(42);
let hash2 = hasher.hash(42);
assert_eq!(hash1, hash2, "Same input should produce same hash");
}
#[test]
fn test_different_inputs() {
let hasher = FibonacciHash::new();
let hash1 = hasher.hash(1);
let hash2 = hasher.hash(2);
assert_ne!(
hash1, hash2,
"Different inputs should produce different hashes"
);
}
#[test]
fn test_hash_distribution() {
let hasher = FibonacciHash::new();
let mut seen = std::collections::HashSet::new();
// Test distribution over a reasonable range
for i in 0..1000 {
seen.insert(hasher.hash(i));
}
// We expect a good hash function to have reasonable distribution
// For 1000 inputs hashed to u16, we expect a decent number of unique values
assert!(
seen.len() > 900,
"Hash function should provide good distribution"
);
}
}