use std::{
hash::{DefaultHasher, Hash, Hasher},
iter::successors,
ops::Index,
};
use crate::{SymbolTable, searching::SearchingNode};
const INITIAL_CAPACITY: usize = 4;
#[derive(Debug, Default)]
pub struct LinearProbingHashTable<K, V> {
items: Vec<Option<SearchingNode<K, V>>>,
amount: usize,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Checks<'a, K, V> {
HashTableTooSmall(usize, usize),
CouldNotGetKey(&'a K, Option<&'a V>), }
pub struct Iter<'a, K, V> {
items: &'a Vec<Option<SearchingNode<K, V>>>,
current: usize,
}
impl<K: Hash + Eq, V> LinearProbingHashTable<K, V> {
pub fn new() -> Self {
Self::with_capacity_unchecked(INITIAL_CAPACITY)
}
pub fn with_capacity(mut amount: usize) -> Self {
let prev_pow2 = 2usize.pow(amount.ilog2());
let next_pow2 = amount.checked_next_power_of_two();
amount = if let Some(next_pow2) = next_pow2 {
if amount.abs_diff(prev_pow2) <= amount.abs_diff(next_pow2) {
prev_pow2
} else {
next_pow2
}
} else {
prev_pow2
};
Self::with_capacity_unchecked(amount)
}
pub fn with_capacity_unchecked(amount: usize) -> Self {
let mut items = Vec::with_capacity(amount);
items.resize_with(amount, || None);
Self { items, amount: 0 }
}
pub fn iter<'a>(&'a self) -> Iter<'a, K, V> {
Iter {
items: &self.items,
current: 0,
}
}
fn resize(&mut self, amount: usize) {
let mut temp = LinearProbingHashTable::with_capacity(amount);
for SearchingNode(key, value) in
self.items.split_off(0).into_iter().flatten()
{
temp.put(key, value.unwrap());
}
self.items = temp.items;
}
fn hash(&self, key: &K) -> usize {
let mut hasher = DefaultHasher::new();
key.hash(&mut hasher);
let mut h = hasher.finish() as usize;
h ^= (h >> 20) ^ (h >> 12) ^ (h >> 7) ^ (h >> 4);
h & (self.items.len() - 1)
}
fn hash_iter(start: usize, max: usize) -> impl Iterator<Item = usize> {
successors(Some(start), move |&a| Some((a + 1) % max))
}
fn check<'a>(&'a self) -> Result<(), Checks<'a, K, V>> {
if self.items.len() < self.amount * 2 {
Err(Checks::HashTableTooSmall(self.amount, self.items.len()))
} else {
for n in self.items.iter().flatten() {
if self.get(&n.0).is_none() {
return Err(Checks::CouldNotGetKey(&n.0, n.1.as_ref()));
}
}
Ok(())
}
}
}
impl<K: Hash + Eq, V> SymbolTable<K, V> for LinearProbingHashTable<K, V> {
fn put(&mut self, key: K, value: V) {
if self.amount >= self.items.len() / 2 {
self.resize(self.items.len() * 2);
}
let mut i = self.hash(&key);
while let Some(n) = &mut self.items[i] {
if n.0 == key {
n.1 = Some(value);
return;
}
i += 1;
}
self.items[i] = Some(SearchingNode(key, Some(value)));
self.amount += 1;
}
fn get(&self, key: &K) -> Option<&V> {
let start = self.hash(key);
let max = self.items.len();
for i in Self::hash_iter(start, max) {
if let Some(v) = &self.items[i] {
if &v.0 == key {
return v.1.as_ref();
}
} else {
break;
}
}
None
}
fn delete(&mut self, key: &K)
where
K: Clone,
V: Clone,
{
if self.amount == 0 || !self.contains(key) {
return;
}
let m = self.items.len();
let mut i = self.hash(key);
while key != &self.items[i].as_ref().unwrap().0 {
i = (i + 1) % m;
}
self.items[i] = None;
self.amount -= 1;
i = (i + 1) % m;
while self.items[i].is_some() {
let item = self.items[i].take().unwrap();
self.amount -= 1;
self.put(item.0, item.1.unwrap());
i = (i + 1) % m;
}
if self.amount > 0 && self.amount <= m / 8 {
self.resize(m / 2);
}
debug_assert!(self.check().is_ok())
}
fn clear(&mut self) {
self.items.clear();
self.items.resize_with(INITIAL_CAPACITY, || None);
}
fn size(&self) -> usize {
self.amount
}
}
impl<K: Eq + Hash, V> Index<&K> for LinearProbingHashTable<K, V> {
type Output = V;
#[inline]
fn index(&self, key: &K) -> &Self::Output {
self.get(key).expect("Key not found in SymbolTable")
}
}
impl<'a, K: Eq + Hash, V> Iterator for Iter<'a, K, V> {
type Item = (&'a K, &'a V);
fn next(&mut self) -> Option<Self::Item> {
let max = self.items.len();
while self.current != max {
match self.items.get(self.current) {
Some(Some(v)) => {
self.current += 1;
return Some((&v.0, v.1.as_ref().unwrap()));
}
Some(None) => self.current += 1,
None => return None,
}
}
None
}
}
impl<K, V> IntoIterator for LinearProbingHashTable<K, V> {
type Item = (K, V);
type IntoIter = std::vec::IntoIter<Self::Item>;
fn into_iter(self) -> Self::IntoIter {
self.items
.into_iter()
.flatten()
.map(|SearchingNode(k, v)| (k, v.unwrap()))
.collect::<Vec<_>>() .into_iter()
}
}
impl<'a, K: Eq + Hash, V> IntoIterator for &'a LinearProbingHashTable<K, V> {
type Item = (&'a K, &'a V);
type IntoIter = Iter<'a, K, V>;
fn into_iter(self) -> Self::IntoIter {
self.iter()
}
}
super::test_hash_table!(LinearProbingHashTable);