Tabelas de dispersão em

Sobre Tabelas de dispersão

As tabelas de dispersão em Common Lisp são estruturas de dados para armazenar dados associativos. Mapeiam chaves (que podem ser qualquer objeto) em valores (que também podem ser qualquer objeto).

Criar tabelas de dispersão

As tabelas de dispersão podem ser criadas com a função make-hash-table.

A função make-hash-table aceita vários parâmetros de palavra-chave para afinar o tamanho inicial da tabela de dispersão, bem como o seu limiar de redimensionamento; consulta a documentação para obteres toda a informação sobre eles. Mais importante ainda, aceita também um parâmetro de palavra-chave test, que define como as chaves são comparadas durante a inserção, a consulta e a remoção de chaves e valores. Os valores do argumento test podem ser 'eq, 'eql, 'equal ou 'equalp, que correspondem aos predicados de igualdade genéricos. O valor predefinido é 'eql.

Operações comuns em tabelas de dispersão

Para obter um valor a partir da sua chave, usa-se gethash. O gethash aceita um [argumento opcional][concept-defualt-arguments] que funciona como o valor a devolver se a chave não estiver presente na tabela de dispersão. O gethash devolve também múltiplos valores (explicados noutro conceito). O primeiro valor é o valor dessa chave na tabela de dispersão, o valor predefinido, se for fornecido, ou NIL. O segundo valor é um Boolean que indica se a chave estava presente na tabela de dispersão ou não.

Para inserir um par chave-valor, usa-se setf com gethash.

Para remover uma chave e o seu valor, usa-se remhash.

Para remover todas as chaves e valores, usa-se clrhash.

Embora uma tabela de dispersão em Common Lisp, tal como noutras linguagens, não tenha uma ordem garantida, por vezes pode ser útil iterar sobre uma, processando cada par chave/valor. Isso pode ser feito com maphash:

(maphash #'(lambda (key value) (print (cons key value))) *hash-table*)

(Isto imprime cada chave e valor como um par cons, um por linha.)

Referência

(setf *hash-table* (make-hash-table))     ; => #<HASH-TABLE :TEST EQL :COUNT 0 {100375FD23}>
(gethash :foo *hash-table*)               ; => NIL
                                          ;    NIL
(gethash :foo *hash-table* 
         :default-value)                  ; => :DEFAULT-VALUE
                                          ;    NIL

(setf (gethash :foo *hash-table*) :bar)   ; => :BAR
(gethash :foo *hash-table*)               ; => :BAR
                                          ;    T

(setf (gethash :key *hash-table*) :value) ; => :RIGHT
(gethash :key *hash-table*)               ; => :VALUE
                                          ;    T

(remhash :key *hash-table*)               ; => T
(gethash :key *hash-table*)               ; => NIL
                                          ; => NIL
                            
(clrhash *hash-table*)                    ; => #<HASH-TABLE :TEST EQL :COUNT 0 {1005A90103}>
(gethash :foo *hash-table*)               ; => NIL
                                          ;    NIL