LISP - Tabela de Hash

A estrutura de dados da tabela de hash representa uma coleção de key-and-valuepares que são organizados com base no código hash da chave. Ele usa a chave para acessar os elementos da coleção.

Uma tabela hash é usada quando você precisa acessar elementos usando uma chave e pode identificar um valor de chave útil. Cada item da tabela hash possui um par chave / valor. A chave é usada para acessar os itens da coleção.

Criando Hash Table em LISP

No Common LISP, a tabela hash é uma coleção de propósito geral. Você pode usar objetos arbitrários como uma chave ou índices.

Quando você armazena um valor em uma tabela hash, você faz um par de valores-chave e o armazena nessa chave. Posteriormente, você pode recuperar o valor da tabela de hash usando a mesma chave. Cada chave mapeia para um único valor, embora você possa armazenar um novo valor em uma chave.

As tabelas de hash, em LISP, podem ser categorizadas em três tipos, com base na forma como as chaves podem ser comparadas - eq, eql ou igual. Se a tabela hash for hash em objetos LISP, as chaves serão comparadas com eq ou eql. Se a tabela hash hash na estrutura de árvore, então ela seria comparada usando igual.

o make-hash-tablefunção é usada para criar uma tabela hash. A sintaxe para esta função é -

make-hash-table &key :test :size :rehash-size :rehash-threshold

Onde -

  • o key argumento fornece a chave.

  • o :testargumento determina como as chaves são comparadas - deve ter um dos três valores # 'eq, #' eql ou # 'igual, ou um dos três símbolos eq, eql ou igual. Se não for especificado, eql será assumido.

  • o :sizeargumento define o tamanho inicial da tabela hash. Deve ser um número inteiro maior que zero.

  • o :rehash-sizeargumento especifica quanto aumentar o tamanho da tabela hash quando ela ficar cheia. Pode ser um número inteiro maior que zero, que é o número de entradas a serem adicionadas, ou pode ser um número de ponto flutuante maior que 1, que é a proporção do novo tamanho em relação ao antigo. O valor padrão para este argumento depende da implementação.

  • o :rehash-thresholdargumento especifica o quão cheia a tabela hash pode ficar antes de crescer. Pode ser um número inteiro maior que zero e menor que: rehash-size (nesse caso, ele será dimensionado sempre que a tabela aumentar) ou pode ser um número de ponto flutuante entre zero e 1. O valor padrão para isso argumento é dependente da implementação.

Você também pode chamar a função make-hash-table sem argumentos.

Recuperando itens e adicionando itens na tabela de hash

o gethashfunção recupera um item da tabela hash procurando por sua chave. Se não encontrar a chave, ele retornará nulo.

Possui a seguinte sintaxe -

gethash key hash-table &optional default

onde -

  • chave: é a chave associada

  • tabela de hash: é a tabela de hash a ser pesquisada

  • default: é o valor a ser retornado, se a entrada não for encontrada, que é nulo, se não for especificado.

o gethash na verdade, a função retorna dois valores, o segundo sendo um valor de predicado verdadeiro se uma entrada for encontrada e falso se nenhuma entrada for encontrada.

Para adicionar um item à tabela hash, você pode usar o setf funcionar junto com o gethash função.

Exemplo

Crie um novo arquivo de código-fonte denominado main.lisp e digite o seguinte código nele.

(setq empList (make-hash-table)) 
(setf (gethash '001 empList) '(Charlie Brown))
(setf (gethash '002 empList) '(Freddie Seal)) 
(write (gethash '001 empList)) 
(terpri)
(write (gethash '002 empList))

Quando você executa o código, ele retorna o seguinte resultado -

(CHARLIE BROWN)
(FREDDIE SEAL)

Removendo uma entrada

o remhashfunção remove qualquer entrada para uma chave específica na tabela de hash. Este é um predicado verdadeiro se houver uma entrada ou falso se não houver.

A sintaxe para esta função é -

remhash key hash-table

Exemplo

Crie um novo arquivo de código-fonte denominado main.lisp e digite o seguinte código nele.

(setq empList (make-hash-table)) 
(setf (gethash '001 empList) '(Charlie Brown))
(setf (gethash '002 empList) '(Freddie Seal)) 
(setf (gethash '003 empList) '(Mark Mongoose)) 

(write (gethash '001 empList)) 
(terpri)
(write (gethash '002 empList)) 
(terpri)
(write (gethash '003 empList))  
(remhash '003 empList)
(terpri)
(write (gethash '003 empList))

Quando você executa o código, ele retorna o seguinte resultado -

(CHARLIE BROWN)
(FREDDIE SEAL)
(MARK MONGOOSE)
NIL

A função maphash

o maphash função permite que você aplique uma função especificada em cada par de valores-chave em uma tabela hash.

Recebe dois argumentos - a função e uma tabela hash e invoca a função uma vez para cada par chave / valor na tabela hash.

Exemplo

Crie um novo arquivo de código-fonte denominado main.lisp e digite o seguinte código nele.

(setq empList (make-hash-table)) 
(setf (gethash '001 empList) '(Charlie Brown))
(setf (gethash '002 empList) '(Freddie Seal)) 
(setf (gethash '003 empList) '(Mark Mongoose)) 

(maphash #'(lambda (k v) (format t "~a => ~a~%" k v)) empList)

Quando você executa o código, ele retorna o seguinte resultado -

3 => (MARK MONGOOSE)
2 => (FREDDIE SEAL)
1 => (CHARLIE BROWN)