Hashing & Algoritmos de Armazenamento
Módulo 03
Tabela Hash Manual com Endereçamento Aberto
Uma investigação profunda sobre como estruturas associativas funcionam em nível de máquina. Esta implementação não utiliza a coleção nativa da stdlib, criando do zero um mapa com sondagem linear (*Linear Probing*), reciclagem de registros excluídos via *Tombstones* e redimensionamento dinâmico baseado em limiares de saturação.
01. Decisão de Arquitetura: Endereçamento Aberto vs Encadeamento
Quando duas chaves distintas geram o mesmo índice de hash, ocorre uma colisão. Existem duas formas canônicas de resolver colisões na ciência da computação:
1. Separate Chaining (Encadeamento)
Cada bucket armazena um ponteiro para uma lista ligada. É simples de implementar, mas fragmenta a memória com pequenas alocações avulsas no Heap, gerando altos índices de Cache Misses durante a leitura.
2. Open Addressing (Nossa Abordagem)
Todos os dados residem dentro de um único vetor plano contíguo (Vec<Bucket<K, V>>). Ao colidir no índice $i$, inspecionamos sequencialmente $i+1, i+2, \dots$. Essa técnica maximiza a localidade espacial das linhas de cache L1/L2 do processador.
02. O Padrão Tombstone (Lápides de Deleção)
O maior desafio do Endereçamento Aberto é a remoção. Se ao remover um item simplesmente definíssemos o slot como Empty, a cadeia de busca para elementos que colidiram após ele seria interrompida prematuramente, fazendo buscas legítimas retornarem None.
Como os três estados do enum resolvem o problema:
- Bucket::Empty: O slot nunca foi preenchido. Finaliza a busca imediatamente com segurança.
- Bucket::Occupied(K, V): Contém dados ativos. Se a chave for idêntica, retorna o valor.
- Bucket::Tombstone: Slot previamente deletado. As operações de
get() pulam este slot continuando a busca linear, enquanto operações subsequentes de insert() podem reciclar este espaço sem alocar novos slots.
03. Fator de Carga ($\alpha$) & Primary Clustering
Definido como $\alpha = \frac{N + T}{M}$ (onde $N$ são itens ocupados, $T$ são túmulos e $M$ é a capacidade física total). Se $\alpha$ se aproximar de $1.0$, o Linear Probing sofre de Primary Clustering: longos blocos de slots ocupados começam a se fundir, degradando a busca para $O(N)$.
Ao fixar o limiar em $\alpha \ge 0.70$, o método rehash() dobra a capacidade física, purga todos os túmulos e redistribui as chaves ativas, mantendo o custo médio de busca e inserção rigorosamente em $O(1)$.
| Operação |
Caso Médio |
Pior Caso |
Comportamento de Memória |
| insert(k, v) |
O(1) amortizado |
O(n) no rehash |
Recicla túmulos ou insere em slot contíguo |
| get(k) |
O(1) |
O(n) tabela saturada |
Varredura contígua com alto Cache Hit |
| remove(k) |
O(1) |
O(n) |
Gravação imediata da flag Tombstone |
04. Como a stdlib do Rust (HashBrown) Faz?
💡 Swiss Tables & SIMD:
Historicamente, o Rust utilizava Robin Hood Hashing com SipHash. A partir da versão 1.36, a biblioteca padrão adotou a crate hashbrown (inspirada nas Swiss Tables do Google). Ela separa o array em dois: um array de controle de 1 byte por bucket e um array de pares chave-valor. O array de controle é inspecionado usando instruções SIMD que comparam até 16 buckets simultaneamente em um único ciclo de clock.
use std::collections::hash_map::DefaultHasher;
use std::fmt::{self, Display, Formatter};
use std::hash::{Hash, Hasher};
const INITIAL_CAPACITY: usize = 8;
const MAX_LOAD_FACTOR: f64 = 0.70;
#[derive(Clone, Debug, PartialEq)]
pub enum Bucket<K, V> {
Empty,
Tombstone,
Occupied(K, V),
}
pub struct CustomHashMap<K, V> {
buckets: Vec<Bucket<K, V>>,
len: usize,
tombstones: usize,
}
impl<K, V> CustomHashMap<K, V>
where
K: Hash + Eq + Clone + Display,
V: Clone + Display,
{
pub fn new() -> Self {
let mut buckets = Vec::with_capacity(INITIAL_CAPACITY);
for _ in 0..INITIAL_CAPACITY {
buckets.push(Bucket::Empty);
}
Self {
buckets,
len: 0,
tombstones: 0,
}
}
pub fn len(&self) -> usize {
self.len
}
pub fn capacity(&self) -> usize {
self.buckets.len()
}
pub fn load_factor(&self) -> f64 {
(self.len + self.tombstones) as f64 / self.buckets.len() as f64
}
fn hash_index(&self, key: &K, capacity: usize) -> usize {
let mut hasher = DefaultHasher::new();
key.hash(&mut hasher);
(hasher.finish() as usize) % capacity
}
pub fn insert(&mut self, key: K, value: V) -> Option<V> {
if self.load_factor() >= MAX_LOAD_FACTOR {
self.rehash(self.buckets.len() * 2);
}
let cap = self.buckets.len();
let start_idx = self.hash_index(&key, cap);
let mut first_tombstone = None;
for i in 0..cap {
let idx = (start_idx + i) % cap;
match &mut self.buckets[idx] {
Bucket::Occupied(existing_key, existing_val) => {
if *existing_key == key {
let old_val = std::mem::replace(existing_val, value);
return Some(old_val);
}
}
Bucket::Tombstone => {
if first_tombstone.is_none() {
first_tombstone = Some(idx);
}
}
Bucket::Empty => {
let target_idx = first_tombstone.unwrap_or(idx);
if first_tombstone.is_some() {
self.tombstones -= 1;
}
self.buckets[target_idx] = Bucket::Occupied(key, value);
self.len += 1;
return None;
}
}
}
if let Some(target_idx) = first_tombstone {
self.buckets[target_idx] = Bucket::Occupied(key, value);
self.tombstones -= 1;
self.len += 1;
return None;
}
None
}
pub fn get(&self, key: &K) -> Option<&V> {
let cap = self.buckets.len();
let start_idx = self.hash_index(key, cap);
for i in 0..cap {
let idx = (start_idx + i) % cap;
match &self.buckets[idx] {
Bucket::Occupied(k, v) => {
if k == key {
return Some(v);
}
}
Bucket::Tombstone => {
continue;
}
Bucket::Empty => {
return None;
}
}
}
None
}
pub fn remove(&mut self, key: &K) -> Option<V> {
let cap = self.buckets.len();
let start_idx = self.hash_index(key, cap);
for i in 0..cap {
let idx = (start_idx + i) % cap;
match &self.buckets[idx] {
Bucket::Occupied(k, _) => {
if k == key {
if let Bucket::Occupied(_, val) =
std::mem::replace(&mut self.buckets[idx], Bucket::Tombstone)
{
self.len -= 1;
self.tombstones += 1;
return Some(val);
}
}
}
Bucket::Tombstone => continue,
Bucket::Empty => return None,
}
}
None
}
fn rehash(&mut self, new_capacity: usize) {
let mut old_buckets = Vec::with_capacity(new_capacity);
for _ in 0..new_capacity {
old_buckets.push(Bucket::Empty);
}
let old_items = std::mem::replace(&mut self.buckets, old_buckets);
self.len = 0;
self.tombstones = 0;
for bucket in old_items {
if let Bucket::Occupied(k, v) = bucket {
self.insert(k, v);
}
}
}
pub fn print_inspection(&self) {
println!(" Capacidade: {} | Elementos: {} | Lápides (Tombstones): {} | Load Factor: {:.2}",
self.capacity(), self.len(), self.tombstones, self.load_factor()
);
for (i, bucket) in self.buckets.iter().enumerate() {
match bucket {
Bucket::Empty => println!(" [{:02}] -> [ Vazio ]", i),
Bucket::Tombstone => println!(" [{:02}] -> [ 🪦 LÁPIDE (Tombstone) ]", i),
Bucket::Occupied(k, v) => println!(" [{:02}] -> [ OCUPADO ] Chave: \"{}\" => {}", i, k, v),
}
}
}
}
fn main() {
println!("============================================================");
println!("🦀 RUST DATA STRUCTURES: CUSTOM HASHMAP (LINEAR PROBING)");
println!("============================================================");
let mut map: CustomHashMap<String, String> = CustomHashMap::new();
println!("\n1. Inserindo dados iniciais (Capacidade base: 8):");
map.insert("db_port".to_string(), "5432".to_string());
map.insert("env".to_string(), "production".to_string());
map.insert("timeout".to_string(), "30s".to_string());
map.insert("auth_mode".to_string(), "oauth2".to_string());
println!(" Estado físico dos buckets após 4 inserções:");
map.print_inspection();
println!("\n2. Recuperando chaves (get):");
println!(" get(\"db_port\") => {:?}", map.get(&"db_port".to_string()));
println!(" get(\"auth_mode\") => {:?}", map.get(&"auth_mode".to_string()));
println!(" get(\"missing\") => {:?}", map.get(&"missing".to_string()));
println!("\n3. Deletando chaves e validando o Tombstone Pattern:");
println!(" -> Removendo \"env\"...");
let removed = map.remove(&"env".to_string());
println!(" Removido: {:?}", removed);
println!(" Estado dos buckets com o túmulo de busca preservado:");
map.print_inspection();
println!("\n4. Forçando Colisões e Rehash Dinâmico:");
println!(" Inserindo novas chaves até ultrapassar o Load Factor limite (0.70)...");
map.insert("cache_ttl".to_string(), "3600".to_string());
map.insert("retry_count".to_string(), "5".to_string());
map.insert("log_level".to_string(), "debug".to_string());
println!("\n Tabela após Rehashing automático:");
map.print_inspection();
println!("\n5. Garantindo integridade após expansão:");
println!(" get(\"timeout\") => {:?}", map.get(&"timeout".to_string()));
println!(" get(\"cache_ttl\") => {:?}", map.get(&"cache_ttl".to_string()));
println!(" Finalizado com sucesso sem vazamento de memória e O(1) amortizado!");
}