oxihuman_core/
compact_hash.rs

1// Copyright (C) 2026 COOLJAPAN OU (Team KitaSan)
2// SPDX-License-Identifier: Apache-2.0
3#![allow(dead_code)]
4
5/// A compact hash map using open addressing with linear probing.
6/// Stores `u64` keys and `u64` values in parallel arrays.
7#[allow(dead_code)]
8#[derive(Debug, Clone)]
9pub struct CompactHash {
10    keys: Vec<u64>,
11    values: Vec<u64>,
12    occupied: Vec<bool>,
13    count: usize,
14}
15
16const EMPTY_KEY: u64 = u64::MAX;
17
18#[allow(dead_code)]
19impl CompactHash {
20    pub fn new(capacity: usize) -> Self {
21        let cap = capacity.max(8).next_power_of_two();
22        Self {
23            keys: vec![EMPTY_KEY; cap],
24            values: vec![0; cap],
25            occupied: vec![false; cap],
26            count: 0,
27        }
28    }
29
30    fn hash_index(&self, key: u64) -> usize {
31        let h = key.wrapping_mul(0x9E37_79B9_7F4A_7C15);
32        (h as usize) & (self.keys.len() - 1)
33    }
34
35    pub fn insert(&mut self, key: u64, value: u64) -> bool {
36        if self.count * 4 >= self.keys.len() * 3 {
37            self.grow();
38        }
39        let mask = self.keys.len() - 1;
40        let mut idx = self.hash_index(key);
41        loop {
42            if !self.occupied[idx] {
43                self.keys[idx] = key;
44                self.values[idx] = value;
45                self.occupied[idx] = true;
46                self.count += 1;
47                return true;
48            }
49            if self.keys[idx] == key {
50                self.values[idx] = value;
51                return false;
52            }
53            idx = (idx + 1) & mask;
54        }
55    }
56
57    pub fn get(&self, key: u64) -> Option<u64> {
58        let mask = self.keys.len() - 1;
59        let mut idx = self.hash_index(key);
60        for _ in 0..self.keys.len() {
61            if !self.occupied[idx] {
62                return None;
63            }
64            if self.keys[idx] == key {
65                return Some(self.values[idx]);
66            }
67            idx = (idx + 1) & mask;
68        }
69        None
70    }
71
72    pub fn contains(&self, key: u64) -> bool {
73        self.get(key).is_some()
74    }
75
76    pub fn count(&self) -> usize {
77        self.count
78    }
79
80    pub fn capacity(&self) -> usize {
81        self.keys.len()
82    }
83
84    pub fn load_factor(&self) -> f64 {
85        self.count as f64 / self.keys.len() as f64
86    }
87
88    fn grow(&mut self) {
89        let old_keys = std::mem::take(&mut self.keys);
90        let old_values = std::mem::take(&mut self.values);
91        let old_occupied = std::mem::take(&mut self.occupied);
92        let new_cap = old_keys.len() * 2;
93        self.keys = vec![EMPTY_KEY; new_cap];
94        self.values = vec![0; new_cap];
95        self.occupied = vec![false; new_cap];
96        self.count = 0;
97        #[allow(clippy::needless_range_loop)]
98        for i in 0..old_keys.len() {
99            if old_occupied[i] {
100                self.insert(old_keys[i], old_values[i]);
101            }
102        }
103    }
104
105    pub fn clear(&mut self) {
106        self.keys.fill(EMPTY_KEY);
107        self.values.fill(0);
108        self.occupied.fill(false);
109        self.count = 0;
110    }
111
112    pub fn is_empty(&self) -> bool {
113        self.count == 0
114    }
115
116    pub fn keys(&self) -> Vec<u64> {
117        self.keys
118            .iter()
119            .zip(self.occupied.iter())
120            .filter(|(_, &occ)| occ)
121            .map(|(&k, _)| k)
122            .collect()
123    }
124}
125
126#[cfg(test)]
127mod tests {
128    use super::*;
129
130    #[test]
131    fn test_new() {
132        let ch = CompactHash::new(16);
133        assert!(ch.is_empty());
134        assert_eq!(ch.capacity(), 16);
135    }
136
137    #[test]
138    fn test_insert_and_get() {
139        let mut ch = CompactHash::new(16);
140        assert!(ch.insert(42, 100));
141        assert_eq!(ch.get(42), Some(100));
142    }
143
144    #[test]
145    fn test_update_existing() {
146        let mut ch = CompactHash::new(16);
147        ch.insert(1, 10);
148        assert!(!ch.insert(1, 20));
149        assert_eq!(ch.get(1), Some(20));
150        assert_eq!(ch.count(), 1);
151    }
152
153    #[test]
154    fn test_contains() {
155        let mut ch = CompactHash::new(16);
156        ch.insert(5, 50);
157        assert!(ch.contains(5));
158        assert!(!ch.contains(6));
159    }
160
161    #[test]
162    fn test_grow() {
163        let mut ch = CompactHash::new(8);
164        for i in 0..20 {
165            ch.insert(i, i * 10);
166        }
167        assert_eq!(ch.count(), 20);
168        for i in 0..20 {
169            assert_eq!(ch.get(i), Some(i * 10));
170        }
171    }
172
173    #[test]
174    fn test_clear() {
175        let mut ch = CompactHash::new(16);
176        ch.insert(1, 2);
177        ch.clear();
178        assert!(ch.is_empty());
179        assert!(ch.get(1).is_none());
180    }
181
182    #[test]
183    fn test_load_factor() {
184        let mut ch = CompactHash::new(8);
185        ch.insert(1, 1);
186        ch.insert(2, 2);
187        let lf = ch.load_factor();
188        assert!(lf > 0.0 && lf < 1.0);
189    }
190
191    #[test]
192    fn test_keys() {
193        let mut ch = CompactHash::new(16);
194        ch.insert(10, 1);
195        ch.insert(20, 2);
196        let mut keys = ch.keys();
197        keys.sort();
198        assert_eq!(keys, vec![10, 20]);
199    }
200
201    #[test]
202    fn test_missing_key() {
203        let ch = CompactHash::new(16);
204        assert!(ch.get(999).is_none());
205    }
206
207    #[test]
208    fn test_count() {
209        let mut ch = CompactHash::new(16);
210        ch.insert(1, 1);
211        ch.insert(2, 2);
212        ch.insert(3, 3);
213        assert_eq!(ch.count(), 3);
214    }
215}
oxihuman_core/compact_hash.rs

oxihuman_core/
compact_hash.rs
