独学Common Lisp

Hash Table Dictionary

概要

ハッシュテーブルはkeyvalueで構成されるデータ構造です。keyvalueが紐づけられており、keyを手がかりにvalueを簡単に取得することができます。

単純な構造なので複雑なことはできませんが、柔軟に使うことができます。

make-hash-table

ハッシュテーブルはmake-hash-tableで作成します。作成したテーブルはシンボルに束縛するか、大域変数として定義しなければ使えません。

(defbar *db* (make-hash-table))
; => *DB*

(hash-table-p *db*)
; => T

*db*
; => #<HASH-TABLE :TEST EQL size 0/60 #x302000B7E30D>

ハッシュテーブルはサイズというオプションがありますが、標準仕様では処理系依存ということになっています。

test オプション

make-hash-tablekeyが一致するレコードのvalueを取り出しますが、「一致」を確かめる述語を指定できます。標準はeqlですが、equalにするとより柔軟な判定を行うことができます。

文字列をeqlで比較すると同じ文字列でも別のオブジェクトなのでNILになりますから、ハッシュテーブルのkeyに文字列を指定する場合はeqlではなくequalを指定します。

(eql "a" "a")
; => NIL

(equal "a" "a")
; => T

(make-hash-table :test 'equal)
; => #<HASH-TABLE :TEST EQUAL size 0/60 #x302000B1E6FD>

:testオプションはfunction(#')でも動くようですが、仕様によればquote(')を使うようなので'equalを指定しています。

gethash

ハッシュテーブルに対して要素の追加と参照を行うにはgethashを使います。gethashはアクセッサなのでsetfの第一引数にすることができます。

(setf (gethash 'year *db*) '(2014 2015 2016))
; => (2014 2015 2016)

(gethash 'year *db*)
; => (2014 2015 2016)
;    T

gethashでハッシュテーブルの探索をすると、返り値は多値で戻ってきます。後ろの値は存在するか否かを判定するために使われます。これは、nilという値が入っている時に有用です。

(gethash nil *db*)
; => NIL
;    NIL

(setf (gethash nil *db*) nil)
; => NIL

(gethash nil *db*)
; => NIL
;    T

最初に探索した時は二つ目の返り値もNILですが、値をセットした後に探索すると存在するのでTに変わっています。

remhash

テーブルからレコードを削除するにはremhashを使います。

(remhash 'year *db*)
; => T

(gethash 'year *db*)
; => NIL
;    NIL

maphash

ハッシュテーブルの要素に対して容易に繰り返しやマップ処理を行うことができるのが、maphashです。

(setf *db* (make-hash-table))
(setf (gethash 'abc *db*) "abc.csv")
(setf (gethash 'def *db*) "def.csv")
(setf (gethash 'ghi *db*) "ghi.csv")
(maphash (lambda (key value)
           (setf (gethash key *db*)
                 (concatenate 'string "datadir/" value)))
         *db*)
(gethash 'def *db*)
; => "datadir/def.csv"
;    T

maphashの第一引数は2つの引数を取るラムダであり、それぞれkeyvalueが束縛されていきます。

with-hash-table-iterator

with-hash-table-iteratorとシンプルなloopを組み合わせればハッシュテーブルを柔軟にイテレート(繰り返し)することができます。

(let ((temp '()))
  (with-hash-table-iterator (next *db*)
    (loop (multiple-value-bind (present key value) (next)
            (when (null present) (return))
            (push key temp)
            (push value temp))))
  (reverse temp))
; => (GHI "datadir/ghi.csv" ABC "datadir/abc.csv" DEF "datadir/def.csv")

with-hash-table-iteratorwith-open-fileによく似た使い方をしますが、束縛するのはストリームではなく、イテレートするためのジェネレータです。ジェネレータは呼び出すたびに異なる値を返すように作られており、今回はnextというシンボルがジェネレータを束縛しています。

multiple-value-bind(next)を呼び出した返り値を多値として束縛しますが、最初の引数が「レコードがまだ存在するかどうか」を示す真偽値になっており、loopからの脱出に用います。(when (not present) (return))もしくは(unless present (return))で脱出できます。

hash-table-count & clrhash

その他使われる可能性のあるオペレータとして、ハッシュテーブルの要素数を数えるhash-table-countと、ハッシュテーブルをクリアするclrhashを紹介します。

(hash-table-count *db*)
; => 3

(clrhash *db*)
; => #<HASH-TABLE :TEST EQL size 0/60 #x302000B240AD>

(hash-table-count *db*)
; => 0

どちらもその関数名の通りですが、名前の付け方がかなり違いますね。

ハッシュテーブル操作用関数

gethashsetfと組み合わせて使うのが面倒なので、ハッシュテーブルを使う場合は簡単な操作用関数を自作してから使う方が便利だと思います。

;;; Hash Table Simple Database
(defvar *db* '())
(defun db-create ()
  (setf *db* (make-hash-table :test 'equal)))

(defun db-insert (key value)
  (setf (gethash key *db*) value))

(defun db-select (key)
  (gethash key *db*))

(defun db-drop (key)
  (remhash key *db*))

(db-create)
; => #<HASH-TABLE :TEST EQUAL size 0/60 #x302000D3E75D>

(db-insert 'year #(2014 2015 2016))
; => #(2014 2015 2016)

(svref (db-select 'year) 1)
; => 2015

(db-drop 'year)
; => T

ハッシュテーブル名を指定するのが面倒なので、大域変数でテーブル名を固定しています。

「初期化」「挿入」「参照」「削除」の基本4操作だけですが、途中の計算結果を保存しながら全体の計算をステップに分けて行うシミュレーション系のツールでハッシュテーブルを用いて実装したことがあります。大域変数をどんどんと増やすのはなんとなく気持ちが悪いので、ただ途中結果を保存するためだけに使ったものですが、プログラムが大きくなかったこともあり、処理速度は全く気になりませんでした。

ハッシュテーブルは配列と異なり、事前にデータ構造の形を決める必要がなく、リストでもベクタでもスカラ(ただの値)でも入れられます。使い方次第でかなり柔軟に実装できると思います。


Copyright © 2017- satoshiweb.net All rights reserved.