第18章「ハッシュテーブル」

概要

ANSI Common Lispの第18章「ハッシュテーブル」を説明します。

ハッシュテーブルの基礎

ハッシュテーブルとは、keyvalue の組み合わせで保存されるデータの構造です。

属性リスト(plist)や連想リスト(alist)はリストの構造を使って keyvalue のデータ構造を実装したものですが、先頭から順に key を検索していくので、アクセス速度が早くありません。ハッシュテーブルはこの弱点を克服し、key からハッシュ値と呼ばれる特定の数に変換し、そのハッシュ値で直接データ構造にアクセスして value を取り出します。そのため、ランダムアクセスに対して高速です。

また、ハッシュテーブルは構造体やクラスと異なり、事前にスロットを定める必要はありません。あるハッシュテーブルを作成したら、動的に keyvalue の組み合わせを追加することができます。データの構造が静的で、そのデータ構造を持つオブジェクトをたくさん生成したい場合は構造体を使用し、継承を使用する場合はクラスを使用しますが、データの構造を静的に決めるのではなく、動的に決める場合はハッシュテーブルが適しています。

ハッシュテーブルを使用する場合の基本的なステップは3つです。
  1. ハッシュテーブルを生成します。生成にはmake-hash-table関数を使います。
  2. ハッシュテーブルにデータを追加します。データの追加にはgethashアクセッサをsetfマクロと共に使います。
  3. ハッシュテーブルからデータを取得します。データの取得にはgethashアクセッサを使用します。
以下が基本的な使い方のサンプルです。
;; ハッシュテーブルの生成
(defparameter *ht* (make-hash-table))
; => *HT*

;; 要素の追加
(setf (gethash 'url *ht*) "lisp.satoshiweb.net")
; => "lisp.satoshiweb.net"
(setf (gethash 'since *ht*) 2017)
; => 2017
(setf (gethash 'author *ht*) "Satoshi")
; => "Satoshi"

;; 要素の参照
(gethash 'url *ht*)
; => "lisp.satoshiweb.net" ;
;    T
(gethash 'since *ht*)
; => 2017 ;
;    T
(gethash 'author *ht*)
; => "Satoshi" ;
;    T

;; 返り値は多値
;; 2番目の値は要素が含まれているかどうか
(gethash 'authors *ht*)
; => NIL ;
;    NIL

ハッシュテーブルに関するオペレータ

ハッシュテーブルはあまり複雑な使い方をすることはないので、多くの使用状況では前節の3ステップで事足りると思います。ただ、ここではいくつかのオペレータを追加で紹介します。

生成: make-hash-table

make-hash-table関数はハッシュテーブルの実体を生成して返す単純な関数ですが、いくつかのキーワード引数が用意されています。中でも:testキーワード引数だけは知っておく必要があります。

シンボルというデータ構造のない他の多くのプログラミング言語では、ハッシュテーブルの key として文字列を使用することが多いと思います。key の判定にはデフォルトでeql述語関数が使われますが、文字列の判定にはeql関数を使うことができません。そのため、文字列の場合にはstring=述語関数を代わりに使う必要があります。

ところが、ハッシュテーブルは使用できる述語関数が汎用の関数4種類だけに限定されています。その4種類とは、eq, eql, equal, equalpです。そのため、文字列を key に用いる場合は以下のようにequalを使用するべきです。
(setq *ht* (make-hash-table :test 'equal))
; => #S(HASH-TABLE :TEST FASTHASH-EQUAL)

逆にシンボルを使う場合はeqlではなくeqの方が高速なので、eqlでも判定上は問題がなくてもeqを使用する場合があります。

参照: gethash

gethashアクセッサは前節で使用したように、多値を返します。そのため、ハッシュテーブルにアクセスし、もし key が見つからなければ2番目の返り値がnilになりますが、1番目の返り値もnilです。動的にインタプリタで用いる場合は「見つからなかった」ことがすぐに分かりますが、プログラムの中では多値を意識してエラーを通知するなど、アクセスできなかった場合に配慮しなければなりません。

ハッシュテーブルから要素を取得しつつ、もし key が存在しなければエラーを通知するような関数は以下のように定義できます。
(defun gethash* (key table)
  (multiple-value-bind (value present-p) (gethash key table)
    (if present-p
        value
        (error "~s is not present in the hash-table." key))))
; => GETHASH*

(defparameter *ht* (make-hash-table))
; => *HT*
(setf (gethash 'url *ht*) "lisp.satoshiweb.net")
; => "lisp.satoshiweb.net"

(gethash* 'ulr *ht*)
; *** - ULR is not present in the hash-table.

要素数: hash-table-count

ハッシュテーブルに登録された要素の数を取得するには、hash-table-count関数を使用します。
(hash-table-count *ht*)
; => 1

削除: remhash

ハッシュテーブルから要素を削除するにはremhash関数を使用します。
(remhash 'url *ht*)
; => T

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

初期化: clrhash

ハッシュテーブルの要素を全て削除するにはclrhashを使用します。
(clrhash *ht*)
; => #S(HASH-TABLE :TEST FASTHASH-EQL)

返り値もハッシュテーブルですが、これは初期化したハッシュテーブルと同じもので、コピーではありません。

繰り返し: maphash

ハッシュテーブルの全ての要素にアクセスするには、loopマクロを使うことができます。ハッシュテーブルにいくつかの要素を追加してから試してみてください。
(loop for v being the hash-values in *ht* do (print v))
; "Satoshi" 
; 2017 
; "lisp.satoshiweb.net" 
; => NIL

(loop for v being the hash-keys in *ht* do (print v))
; AUTHOR 
; SINCE 
; URL 
; => NIL

しかし、maphash関数を使った方がより簡潔に書くことができる場合もあります。
(maphash #'(lambda (k v) (format t "(~s = ~s)~%" k v)) *ht*)
; (AUTHOR = "Satoshi")
; (SINCE = 2017)
; (URL = "lisp.satoshiweb.net")
; => NIL

0 件のコメント :

コメントを投稿