Foto de takis politis no Unsplash
Os Hash maps são conhecidos por muitos nomes diferentes. Dicionários, objetos, registros e mapas, no fim, são todos mais ou menos sinônimos de hash map. Além disso, eles são algo que usamos diariamente. O padrão de comunicação da internet moderna, JSON, utiliza um hash map como componente central da especificação. Os Hash maps são usados em muitos algoritmos como o de otimização para verificação de dados durante iteração. Os Hash maps são utilizados para armazenamento do cache básico em programas. O ponto é que eles são ubíquos. Se você já fez um programa antes, você usou hash maps.
Por que usar um Hash Map?
Essa é uma boa pergunta. Os hash maps são tão populares porque, na maioria das vezes, eles fornecem tempo de busca O(1) e tempo de remoção O(1). O que isso significa? Bem, se você não está familiarizado com a notação Big-O, essa é uma maneira de descrever como o tempo de execução de uma função se relaciona com os dados fornecidos a ela. Por exemplo, se temos um algoritmo que percorre um array para encontrar um item e, em seguida, retorna esse item, nossa notação Big-O para esse algoritmo é O(n), sendo n o número de elementos no array. O(1) é chamado de tempo constante e é a "melhor" das complexidades de tempo porque a entrada de uma função ou de dados no algoritmo não afeta o tempo de execução da função/algoritmo.
Então, por que é chamado de Hash Map?
Essa é uma boa pergunta. A estrutura de dados subjacente de um hash map é um array. Como você sabe, podemos fazer uma busca em um array por meio de um índice. Por exemplo, o primeiro elemento do array em um sistema de indexação baseado em zero é arr[0]. Lembre-se de que estamos implementando uma estrutura de armazenamento chave-valor. Então, como podemos acessar qualquer parte do array em tempo O(1)?
É aí que entra a parte "hashing". O hashing é uma "criptografia unidirecional". Isso significa que você insere um valor em um algoritmo de hash e um valor completamente diferente é gerado como resultado, representando a entrada e sendo em sua maioria, único para cada entrada, mas não podendo ser revertido para a entrada original.
Um destes algoritmos é o algoritmo Fowler, Noll, Vo. Ele pode gerar hashes de vários comprimentos, mas a versão de 64 bits funciona da seguinte forma, em pseudo-código.
algorithm 64-bit fnv-1a is
hash := 14695981039346656037
for each byte_of_data to be hashed do
hash := hash XOR byte_of_data
hash := hash × 1099511628211
return hash
Essencialmente, você tem um valor inicial chamado de FNV offset basis no topo. Em seguida, para cada byte de dados, você realiza uma operação de xor (ou exclusivo a nível de bits) em relação ao valor de hash anterior e depois multiplica pelo FNV prime e atribui novamente ao valor de hash no topo do escopo. Na próxima iteração, esse processo é repetido até que tenha sido feito hash doúltimo byte seja. O valor resultante é então retornado.
O que isso faz é transformar qualquer valor que tenhamos fornecido como chave, seja uma string ou um número inteiro, em um número inteiro. Isso significa que, independentemente do que alimentemos nesse algoritmo de hash, obtemos um número inteiro que poderíamos transformar em um índice para acesso direto a um array, como arr[10], mas em vez de 10, obtemos um número muito maior.
Na verdade, o número é grande demais! Se usarmos "myKey" como uma string para ser hash com esse algoritmo, obtemos o número 11011271260727893002. Esse é um número muito grande para alocar espaços em um array. Embora isso provavelmente funcionasse em uma linguagem com coleta de lixo devido à forma como eles implementam arrays, não poderíamos criar uma estrutura de dados de baixo nível dessa maneira. 64 bits multiplicados pelo valor de hash resultaria em 88 exabytes. Para se ter uma ideia, o mundo estava gerando coletivamente 161 exabytes por ano em 2006.
No entanto, o que podemos fazer é usar o operador de módulo para ajustar nosso hash ao tamanho do nosso array. Por exemplo, se dimensionarmos nosso array para 256, poderíamos fazer 256 mod 11011271260727893002, o que resultaria em 10. Podemos usar o número 10 como o slot para colocar nosso valor. Vamos implementar isso em Rust.
pub struct FnvHasher {
prime: u64,
offset: u64,
}
impl FnvHasher {
pub fn new() -> Self {
Self {
prime: 0x100000001b3,
offset: 0xcbf29ce484222325,
}
}
pub fn hash(&self, value: &[u8], array_size: i64) -> u64 {
let mut final_hash = self.offset;
for byte in value.iter() {
final_hash = final_hash ^ (*byte as u64);
final_hash = final_hash.wrapping_mul(self.prime);
}
final_hash % (array_size as u64)
}
}
Como você pode ver, implementamos o algoritmo de hash conforme descrito acima.
Observe a chamada para wrapping_mul para realizar a multiplicação e evitar o estouro do tipo u64. Também observe que nossos números inteiros são armazenados como valores hexadecimais.
Hashes e Buckets
Agora que estabelecemos o que é o hash e como implementá-lo, vamos expandir sobre como usamos o hash para armazenar dados e o desafio único que os hash maps enfrentam: colisões.
Aqui está o problema: embora um hash de 64 bits por si só não seja propenso a colisões, ao adicionar o operador de módulo em relação ao tamanho do nosso array, estamos propensos a colisões. Então, como lidamos com isso?
Uma forma de fazer isso é chamada de "encadeamento" (chaining). Digamos que façamos o hash da letra "a" e isso nos retorne a posição 3 no array após o hash. Digamos então que façamos o hash da letra "A" maiúscula e também retorne a posição 3 no array. O que fazemos?
Bem, em vez de substituir o hash anterior, adicionamos a chave original a uma estrutura junto com o valor. Adicionamos esse valor a um array na localização do hash. Quando usamos o método get para procurar um hash e temos mais de um elemento no array interno, fazemos uma busca linear pela chave original e retornamos quando as chaves originais coincidem. Tecnicamente, isso não é O(1) o tempo todo, mas é a grande maioria das vezes. Colisões não são a regra, mas a exceção.
#[derive(Debug, Clone)]
pub struct KeyValue<T> {
key: String,
value: T,
}
impl<T> KeyValue<T> {
pub fn new(key: String, value: T) -> Self {
Self { key, value }
}
}
#[derive(Debug, Clone)]
pub struct HashTable<T> {
max_size: i64,
length: i64,
array: Vec<Vec<Rc<KeyValue<T>>>>,
}
impl<T> HashTable<T> {
pub fn new() -> Self {
Self {
max_size: 1000,
length: 0,
array: vec![Vec::new(); 1000]
}
}
pub fn insert(&mut self, key: String, value: T) {
let hasher = FnvHasher::new();
let hash = hasher.hash(key.as_bytes(), self.max_size);
let new_value = KeyValue::new(key, value);
self.array[hash as usize].push(Rc::new(new_value));
self.length += 1;
}
}
Como você pode ver acima, criamos uma estrutura de tabela de hash com três campos. MaxSize é o tamanho máximo do nosso array subjacente. É isso que vamos usar no operador de módulo.
Também temos uma propriedade de comprimento (length) que incrementamos e decrementamos ao adicionar e remover chaves.
Temos também uma estrutura de vetor aninhado, com o nível superior inicializado com nossa propriedade max_size. O vetor interno usa um ponteiro de contagem de referência (reference count pointer) com um novo vetor inicializado como vazio.
Ao inserir, você pode ver que fazemos o hash da chave, criamos um novo KeyValue com a chave original (raw key) e o valor, e o adicionamos ao vetor interno (inner-vector).
E quanto ao Get e Delete?
Get e Delete são relativamente diretos.
impl<T> HashTable<T> {
pub fn get(&self, key: String) -> Option<&T> {
let hasher = FnvHasher::new();
let hash = hasher.hash(key.as_bytes(), self.max_size);
if self.array[hash as usize].len() == 0 {
return None
}
if self.array[hash as usize].len() == 1 {
return Some(&self.array[hash as usize][0].value)
}
for item in self.array[hash as usize].iter() {
if item.key == key {
return Some(&item.value)
}
}
None
}
pub fn remove(&mut self, key: String) {
let hasher = FnvHasher::new();
let hash = hasher.hash(key.as_bytes(), self.max_size);
if self.array[hash as usize].len() == 0 {
return
}
if self.array[hash as usize].len() == 1 {
self.array[hash as usize].remove(0);
return;
}
for (index, item) in self.array[hash as usize].iter().enumerate() {
if item.key == key {
self.array[hash as usize].remove(index);
return;
}
}
self.length -= 1;
}
}
Obter uma chave envolve verificar o comprimento do vetor interno (inner-vector). Se for zero, retornamos a versão do Rust do valor nulo, que essencialmente é um enum chamado Option com dois membros: None e Some. None é exatamente o que parece, onde Some envolve o valor retornado. Ao retornar um Option, é necessário verificar se o valor é none ou some e lidar com o caso de none antes de continuar.
Para garantir que o Get seja o mais eficiente possível, verificamos se o comprimento do vetor interno é zero. Se for, é claro que não há chave para obter e retornamos None. Se for um, simplesmente retornamos o valor no índice um. Caso contrário, precisamos percorrer o vetor interno devido às colisões que ocorreram e comparar a chave original (raw key) com a chave original armazenada e retornar aquele valor, caso exista.
Para exclusão, usamos a lógica acima, mas para fins de remoção.
Isso é tudo?
Para nossa implementação, sim. No entanto, essa não é uma solução que usaríamos em produção. Em primeiro lugar, não lidamos com o caso de chaves duplicadas. Outro problema é que não permitimos que os nomes das chaves sejam de outro tipo que não seja String. Idealmente, poderíamos adicionar outro tipo, como um número inteiro. Adicionar um número inteiro como chave não mudaria nada, exceto os parâmetros genéricos que estamos passando e o que passamos para o hash como parâmetro. Também poderíamos implementar um método mais eficiente para lidar com colisões. Este não é o método mais rápido, mas é um dos mais fáceis de entender.
Mostre-nos os testes!
Claro.
fn main() {
let hasher = FnvHasher::new();
let hash = hasher.hash(b"hello", 100);
println!("Hash: {}", hash);
}
#[cfg(test)]
mod tests {
// Observe este útil da linguagem : importar nomes do escopo externo (para testes de módulos).
use crate::HashTable;
#[teste]
fn test_add() {
let mut table = HashTable::<String>::new();
table.insert("hello".to_string(), "world".to_string());
table.insert("hello2".to_string(), "world2".to_string());
table.insert("hello3".to_string(), "world3".to_string());
assert_eq!(table.get("hello".to_string()).unwrap(), "world");
assert_eq!(table.get("hello2".to_string()).unwrap(), "world2");
assert_eq!(table.get("hello3".to_string()).unwrap(), "world3");
}
#[teste]
fn test_remove() {
let mut table = HashTable::<String>::new();
table.insert("hello".to_string(), "world".to_string());
assert_eq!(table.get("hello".to_string()).unwrap(), "world");
table.remove("hello".to_string());
assert_eq!(table.get("hello".to_string()), None);
}
}
Este artigo foi escrito por Kyle Fahey e traduzido por Adriano P. de Araujo. O original em inglês pode ser encontrado aqui
Top comments (0)