For Gauche 0.9.6


Next: , Previous: , Up: 組み込みライブラリ   [Contents][Index]

6.15 ハッシュテーブル

R7RS-largeにはハッシュテーブルが定義されています (scheme.hash-tableモジュール、R7RSハッシュテーブル参照)。 しかし、そのAPIはGaucheにもともとあったハッシュテーブルや他のネイティブAPIと一貫性を 欠いている部分があります。

APIをごちゃまぜにするよりは、GaucheのネイティブなAPIの一貫性を保つことを重視し、 R7RSの手続きのうちGaucheにそぐわないものは、組み込み関数では別名 (サフィックス-r7がついたもの)をつけて提供しています。 ポータブルなコードを書く場合は、scheme.hash-tableをインポートすれば R7RSの名前が使えます。

Builtin Class: <hash-table>

ハッシュテーブルのクラスです。<collection><dictionary>を 継承します。

Gaucheは今のところ、変更不可なハッシュテーブルは提供しません。 (変更不可なマップが必要な場合は、変更不可なマップを参照してください。)

ハッシュテーブルのプロパティ

Function: hash-table? obj

[R7RS hash-table] objがハッシュテーブルであれば#tを返します。

Function: hash-table-mutable? ht

[R7RS hash-table] ハッシュテーブルhtが変更可能なら#tを返します。 Gaucheは変更不可なハッシュテーブルを持たないので、 どんなハッシュテーブルに関しても手続きは#tを返します。

Function: hash-table-comparator ht

ハッシュテーブルhtで使われている比較器を返します。

Function: hash-table-type ht

これは古いAPIで、hash-table-comparatorによって置き換えられました。

ハッシュテーブルhtのタイプに応じて、シンボル eq?eqv?equal?string=?generalのいずれかを返します。

Function: hash-table-num-entries ht
Function: hash-table-size ht

[R7RS hash-table] ハッシュテーブルht中の要素の個数を返します。 R7RSの名前はhash-table-size.

ハッシュテーブルのコンストラクタとコンバータ

Function: make-hash-table :optional comparator

[R7RS+ hash-table] ハッシュテーブルを作成します。comparator引数には、 キーの等価判定とハッシュに使う比較器(基本的な比較器参照)を渡します。 省略された場合はeq-comparatorが使われます。 (R7RSではcomparatorは省略できません。)

Gauche独自拡張として、comparatorにシンボル eq?eqv?equal?string=?のいずれかを 指定することもできます。 eq-comparatoreqv-comparatorequal-comparatorstring-comparatorが使われます。

比較器はハッシュ関数を持っていなければなりません。組み込みのハッシュ関数については ハッシュを参照してください。比較器を組み合わせて作られた比較器については、 元の比較器がハッシュ関数を持っていれば、通常は適切なハッシュ関数が設定されます。

Function: hash-table-from-pairs comparator key&value …

与えられたキーと値の列からハッシュテーブルを構築して 返します。comparator引数の意味はmake-hash-tableと同じです。 各key&valueはペアでなければならず、そのcarがキー、cdrが値として使われます。

註:これは0.9.5までhash-tableと呼ばれていた手続きです。 R7RSは同名で異なるインタフェースを持つインタフェースを定義しました。 そちらの方が使いやすいので、長期的にはR7RSインタフェースへとスイッチする予定ですが、 それはかなり将来のことになります。 R7RSインタフェースはhash-table-r7という名前で利用可能なので、 新たなコードはそちらを使うことを強くお勧めします。 また、既存のコードでhash-tableを使っていたら、 hash-table-from-pairsに直してください。

(hash-table-from-pairs 'eq? '(a . 1) '(b . 2))
  ≡
  (rlet1 h (make-hash-table 'eq?)
     (hash-table-put! h 'a 1)
     (hash-table-put! h 'b 2))
Function: hash-table comparator key&value …

hash-table-from-pairsの別名です。 R7RSが同名で別インタフェースの手続き(下のhash-table-r7参照)を導入し、 将来的にはGaucheもそちらに移行する予定です。なので今のところ、 hash-table-from-pairshash-table-r7を使うか、 scheme.hash-tableをインポートしてR7RSとして書いてください。

Function: hash-table-r7 comparator args …

comparatorを比較器に使うハッシュテーブルを作って返します。 args …はキーと値を交互に並べたもので、ハッシュテーブルの内容を指定します。

これはR7RS scheme.hash-tablehash-tableと定義されている手続きです (R7RSハッシュテーブル参照)。

(hash-table-r7 'eq? 'a 1 'b 2)
  ≡
  (rlet1 h (make-hash-table 'eq?)
     (hash-table-put! h 'a 1)
     (hash-table-put! h 'b 2))

註: R7RS準拠の実装には、hash-tableが変更不可なハッシュテーブルを 返すものがあります。Gaucheは変更不可なハッシュテールを持っていないので (変更不可なマップならあります: 変更不可なマップ参照)、 変更可能なハッシュテーブルが返されます。 ただ、ポータブルなプログラムを書いている場合は、この手続きが返したハッシュテーブルを 変更しないように注意してください。

Function: hash-talbe-unfold p f g seed comparator :rest args

[R7RS hash-table] 次の手順で新たなハッシュテーブルを作り返します。 各繰り返しは「現在のシード値」を参照しますが、その初期値はseedです。

  1. 停止述語pを現在のシード値に適用します。それが真の値を返したら、そこで終了です。
  2. 生産手続きfを現在のシード値に適用します。fは二つの値を返さねばなりません。 最初の値がキー、二番目がキーに対応する値として、作られているハッシュテーブルに挿入されます。
  3. 手続きgが現在のシード値に適用され、その戻り値が次の繰り返しでのシード値となります。
Function: hash-table-copy ht :optional mutable?

[R7RS hash-table] ハッシュテーブルhtのコピーを作って返します。

R7RSは、実装が変更不可なハッシュテーブルをサポートする場合、 mutable?引数に真の値が与えられない限りは、 この手続きは変更不可なハッシュテーブルを返すと規定しています。 Gaucheは変更不可なハッシュテーブルを持たないので、mutable?引数は無視され、 常に変更可能なハッシュテーブルが返されますが、 ポータブルなコードを書いている場合は気をつけてください。

Function: hash-table-empty-copy ht

[R7RS hash-table] ハッシュテーブルhtと同じ性質を持つ空の変更可能なハッシュテーブルを作成して 返します。

Function: alist->hash-table alist :optional comparator

[R7RS+ hash-table] alistに含まれるそれぞれの要素をエントリとして持つハッシュテーブルを 作成して返します。その時、要素のcarがキーとして、要素のcdrが値として 使われます。comparator引数の意味はmake-hash-tableと同じです。 comparatorのデフォルト値はeq-comparatorです。

R7RSではcomparatorは省略不可です。

Function: hash-table->alist hash-table

[R7RS hash-table]

  (hash-table-map h cons)

ハッシュテーブルのルックアップと変更

Function: hash-table-get ht key :optional default

キーkeyをハッシュテーブルhtから探します。見つかればキーに対応する 値を返します。キーが見つからなかった場合、defaultが与えられていればそれを 返し、そうでなければエラーを報告します。

Function: hash-table-put! ht key value

キーkeyと対応する値valueをハッシュテーブルhtに挿入します。

Method: ref (ht <hash-table>) key :optional default
Method: (setter ref) (ht <hash-table>) key value

hash-table-gethash-table-put!のメソッド版です。

Function: hash-table-ref ht key :optional failure success

[R7RS hash-table] これがR7RS方式のハッシュテーブルルックアップです。

ハッシュテーブルht中の、keyに結びつけられた値を探し、 それを手続きsuccessに渡して、その結果を返します。 successが省略された場合は単に値そのものが返されます。

keyに対応する値がhtに無い場合は、引数を取らない手続きfailureが 呼ばれ、その結果が返されます。failureが省略されていた場合はエラーが報告されます。

これはGaucheのhash-table-getよりも汎用的ですが、 キーが見つからなかった場合に単純に既定値を返したいといった場合に、 それをいちいちクロージャで包むのは面倒です。R7RSではそのために 下に説明するhash-table-ref/defaultがあります。

Function: hash-table-ref/default ht key default

[R7RS hash-table] ハッシュテーブルhtからkeyを探し、対応する値を返します。 keyが見つからない場合はdefaultを返します。

これは、defaultが省略できないことを除いては、Gaucheの hash-table-getと同じです。hash-table-getの方が短くて便利なので 両方提供しています。

Function: hash-table-set! ht args …

[R7RS hash-table] これが、ハッシュテーブルに新たなエントリを追加するR7RS式のインタフェースです。 args …にはキーと値を交互に並べたリストを指定します。 Gaucheのhash-table-put!と違い、いくつものエントリを一度に追加することができます。 args …が偶数要素でなければエラーです。

(hash-table-set! ht 'a 1 'b 2)
  ≡
  (begin (hash-table-put! ht 'a 1)
         (hash-table-put! ht 'b 2))
Function: hash-table-intern!-r7 ht key failure

これはR7RSでhash-table-intern!として定義されています。 Gaucheの慣習と異なり、R7RSの方式でfailureにサンクを取ることを強調するために -r7サフィックスをつけました。

htからkeyを探します。もし既にエントリがあれば、その値を返します。 エントリが無ければ、サンクfailureを呼び、その戻り値をkeyに対応する 値としてhtに挿入して、failureの戻り値を返します。

Function: hash-table-exists? ht key
Function: hash-table-contains? ht key

[R7RS hash-table] ハッシュテーブルhtにキーkeyを持つエントリがあれば#tを返します。

R7RSでの名前はhash-table-contains?です。

Function: hash-table-delete! ht key

ハッシュテーブルhtからキーkeyを持つエントリを削除します。 keyを持つエントリが実際に存在して削除された場合は#tを、 エントリが存在しなかった場合は#fを返します。 この手続きはSTkでhash-table-remove!と呼ばれているものです (STkのは戻り値が定義されていませんが)。GaucheではSRFI-1, SRFI-13やその他の ライブラリとの一貫性のために ‘delete’ を採用しました。

註: これはR7RSのhash-table-delete!と異なります。 R7RSインタフェースはhash-table-delete!-r7という別名で提供されます。

Function: hash-table-delete!-r7 ht key …

key …を持つエントリをハッシュテーブルhtから削除します。 htに含まれなかったキーは単に無視されます。実際に削除されたエントリの数が返されます。

これはR7RSでhash-table-delete!と呼ばれており、 scheme.hash-tableでもその名前で提供されます。 Gaucheのhash-table-delete!は真偽値を返すので、 組み込みとしては別名で提供することにしました。

Function: hash-table-clear! ht

[R7RS hash-table] ハッシュテーブルhtの全てのエントリを削除します。

Function: hash-table-push! ht key value

ハッシュテーブルht中の、キーkeyに対応する値にvalueをコンスし、 それをkeyに対する新たな値とします。もしkeyに対応する値がまだ無ければ、 新たなエントリが作成され、(list value)がその値となります。

この手続きは次のコードと同じ動作をしますが、キーの探索が一度しか行われないためより高速です。

(hash-table-put! ht key
    (cons value (hash-table-get ht key '())))
Function: hash-table-pop! ht key :optional default

ハッシュテーブルht中のキーkeyに対応する値が存在し、かつペアで あった場合に、そのエントリーを元の値のcdrで置き換え、元の値のcarを返します。 keyに対応する値が存在しないかペアではなかった場合、テーブルは変更されず、 defaultが与えられていればそれが返され、与えられていなければエラーが報告されます。

値が置き換えられる場合でもキーの探索は一度しか行われないため効率が良いです。

註:R7RSもhash-table-pop!を定義していますが、全く違う操作です。 そこで、R7RSバージョンはhash-table-pop!-r7として提供しています。

Function: hash-table-pop!-r7 ht

ハッシュテーブルht中の任意のエントリをひとつ削除し、 そのエントリのキーと値を二つの戻り値として返します。 htが空ならエラーが報告されます。

R7RSではこれがhash-table-pop!と呼ばれていて、 scheme.hash-tableでもその名前で提供されます。

Function: hash-table-update! ht key proc :optional default

hash-table-push!等のより一般的なバージョンです。 ハッシュテーブルの探索が一度しか行われないことを除いては、 基本的に次のように動作します。

(let ((tmp (proc (hash-table-get ht key default))))
  (hash-table-put! ht key tmp)
  tmp)

例えば、ハッシュテーブルを使ってオブジェクトの個数を数えているとしましょう。 次の1行で、オブジェクトitemが既に出現したかどうかを気にせずに その個数をインクリメントできます。

(hash-table-update! ht item (cut + 1 <>) 0))

R7RSもhash-table-update!を定義していますが、インタフェースが異なるので、 GaucheではR7RS版を別名hash-table-update!-r7として提供します。

Function: hash-table-update!-r7 ht key updater :optional failure success

これがR7RS版のhash-table-update!です。 省略可能引数を全て省略した場合はGaucheのhash-table-update!と同じになりますが、 実際にはkeyhtに無かった場合の振る舞いを指定する必要があることが多く、 その場合R7RSのインタフェースはGaucheと異なってきます。

R7RS版は、効率を除けば次のとおり動作します。

(hash-table-put! ht key (updater (hash-table-ref-r7 ht key failure success)))
Function: hash-table-update!/default ht key updater default

[R7RS hash-table] これはdefaultが省略できないことを除けば、 Gaucheのhash-table-update!と同じです。

ハッシュテーブルの走査

Function: hash-table-for-each ht proc
Function: hash-table-map ht proc

ハッシュテーブルht内の全てのエントリについて、各エントリのキーと値を 2つの引数として手続きprocを呼びます。

Function: hash-table-fold ht kons knil

ハッシュテーブルht内の全てのエントリについてkonsを呼びます。 konsには3つの引数が渡されます。 各エントリのキーと値、および一つ前のkonsの返り値です。 最初のkonsの呼び出しの時には、第3引数にknilが渡されます。 最後のkonsの返り値がhash-table-foldの返り値となります。

Function: hash-table-find ht pred :optional failure

predをハッシュテーブルhtの各エントリのキーと値を引数にして 呼び出し、それが真の値を返したら直ちにそれを戻り値とします。 predを満たすキーと値が無ければ、無引数の手続きfailureが呼び出され、 その値が戻り値となります。failureが省略された場合は (lambda () #f)が使われます。

註: srfi-1から始まった慣習では、*-findというAPIは 述語を満たすようなコレクション内の要素を返し、*-anyというAPIが 述語が偽でない値を返した時にその値をそのまま返り値とします。 SRFI-125が慣習を破った理由は、 “any”のセマンティクスで従来の “find” の動作もエミュレートできるので “find”が “any” の動作も兼ねてしまえばよいというものです。 しかし、現在までのところ、この慣習を破っているのはSRFI-125のみです。

;; ハッシュテーブルhaとhbに共通のキーがあるかどうか調べる
(hash-table-find ha (^[k v] (hash-table-exists? hb k)))
Function: hash-table-keys ht
Function: hash-table-values ht

それぞれ、ハッシュテーブルht内の全てのキーまたは値をリストにして返します。

集合としてのハッシュテーブル

Function: hash-table-compare-as-sets ht1 ht2 :optional value=? fallback

ハッシュテーブルは、キーと値の組を要素とする集合とみなすことができます。 この手続きは二つのハッシュテーブルht1ht2を集合として比較します。

二つのハッシュテーブルのキー比較器は同じ (equal?の意味で) でなければなりません。そうでない場合はエラーが投げられます。

二つの要素は、キー同士がキー比較器によって等価と判断され、かつ 値同士がvalue=?手続きによって等価と判断された場合に等しいとみなされます。 value=?が省略された場合はequal?が使われます。

4通りの結果が有り得ます。

Function: hash-table=? value-cmpr ht1 ht2

[R7RS hash-table] この手続きもht1ht2を集合として比較し、 二つのテーブルが等しい集合である場合、つまりht1の要素がすべてht2の要素でもあり、 またその逆も真である場合に#tを、そうでなければ#fを返します。

二つの要素は、キー同士がキー比較器によって等価と判定され、かつ また値同士が比較器value-cmprによって等価と判定された場合に 等しいとみなされます。

ht1ht2のキー比較器が異なっていた場合はエラーが投げられます。 上のhash-table-compare-as-setsも参照してください。

Function: hash-table-union! ht1 ht2
Function: hash-table-intersection! ht1 ht2
Function: hash-table-difference! ht1 ht2
Function: hash-table-xor! ht1 ht2

[R7RS hash-table] 二つのハッシュテーブル間で集合演算を行い、結果をht1に格納します。 これらの手続きでは、集合の要素としてキーだけを見ます。 もし同じキーを持つ要素の値がht1ht2で異なっていた場合、 ht1の値が優先されます。


Next: , Previous: , Up: 組み込みライブラリ   [Contents][Index]