Capítulo 13 14 min de leitura

HashMap & Set

A biblioteca padrão do Glide oferece dois contêineres associativos, ambos com chave string: um HashMap<V> genérico (endereçamento aberto, sondagem linear, redimensionamento automático com carga de 75%) e um StringSet construído sobre ele. Os dois podem ser alocados no heap ou em arena e são donos dos seus buffers de slots; combine toda construção com defer x.free().

Import

import stdlib::hashmap::*;   // HashMap<V>, Pair<K, V>
import stdlib::set::*;       // StringSet (também re-exporta hashmap)

HashMap<V>

Um mapa hash de chaves string para valores V. As chaves são armazenadas por valor, de modo que as strings do chamador podem ser liberadas independentemente. Todas as operações, exceto resize, têm custo amortizado O(1); resize tem custo O(n).

pub struct HashMap<V> {
    keys: *string,      // chaves dos slots (válidas onde occupied[i])
    values: *V,         // valores dos slots (válidos onde occupied[i])
    occupied: *bool,    // flag de ocupação por slot para sondagem
    len: i32,           // número de entradas ativas
    cap: i32,           // tamanho da alocação em slots (potência de dois quando não zero)
    is_arena: bool,     // true quando alocado por bump na arena ativa
}

Os campos da struct são internos; interaja com o mapa por meio dos seus métodos.

Construção e tempo de vida

Método	Assinatura	Descrição
`new`	`fn new() -> *HashMap<V>`	Mapa vazio sem alocação. O primeiro `insert` aloca a tabela.
`free`	`fn free(self: *HashMap<V>)`	Libera os três buffers de slots e a struct. O ponteiro fica pendente após a chamada. Sem efeito em mapas alocados por arena.

import stdlib::hashmap::*;

fn main() -> i32 {
    let m: *HashMap<i32> = HashMap::new();
    defer m.free();

    m.insert("one", 1);
    println!("one ->", m.get("one"));   // 1
    return 0;
}

Inserção e leitura

Método	Assinatura	Descrição
`insert`	`fn insert(self: *HashMap<V>, k: string, v: V)`	Associa `k` a `v`, substituindo qualquer valor existente. Dispara um redimensionamento com 75% de carga.
`get`	`fn get(self: *HashMap<V>, k: string) -> V`	Lê o valor associado a `k`. Comportamento indefinido se `k` estiver ausente — proteja a chamada com `contains` antes.
`contains`	`fn contains(self: *HashMap<V>, k: string) -> bool`	`true` quando `k` está associado a um valor.
`remove`	`fn remove(self: *HashMap<V>, k: string) -> bool`	Remove a entrada de `k`; retorna `true` se algo foi removido.

m.insert("count", 1);
m.insert("count", 2);          // sobrescreve — chaves são únicas
println!(m.get("count"));      // 2

if m.contains("count") {
    let n: i32 = m.get("count");
}

let was_present: bool = m.remove("count");   // true
let again: bool      = m.remove("count");    // false

Como HashMap<V> não possui get-com-padrão, encapsule o padrão contains/get em um helper para o caso comum de "ler ou usar fallback":

import stdlib::hashmap::*;

fn get_or(m: *HashMap<i32>, k: string, fallback: i32) -> i32 {
    if m.contains(k) { return m.get(k); }
    return fallback;
}

fn main() -> i32 {
    let m: *HashMap<i32> = HashMap::new();
    defer m.free();
    m.insert("hits", 5);

    println!("hits:", get_or(m, "hits", 0));     // 5
    println!("misses:", get_or(m, "misses", 0)); // 0
    return 0;
}

Um padrão comum — acumular contagens — combina contains, get e insert:

import stdlib::hashmap::*;

fn main() -> i32 {
    let counts: *HashMap<i32> = HashMap::new();
    defer counts.free();

    let text: string = "the cat the dog the cat";
    let words: *Vector<string> = text.split(" ");
    for let i: i32 = 0; i < words.len(); i++ {
        let w: string = words.get(i);
        if counts.contains(w) {
            counts.insert(w, counts.get(w) + 1);
        } else {
            counts.insert(w, 1);
        }
    }
    println!("the:", counts.get("the"));   // 3
    println!("cat:", counts.get("cat"));   // 2
    return 0;
}

Tamanho e estado

Método	Assinatura	Descrição
`len`	`fn len(self: *HashMap<V>) -> i32`	Número de entradas ativas.
`is_empty`	`fn is_empty(self: *HashMap<V>) -> bool`	`true` quando o mapa não contém nenhuma entrada.
`cap`	`fn cap(self: *HashMap<V>) -> i32`	Quantidade de slots alocados (potência de dois quando não zero). `0` antes do primeiro insert, `8` depois. Para diagnóstico — a maioria dos chamadores quer `len()`.
`clear`	`fn clear(self: *HashMap<V>)`	Remove todas as entradas. A capacidade é preservada, portanto inserções subsequentes não realocam.

let m: *HashMap<i32> = HashMap::new();   defer m.free();
m.cap();                 // 0  (sem alocação ainda)
m.insert("a", 1);
m.cap();                 // 8  (tamanho inicial da tabela)
m.insert("b", 2);
m.len();                 // 2
m.is_empty();            // false
m.clear();
m.len();                 // 0
m.is_empty();            // true

A tabela dobra de tamanho sempre que um insert levaria a carga a ultrapassar 75% (len * 4 >= cap * 3). O primeiro insert aloca 8 slots; a 7ª chave distinta atinge o limiar (7*4 >= 8*3) e expande a tabela para 16:

import stdlib::hashmap::*;

fn main() -> i32 {
    let m: *HashMap<i32> = HashMap::new();
    defer m.free();

    println!("cap before insert:", m.cap());   // 0
    m.insert("a", 1);
    println!("cap after 1:", m.cap());          // 8
    m.insert("b", 2);
    m.insert("c", 3);
    m.insert("d", 4);
    m.insert("e", 5);
    m.insert("f", 6);
    m.insert("g", 7);   // 7º de 8 slots dispara o redimensionamento -> 16
    println!("cap after 7:", m.cap());          // 16
    println!("len:", m.len());                  // 7
    return 0;
}

Snapshots de iteração

Esses métodos retornam cada um um Vector recém-alocado. A ordem é a ordem dos slots, que não é especificada em relação à ordem de inserção. keys(), values() e entries() compartilham a mesma ordem de slots, portanto a iteração por índice emparelhado é significativa dentro de um único momento no tempo.

Método	Assinatura	Descrição
`keys`	`fn keys(self: HashMap<V>) -> Vector<string>`	Snapshot de todas as chaves ativas.
`values`	`fn values(self: HashMap<V>) -> Vector<V>`	Snapshot de todos os valores ativos (mesma ordem que `keys`).
`entries`	`fn entries(self: HashMap<V>) -> Vector<*Pair<string, V>>`	Snapshot de cada `(chave, valor)` como um `Pair`.

import stdlib::hashmap::*;

fn main() -> i32 {
    let m: *HashMap<i32> = HashMap::new();
    defer m.free();
    m.insert("a", 1);
    m.insert("b", 2);

    let ks: *Vector<string> = m.keys();
    for let i: i32 = 0; i < ks.len(); i++ { println!(ks.get(i)); }

    let vs: *Vector<i32> = m.values();
    println!("sum:", vs.sum());          // 3

    let es: *Vector<*Pair<string, i32>> = m.entries();
    for let i: i32 = 0; i < es.len(); i++ {
        let p: *Pair<string, i32> = es.get(i);
        println!(p.first, "->", p.second);
    }
    return 0;
}

keys() e values() são emitidos na mesma ordem de slots, portanto um único loop por índice percorre os dois como pares correspondentes (desde que você não mute o mapa entre os snapshots):

import stdlib::hashmap::*;

fn main() -> i32 {
    let m: *HashMap<i32> = HashMap::new();
    defer m.free();
    m.insert("a", 1);
    m.insert("b", 2);
    m.insert("c", 3);

    let ks: *Vector<string> = m.keys();
    let vs: *Vector<i32> = m.values();
    for let i: i32 = 0; i < ks.len(); i++ {
        println!(ks.get(i), "=", vs.get(i));
    }
    return 0;
}

entries() agrupa os dois em um Pair por slot — útil quando você quer passar (chave, valor) como uma unidade ou fazer uma redução sobre eles:

import stdlib::hashmap::*;

fn main() -> i32 {
    let m: *HashMap<i32> = HashMap::new();
    defer m.free();
    m.insert("a", 1);
    m.insert("b", 2);
    m.insert("c", 3);

    let es: *Vector<*Pair<string, i32>> = m.entries();
    let mut total: i32 = 0;
    for let i: i32 = 0; i < es.len(); i++ {
        let p: *Pair<string, i32> = es.get(i);
        total = total + p.second;
    }
    println!("sum of values:", total);   // 6
    return 0;
}

Transformando valores

Método	Assinatura	Descrição
`map_values`	`fn map_values<U>(self: HashMap<V>, f: fn(V) -> U) -> HashMap<U>`	Aplica `f` a cada valor, produzindo um novo mapa com as mesmas chaves e valores transformados. O original permanece inalterado.

import stdlib::hashmap::*;

fn square(x: i32) -> i32 { return x * x; }

fn main() -> i32 {
    let m: *HashMap<i32> = HashMap::new();
    defer m.free();
    m.insert("a", 2);
    m.insert("b", 3);

    let m2: *HashMap<i32> = m.map_values(square);
    defer m2.free();
    println!("b squared:", m2.get("b"));   // 9
    return 0;
}

map_values é genérico em relação ao tipo de saída U, portanto o mapa resultante pode conter um tipo de valor diferente do mapa de origem. Aqui fn(i32) -> string transforma um mapa de contagens em um mapa de rótulos, deixando o original intacto:

import stdlib::hashmap::*;

fn label(x: i32) -> string { return format!("v={}", x); }

fn main() -> i32 {
    let m: *HashMap<i32> = HashMap::new();
    defer m.free();
    m.insert("a", 10);
    m.insert("b", 20);

    let labels: *HashMap<string> = m.map_values(label);
    defer labels.free();

    println!(labels.get("a"));   // v=10
    println!(labels.get("b"));   // v=20
    println!(m.get("a"));        // 10  (fonte inalterada)
    return 0;
}

Exemplo prático: agrupamento

Um HashMap cujo tipo de valor é em si um *Vector<V> é a estrutura canônica de "group-by". Inicialize um bucket vazio na primeira vez que uma chave aparecer e, em seguida, empurre elementos para dentro dele:

import stdlib::hashmap::*;

fn main() -> i32 {
    let groups: *HashMap<*Vector<string>> = HashMap::new();
    defer groups.free();

    let words: *Vector<string> = "apple ant bee bird cat".split(" ");
    for let i: i32 = 0; i < words.len(); i++ {
        let w: string = words.get(i);
        let key: string = w.substring(0, 1);   // agrupa pela primeira letra
        if !groups.contains(key) {
            groups.insert(key, Vector::new());
        }
        let bucket: *Vector<string> = groups.get(key);
        bucket.push(w);
    }

    let ks: *Vector<string> = groups.keys();
    for let i: i32 = 0; i < ks.len(); i++ {
        let k: string = ks.get(i);
        let b: *Vector<string> = groups.get(k);
        println!(k, "->", b.len());   // a -> 2, b -> 2, c -> 1
    }
    return 0;
}

StringSet

Um set de strings, implementado sobre HashMap<bool>. Inserção e remoção indicam se o set realmente mudou, o que torna a deduplicação uma operação de uma linha.

pub struct StringSet {
    m: *HashMap<bool>,   // mapa de apoio interno
}

Método	Assinatura	Descrição
`new`	`fn new() -> *StringSet`	Cria um set de strings vazio.
`insert`	`fn insert(self: *StringSet, k: string) -> bool`	Insere `k`; retorna `true` quando não estava presente antes.
`contains`	`fn contains(self: *StringSet, k: string) -> bool`	`true` quando `k` está presente.
`remove`	`fn remove(self: *StringSet, k: string) -> bool`	Remove `k`; retorna `true` quando estava presente.
`len`	`fn len(self: *StringSet) -> i32`	Número de chaves atualmente contidas.
`clear`	`fn clear(self: *StringSet)`	Remove todas as chaves preservando a alocação do mapa interno.
`free`	`fn free(self: *StringSet)`	Libera o mapa interno e a struct do set. Use com `defer`.

import stdlib::set::*;

fn main() -> i32 {
    let s: *StringSet = StringSet::new();
    defer s.free();

    let added: bool = s.insert("apple");   // true
    let again: bool = s.insert("apple");   // false (já presente)
    println!(added, again);

    s.insert("banana");
    println!("has apple:", s.contains("apple"));   // true
    println!("has grape:", s.contains("grape"));   // false
    println!("len:", s.len());                     // 2

    let removed: bool = s.remove("banana");        // true
    let removed2: bool = s.remove("banana");       // false
    println!(removed, removed2);

    s.clear();
    println!("len:", s.len());                     // 0
    return 0;
}

O retorno booleano de insert torna a deduplicação baseada em set concisa — incremente um contador apenas quando o valor for genuinamente novo:

import stdlib::set::*;

fn main() -> i32 {
    let seen: *StringSet = StringSet::new();
    defer seen.free();

    let words: *Vector<string> = "the cat the dog the cat".split(" ");
    let unique: i32 = 0;
    for let i: i32 = 0; i < words.len(); i++ {
        if seen.insert(words.get(i)) { unique = unique + 1; }
    }
    println!("unique words:", unique);   // 3
    return 0;
}

A pertinência a um set brilha em interseção e diferença. Como StringSet não tem iterador, conduza a comparação a partir de uma lista conhecida de candidatos e teste cada um com contains:

import stdlib::set::*;

fn main() -> i32 {
    let a: *StringSet = StringSet::new();
    defer a.free();
    let b: *StringSet = StringSet::new();
    defer b.free();

    a.insert("x"); a.insert("y"); a.insert("z");
    b.insert("y"); b.insert("z"); b.insert("w");

    let common: *StringSet = StringSet::new();
    defer common.free();

    let items: *Vector<string> = "x y z".split(" ");
    for let i: i32 = 0; i < items.len(); i++ {
        let it: string = items.get(i);
        if a.contains(it) && b.contains(it) {
            common.insert(it);
        }
    }
    println!("intersection size:", common.len());   // 2 (y, z)
    return 0;
}

Pair<K, V>

Retornado por HashMap::entries. Uma tupla mínima de dois campos (Glide ainda não possui tuplas anônimas).

pub struct Pair<K, V> {
    pub first: K,
    pub second: V,
}

pub fn new(first: K, second: V) -> *Pair<K, V>   // Pair::new(...)

Ambos os campos são públicos; leia-os diretamente:

let p: *Pair<i32, string> = Pair::new(42, "answer");
p.first;     // 42
p.second;    // "answer"

Import

HashMap&lt;V&gt;

Construção e tempo de vida

Inserção e leitura

Tamanho e estado

Snapshots de iteração

Transformando valores

Exemplo prático: agrupamento

StringSet

Pair&lt;K, V&gt;

Notas de tempo de vida e alocação

HashMap<V>

Pair<K, V>