dsa_rust/associative/
hash_lib.rs

1/*! Hashing & compression functions
2
3The utility functions in this module can be used to implement various hashing and compression algorithms
4
5*/
6
7// HOME-ROLLED HASHING
8//////////////////////
9
10/** Illustrates the concept of bit shifting;
11Takes a string a prints the bit and integer value of each character before
12performing a bit shift operation and printing the result as bit and integer values */
13pub fn visual_bit_shift(value: &str) {
14    for mut v in value.bytes() {
15        print!("{v:08b} ({v}) -> ");
16        //v = (v << 5) | (v >> 3);
17        // clippy wants a function
18        v = v.rotate_right(3);
19        println!("{v:08b} ({v})");
20    }
21}
22
23/** Calculates a bit-shifted hash code;
24The function initializes a 32-bit hash code integer to 0,
25then loops over each character in the input string;
26Each loop adds the next character in the string to the hash code
27as an integer value with wrapping; This ensures consistency
28across architectures; The next operation in each loop performs
29a cyclic bit shift on the hash code, and the process repeats */
30pub fn visual_hash_code(key: &str) -> u32 {
31    let mut hash: u32 = 0;
32    for word in key.bytes() {
33        print!("{word:08b} -> ");
34        hash = hash.wrapping_add(word as u32);
35        //hash = (hash << 5) | (hash >> 27);
36        // clippy wants a function
37        hash = hash.rotate_left(5);
38        println!("{hash:032b}");
39    }
40    hash
41}
42#[test]
43fn hash_code_test() {
44    let v = visual_hash_code("Peter");
45    assert_eq!(v, 2794168896);
46
47    //let v = visual_hash_code("This block overflows the value");
48    //assert_eq!(v, 3862340559);
49}
50
51// STANDARD LIBRARY HASHING
52///////////////////////////
53
54// Explores Rust's default hashing functionality
55use std::collections::hash_map::DefaultHasher;
56use std::fmt::Debug;
57use std::hash::{Hash, Hasher};
58
59/// Takes a reference to a type `T` and uses Rust's default hasher to return a
60/// 64-bit digest.
61pub fn hash<T: Hash + Debug + ?Sized>(key: &T) -> usize {
62    let mut hasher = DefaultHasher::new();
63    key.hash(&mut hasher); // Hash::hash()
64    let digest = hasher.finish(); // Hasher::finish()
65    digest as usize
66}
67
68/** Does the same thing as hash() but feeds individual bytes which produces a
69slightly less efficient (and different) digest */
70pub fn hash_1(key: &str) -> u64 {
71    let mut hasher = DefaultHasher::new();
72    for e in key.bytes() {
73        hasher.write_u8(e)
74    }
75    hasher.finish()
76}
77
78// COMPRESSION
79//////////////
80
81/// Super simple division compression as `i mod N`.
82/// Produces a deterministic output, works best when `n` (len) is prime.
83pub fn division_compression(key: usize, len: usize) -> usize {
84    key % len
85}
86
87/// Efficient primality test using the 6k ± 1 rule for numbers >3 by trial.
88fn is_prime(n: usize) -> bool {
89    // Only positive numbers >1 need apply
90    if n < 2 {
91        return false;
92    }
93    // The lil guys get some love
94    if n == 2 || n == 3 {
95        return true;
96    }
97    // Skips evens and numbers divisible by 3
98    if n % 2 == 0 || n % 3 == 0 {
99        return false;
100    }
101    // 6k ± 1 rule check
102    let mut i = 5;
103    while i * i <= n {
104        if n % i == 0 || n % (i + 2) == 0 {
105            return false;
106        }
107        i += 6;
108    }
109    true
110}
111#[test]
112fn prime_test() {
113    // Prime
114    assert!(is_prime(7));
115    assert!(is_prime(23));
116    assert!(is_prime(1103));
117    assert!(is_prime(50411));
118    assert!(is_prime(120569));
119    // Not prime
120    assert!(!is_prime(21));
121    assert!(!is_prime(39));
122    assert!(!is_prime(98));
123    assert!(!is_prime(1208));
124    assert!(!is_prime(445));
125}
126
127/** Finds the next prime by brute force in O(n) time */
128//fn next_prime(n: u64) -> u64 {
129//    let mut candidate = n + 1;
130//    while !is_prime(candidate) {e
131//        candidate += 1;
132//    }
133//    candidate
134//}
135/** Finds the next prime in O(n/2) time by skipping evens */
136pub fn next_prime(n: usize) -> usize {
137    if n < 2 {
138        return 2;
139    }
140    if n == 2 {
141        return 3;
142    }
143    let mut candidate = if n % 2 == 0 { n + 1 } else { n + 2 }; // Ensure candidate is odd
144    while !is_prime(candidate) {
145        candidate += 2; // Skip even numbers
146    }
147    candidate
148}
149#[test]
150fn next_prime_test() {
151    assert_eq!(next_prime(3), 5);
152    assert_eq!(next_prime(19), 23);
153    assert_eq!(next_prime(8868), 8887);
154    assert_eq!(next_prime(117760), 117763);
155    assert_eq!(next_prime(1899498), 1899503);
156}
157
158use rand::Rng;
159
160/** Implements MAD compression as `[(ai + b) mod p] mod N`
161Relies on `is_prime` and `next_prime` functions */
162// `c(h(k)) = ((a * h(k) + b) mod p) mod N`
163pub fn mad_compression(key: usize, len: usize) -> usize {
164    // Finds a prime >len, starting much larger to ensure even spread
165    let p = next_prime(len.pow(3));
166
167    let mut rng = rand::rng(); // Thread-local RNG
168    let a = rng.random_range(1..=p - 1);
169    let b = rng.random_range(0..=p - 1);
170
171    // Raw-dogging the algorithm may cause overflow
172    //(((key * a) + b) % p) % len
173
174    // Apply wrapping * and + to prevent overflow
175    (key.wrapping_mul(a))
176        .wrapping_add(b)
177        .wrapping_rem(p)
178        .wrapping_rem(len)
179}
180pub fn mad_compression_1(
181    hash: usize,
182    prime: usize,
183    scale: usize,
184    shift: usize,
185    capacity: usize,
186) -> usize {
187    (hash.wrapping_mul(scale)).wrapping_add(shift) % (prime) % (capacity)
188}
dsa_rust/associative/hash_lib.rs

dsa_rust/associative/
hash_lib.rs
