Diário de Bordo do Farol

Os conjuntos de hash são coleções mutáveis e não ordenadas que guardam cada valor no máximo uma vez. A consulta, a inserção e a remoção são, em média, O(1). Estão em hash-sets e implementam o protocolo sets.

Literais de conjuntos de hash

HS{ "NS-1024" "WB-203" } .
! => HS{ "NS-1024" "WB-203" }

HS{ } é o literal vazio. Tal como outros literais de Factor, é um objeto partilhado: todas as referências a HS{ } no código fonte apontam para o mesmo conjunto. HS{ } clone dá-te uma cópia nova e independente a cada chamada.

A partir de uma sequência

>hash-set ( seq -- set )    ! build a fresh set from a sequence

Quando já tens os valores numa sequência, >hash-set converte-os num único passo, descartando eventuais duplicados.

USING: hash-sets prettyprint ;

{ "NS-1024" "WB-203" "NS-1024" } >hash-set .
! => HS{ "NS-1024" "WB-203" }

Juntar e remover

adjoin     ( elt set -- )    ! insert in place; no-op if already present
adjoin-all ( seq set -- )    ! insert every element of seq in place
delete     ( elt set -- )    ! remove in place; no-op if absent

Os três alteram o conjunto; nenhum devolve nada para a pilha.

USING: hash-sets kernel sets ;

HS{ } clone
"NS-1024" over adjoin
"WB-203"  over adjoin
"NS-1024" over adjoin    ! duplicate — no effect
.                        ! => HS{ "NS-1024" "WB-203" }

adjoin-all é a forma em bloco: junta cada elemento de uma sequência, ignorando duplicados tal como adjoin faz um a um.

USING: hash-sets kernel sets ;

HS{ "NS-1024" } clone
{ "WB-203" "NS-1024" "QR-7" } over adjoin-all
.                        ! => HS{ "QR-7" "NS-1024" "WB-203" }  (order not guaranteed)

Perguntar ao conjunto

in?         ( elt set -- ? )   ! is elt in the set?
null?       ( set -- ? )       ! is the set empty?
cardinality ( set -- n )       ! number of elements
members     ( set -- seq )     ! enumerate as a sequence

in? é o teste de pertença do protocolo de conjuntos. É diferente de member? (de sequences), que faz uma pesquisa linear sobre uma sequência. Para um conjunto de hash, in? é uma consulta de hash: O(1) em média, que é exatamente o motivo de usar um conjunto de hash.

null? indica se o conjunto não tem elementos: a forma direta de perguntar "está vazio?" em vez de comparar cardinality com zero.

: my-log ( -- set ) HS{ "NS-1024" "WB-203" } ;

"NS-1024" my-log in? .   ! => t
"X-99"    my-log in? .   ! => f
my-log null? .           ! => f
HS{ } clone null? .      ! => t
my-log cardinality .     ! => 2

Combinar conjuntos

union     ( set1 set2 -- set )
intersect ( set1 set2 -- set )
diff      ( set1 set2 -- set )
set-like  ( set exemplar -- set' )

union é "todos os elementos de qualquer um dos conjuntos"; intersect é "elementos em ambos"; diff é "em set1 mas não em set2". Cada uma devolve um novo conjunto sem alterar os conjuntos de entrada.

set-like converte set para o tipo de exemplar. As implementações predefinidas de union/intersect/diff usam-no para fazer com que o resultado corresponda ao tipo do recetor: <my-set> <hash-set> union devolve um my-set, não um conjunto de hash.

Porque é que isto importa

Os conjuntos de hash combinam naturalmente com tabelas de hash para travessia de grafos: uma tabela de hash mapeia cada nó para os seus vizinhos, e um conjunto de hash regista quais os nós que já foram visitados, para que a pesquisa não entre em ciclo nem repita trabalho. A travessia é então uma fila mais as duas estruturas, alteradas no local à medida que avanças para fora.