Skip to content

Instantly share code, notes, and snippets.

@edg-l
Created July 10, 2023 12:40
Show Gist options
  • Save edg-l/7842a445367bfdf2a89ad8c5f70348d4 to your computer and use it in GitHub Desktop.
Save edg-l/7842a445367bfdf2a89ad8c5f70348d4 to your computer and use it in GitHub Desktop.
#![deny(clippy::all)]
#![deny(clippy::nursery)]
#![allow(clippy::cast_possible_truncation)]
use std::{
collections::hash_map::RandomState,
hash::{BuildHasher, Hash, Hasher},
};
#[derive(Debug, Clone)]
pub struct MyHashmap<K, V, S = RandomState> {
// Our storage
storage: Vec<Option<(K, V)>>,
// Save the length for quick querying
len: usize,
// The hasher.
state: S,
// Wehther to use quadratic or linear probing.
quadratic: bool,
}
impl<K, V, S> MyHashmap<K, V, S> {
pub fn new(hasher: S, quadratic: bool) -> Self {
Self {
storage: (0..8).map(|_| None).collect(),
len: 0,
state: hasher,
quadratic,
}
}
pub const fn len(&self) -> usize {
self.len
}
pub const fn is_empty(&self) -> bool {
self.len == 0
}
pub const fn is_quadratic(&self) -> bool {
self.quadratic
}
fn should_resize(&self) -> bool {
(self.len as f64 / self.storage.len() as f64) > 0.7
}
}
impl<K, V, S> MyHashmap<K, V, S>
where
K: Eq + Hash,
S: BuildHasher,
{
// Should be called with a sensible load factor.
fn find_slot_linear(&self, key: &K) -> &Option<(K, V)> {
let mut hasher = self.state.build_hasher();
key.hash(&mut hasher);
let start_idx = hasher.finish() as usize;
let mut iter_idx = 0;
let len = self.storage.len();
let slot_idx = loop {
let idx_mod: usize = (start_idx + iter_idx) % len;
match &self.storage[idx_mod] {
Some(kv) if kv.0.eq(key) => break idx_mod,
None => break idx_mod,
_ => {
iter_idx += 1;
assert!(
iter_idx <= len,
"find_slot called without a matching key and full storage!"
);
}
}
};
&self.storage[slot_idx]
}
fn find_slot_linear_mut(&mut self, key: &K) -> &mut Option<(K, V)> {
let mut hasher = self.state.build_hasher();
key.hash(&mut hasher);
let start_idx = hasher.finish() as usize;
let mut iter_idx = 0;
let len = self.storage.len();
let slot_idx = loop {
let idx_mod: usize = (start_idx + iter_idx) % len;
match &self.storage[idx_mod] {
Some(kv) if kv.0.eq(key) => break idx_mod,
None => break idx_mod,
_ => {
iter_idx += 1;
assert!(
iter_idx <= len,
"find_slot called without a matching key and full storage!"
);
}
}
};
&mut self.storage[slot_idx]
}
// Should be called with a sensible load factor.
fn find_slot_quadratic(&self, key: &K) -> &Option<(K, V)> {
let mut hasher = self.state.build_hasher();
key.hash(&mut hasher);
let start_idx = hasher.finish() as usize;
let mut iter_idx: usize = 0;
let len = self.storage.len();
let slot_idx = loop {
let idx_mod: usize = (start_idx + (iter_idx + iter_idx.pow(2)) / 2) % len;
match &self.storage[idx_mod] {
Some(kv) if kv.0.eq(key) => break idx_mod,
None => break idx_mod,
_ => {
iter_idx += 1;
assert!(
iter_idx <= len,
"find_slot called without a matching key and full storage!"
);
}
}
};
&self.storage[slot_idx]
}
// Should be called with a sensible load factor.
fn find_slot_quadratic_mut(&mut self, key: &K) -> &mut Option<(K, V)> {
let mut hasher = self.state.build_hasher();
key.hash(&mut hasher);
let start_idx = hasher.finish() as usize;
let mut iter_idx: usize = 0;
let len = self.storage.len();
let slot_idx = loop {
let idx_mod: usize = (start_idx + (iter_idx + iter_idx.pow(2)) / 2) % len;
match &self.storage[idx_mod] {
Some(kv) if kv.0.eq(key) => break idx_mod,
None => break idx_mod,
_ => {
iter_idx += 1;
assert!(
iter_idx <= len,
"find_slot called without a matching key and full storage!"
);
}
}
};
&mut self.storage[slot_idx]
}
fn resize(&mut self) {
let new_storage: Vec<Option<(K, V)>> = (0..self.storage.len() * 2).map(|_| None).collect();
let old_storage = std::mem::replace(&mut self.storage, new_storage);
self.len = 0;
for (k, v) in old_storage.into_iter().flatten() {
self.insert(k, v);
}
}
pub fn insert(&mut self, key: K, value: V) -> Option<V> {
if self.should_resize() {
self.resize();
}
let slot = if self.quadratic {
self.find_slot_quadratic_mut(&key)
} else {
self.find_slot_linear_mut(&key)
};
let new_slot = Some((key, value));
let old_slot = std::mem::replace(slot, new_slot).map(|kv| kv.1);
if old_slot.is_none() {
self.len += 1;
}
old_slot
}
pub fn get(&self, key: &K) -> Option<&V> {
let slot = if self.quadratic {
self.find_slot_quadratic(key)
} else {
self.find_slot_linear(key)
};
slot.as_ref().map(|kv| &kv.1)
}
pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
let slot = if self.quadratic {
self.find_slot_quadratic_mut(key)
} else {
self.find_slot_linear_mut(key)
};
slot.as_mut().map(|kv| &mut kv.1)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn new() {
let map: MyHashmap<u32, u32> = MyHashmap::new(RandomState::new(), false);
assert!(map.is_empty());
assert_eq!(map.len(), 0);
}
#[test]
fn insert() {
let mut map: MyHashmap<u32, u32> = MyHashmap::new(RandomState::new(), false);
map.insert(1, 2);
map.insert(2, 2);
map.insert(3, 2);
map.insert(4, 2);
map.insert(1, 3);
map.insert(2, 4);
map.insert(3, 5);
map.insert(4, 6);
}
#[test]
fn get() {
let mut map: MyHashmap<u32, u32> = MyHashmap::new(RandomState::new(), false);
map.insert(1, 3);
map.insert(2, 2);
map.insert(3, 1);
assert_eq!(map.get(&1), Some(&3));
assert_eq!(map.get(&2), Some(&2));
assert_eq!(map.get(&3), Some(&1));
assert_eq!(map.get(&6), None);
}
#[test]
fn get_mut() {
let mut map: MyHashmap<u32, u32> = MyHashmap::new(RandomState::new(), false);
map.insert(1, 3);
map.insert(2, 2);
map.insert(3, 1);
assert_eq!(map.get(&1), Some(&3));
let val = map.get_mut(&1);
if let Some(val) = val {
*val = 4;
}
assert_eq!(map.get(&1), Some(&4));
}
#[test]
fn insert_lots() {
let mut map: MyHashmap<u32, u32> = MyHashmap::new(RandomState::new(), false);
for x in 0..100000 {
map.insert(x, x);
assert_eq!(map.get(&x).unwrap(), &x)
}
}
#[test]
fn insert_quadratic() {
let mut map: MyHashmap<u32, u32> = MyHashmap::new(RandomState::new(), true);
map.insert(1, 2);
map.insert(2, 2);
map.insert(3, 2);
map.insert(4, 2);
map.insert(1, 3);
map.insert(2, 4);
map.insert(3, 5);
map.insert(4, 6);
}
#[test]
fn get_quadratic() {
let mut map: MyHashmap<u32, u32> = MyHashmap::new(RandomState::new(), true);
map.insert(1, 3);
map.insert(2, 2);
map.insert(3, 1);
assert_eq!(map.get(&1), Some(&3));
assert_eq!(map.get(&2), Some(&2));
assert_eq!(map.get(&3), Some(&1));
assert_eq!(map.get(&6), None);
}
#[test]
fn get_mut_quadratic() {
let mut map: MyHashmap<u32, u32> = MyHashmap::new(RandomState::new(), true);
map.insert(1, 3);
map.insert(2, 2);
map.insert(3, 1);
assert_eq!(map.get(&1), Some(&3));
let val = map.get_mut(&1);
if let Some(val) = val {
*val = 4;
}
assert_eq!(map.get(&1), Some(&4));
}
#[test]
fn insert_lots_quadratic() {
let mut map: MyHashmap<u32, u32> = MyHashmap::new(RandomState::new(), true);
for x in 0..100000 {
map.insert(x, x);
assert_eq!(map.get(&x).unwrap(), &x)
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment