Basic hash tables
Panu Kalliokoski
This SRFI is currently in ``final'' status. To see an explanation of each
status that a SRFI can hold, see
here.
It will remain in draft status until 2005/09/09, or as amended. To
provide input on this SRFI, please
mailto:srfi-69@srfi.schemers.org.
See instructions
here to subscribe to the list. You can access previous messages via
the
archive of the mailing list.
この SRFI は簡単なハッシュテーブルを定義する。 ハッシュテーブルは様々なアプリケーションで用いられる 基礎的なデータ構造として広く知られている。 ハッシュテーブルは以下のようなデータ構造である。
この SRFI の目標は以下の通りである。
ハッシュテーブルをつくる唯一の正解の方法はない。
この SRFI では、概念的に単純で、
様々なアプリケーションで使用可能なことを目標にする。
ポータブルな実装が提供されていたとしても、実装側では、
例えば、シンボルに対して内部ハッシュ関数を提供するなどして、
大幅に高速化をはかることができる。また、ほとんどの実装には、
大域環境を実装する自然な方法として、具体的には
string->symbol を提供するために、
既に何らかの低レベルハッシュテーブル機能がある。
ここで紹介する API と実装依存のデータ型を統合することには
何らかの利益あるだろうが、ここではこの問題については保留しておく。
この SRFI は SRFI 44 の map のインタフェースには従わない。 SRFI 44 に従うことにより、ハッシュテーブルのインタフェースは 著しく不自由になる。 SRFI 44 の map に対する操作の命名規則は一般的な用法に反し、 不自然なものにになっている。 しかしながら、この SRFI は SRFI 44 の API をハッシュテーブルに 適用することを妨げるものではない。 この SRFI と SRFI 44 の両方をサポートする処理系は、 ここに示すものに加えて、SRFI 44 のインタフェースをハッシュテーブル用に 提供することをおすすめする。
ハッシュテーブルは様々な種類の計算タスクのための基礎的な データ構造として広く知られている。 今のところ、Scheme のハッシュテーブルには標準的なものがなく、 ごく小さな実装を除いてほとんどの実装が別個に 何らかのハッシュテーブル機能を提供している。
しかし悲しいかな、何らかの似通ったところはあるものの、 これらのハッシュテーブルには差違が多い。 ささいな点でいえば、特定の関数の名前のようなものであったり、 複雑なものでは、実装内部の異なる側面がユーザーに見えていたり、 お粗末なところでは、キーが何か特定の型であることを要求するという ようなことであったり、 微妙な点では、最適な性能を得るためには、ユーザーに前もって ハッシュテーブルのサイズを見積ってもらう必要がある、等々、 様々である。結果として、既存のハッシュテーブルはポータブルな プログラムを書くのには使えないのである。
この SRFI のいちばんの目標は標準的なハッシュテーブルの API を確立し、ハッシュテーブルを有効に利用したポータブルな プログラムを書けるようにすることである。 この SRFI では、さまざまなハッシュテーブルの API の間に存在する、 命名規則やハッシュテーブルの操作の意味論についての違いを解決する。 API を、一貫性があり、単純で一般性のあるものにするために 多大な努力が支払われた。 この SRFI では他にも、様々なアプリケーションを書くのに必要になるであろう、 もっとも一般的なユーティリティルーチンも定義している。
この SRFI を実装の標準機能に加えれば、ハッシュテーブルをつかった、 効率のよいポータブルなプログラムを書けるようになるだろう。
この SRFI で定義される名前
hash-table-ref、hash-table-set!、
hash-table-delete!、hash-table-update!、
hash-table-exists?、hash-table-size
が（よいハッシュ関数が与えられた場合に）償却定数時間で実行されない、
ないしは、hash、string-hash、
string-ci-hash、hash-by-identity
について、よいハッシュ関数の定義の与えられないものは、この
SRFI に合致しない。
ハッシュテーブルの実装はテーブル中のキーのハッシュ値が変化しないことに 依存してもよい。大抵の場合、ハッシュテーブルにキーを挿入したあとに、 キーを in-place に変更すると、この制約がおかされ未定義のふるまいを ひきおこす。
何の対応も格納しない新しいハッシュテーブルを作成する。
equal? は述語で、キーをふたつ受け取り、それらが同一のキー値を
持つかどうかを返す。デフォルトは equal? である。
hash はハッシュ関数で、デフォルト値は与えられた
equal? 述語に適したハッシュ関数になる
（ハッシュ関数 の節を参照）。
ただし、strinc-ci=? を除き、equal?
よりも粗い同値関係については許容可能なデフォルト値は保証されない
[1]。関数 hash は equal?
を許容可能でなければならない。すなわち、string-ci=?
以外の、equal? よりも粗い同値関係を使う場合には、
hash を使用者が指定しなければならない。
[1]
同値述語 c1 が同値述語 c2 について、
(and (c1 x y) (not (c2 x y))) なる x、y
が存在するときかつそのときにかぎり、c1 は
c2 よりも粗い、という。
残りの args を実装依存の拡張に使ってもかまわない。 ただし、このような拡張をつかうと、プログラムのポータビリティが そこなわれることには注意しなけらばならない。
与えられたオブジェクト obj がハッシュテーブルかどうかをテストする述語。ハッシュテーブル型は、 可能であれば、ほかのすべての型と互いに素であるべきである。
連想リスト alist を取り、連想リストの car
を対応する cdr に写像するハッシュテーブルを作成する。
equal?、hash、args は
make-hash-table と同様に解釈される。
キーが alist のなかに複数回現れた場合には、
最初の対応に現れたものの方があとのものよりも優先される
（注: 値として（cadr の代わりに）cdr
をつかうのは、ふたつの方法のバランスをとろうとしたものである。
cadr を使うとこの手続きは cdr
連想リストに使えなくなるが、逆は真ではない）。
hash-table のキーに使われる同値述語を返す。
hash-table のキーに使われるハッシュ関数を返す。
この手続きは hash-table 中の key に対応する value を返す。 key に対応する value がない場合、 thunk があたえられていれば、thunk を呼び出し、その戻り値を返し、 thunk が与えられていない場合にはエラーが通知される。 よいハッシュ関数が与えられていれば、この操作の（償却）計算量は hash-table 中の対応の数に対して O(1) になる （注: これにより連想リストや固定長ハッシュテーブルによる実装は除外される）。
(hash-table-ref hash-table key (lambda () default)).
と同じ値に評価される。
よいハッシュ関数が与えられていれば、この操作の（償却）計算量は
hash-table 中の対応の数に対して O(1) になる
（注: これにより連想リストや固定長ハッシュテーブルによる実装は除外される）。
この手続きは hash-table 中の key に対して value を設定する。以前の対応は（もしあれば）取り除かれる。 よいハッシュ関数が与えられていれば、この操作の（償却）計算量は hash-table 中の対応の数に対して O(1) になる （注: これにより連想リストや固定長ハッシュテーブルによる実装は除外される）。
この手続きは hash-table 中の key への対応をすべて取り除く。キーに対する対応が存在しない場合、 エラーにはならず、何もしない。 よいハッシュ関数が与えられていれば、この操作の（償却）計算量は hash-table 中の対応の数に対して O(1) になる （注: これにより連想リストや固定長ハッシュテーブルによる実装は除外される）。
この述語は hash-table 中に key に関する対応があるかどうかを返す。 よいハッシュ関数が与えられていれば、この操作の（償却）計算量は hash-table 中の対応の数に対して O(1) になる （注: これにより連想リストや固定長ハッシュテーブルによる実装は除外される）。
意味的には以下のコードと同等だが、 より効率的に実装されるかもしれない。
(hash-table-set! hash-table key
(function (hash-table-ref hash-table key thunk)))
(hash-table-update! hash-table key
function (lambda () default)) を評価したようにふるまう。
hash-table 中の対応の個数を返す。この操作は、 hash-table 中の対応の個数に対して O(1) の複雑さでなければならない。
hash-table 中のキーのリストを返す。 キーの順番は未定義である。
hash-table 中の値のリストを返す。値の順序は未定義で、 hash-table-keys の結果のキーの順序と一致することは保証されない。
proc は key と value のふたつの引数を取る関数でなければならない。 この手続きは hash-table 中の各対応について proc を呼び出す。proc の戻り値は捨てられる。 別の対応に対する proc の呼び出し順序は規定されていない。
（注: この手続きと同じことをする
hash-table-map という手続きのある実装もあるが、
hash-table-map が何か別のことをする実装もある。
著者の知っている範囲で、hash-table-map
が通常の関数をハッシュテーブルのドメインに持ち上げる
（that lifts an ordinary function to the domain of hash tables）
ような実装は存在しない。このような理由により、
hash-table-map はこの SRFI の範囲外になっている。
この手続きは hash-table 中の各対応について f
を、対応の key、対応の値 value、
累積値 val を引き数に呼び出す。
val は f の最初の呼び出し時には
init-value になり、以下の f の呼び出しでは
直前の f の呼び出しの戻り値になる。
hash-table-fold の返す final-value
の値は f の最後の呼び出しの値である。
別の対応に対する proc の呼び出し順序は規定されていない。
各要素の car が hash-table のキーで、対応する
cdr がキーに対応する値であるような連想リストを返す。
要素の順序は規定されていない。
以下のコードは常に h と同じ写像のハッシュテーブルを
返さなければならない。
(alist->hash-table (hash-table->alist h)
(hash-table-equivalence-function h)
(hash-table-hash-function h))
hash-table と同じ同値述語、ハッシュ関数、写像の、 新しいハッシュテーブルを返す。
hash-table2 中の写像をすべて hash-table1 に追加し、結果のハッシュテーブルを返す。この関数は hash-table1 を破壊的に変更するかもしれない。
ハッシングは何らかの値を受け取り、その値から数値を生成することをいう。
ハッシュ関数はこれをする関数である。
同値述語 e にはそれぞれ許容可能なハッシュ関数がある。
(e obj1 obj2) → (= (hash obj1) (hash obj2))
であるときかつそのときにかぎり、ハッシュ関数 hash
が許容可能である、という。
ハッシュ関数 h が 同値関数 e に対して よい というのは、 （e にとって）等しくないオブジェクトに対して、 特に、等しくないオブジェクト同士が互いに似通っている、 例えば、共通の部分列をもつ場合に、 結果の値（ハッシュ値）がハッシュ値の値域にできるだけ 均一に分散することをいう。 この定義は曖昧であるが、例えば、定数関数がよいハッシュ関数ではない ことを主張するには十分である。
上の make-hash-table の定義で e に対して 適切なハッシュ関数と言ったとき、 ハッシュ関数が e に対して許容可能でよく、 さらに（ハッシング操作に対して）優れた性能を示すことをいう。 この定義もまた、意図的に曖昧になっている。
object に対して (0, bound)
の範囲のハッシュ値を生成する。bound が与えられなかった場合、
デフォルトの bound が普通のアプリケーションで想定可能な
どんなハッシュテーブルよりも大きな値であれば、
実装側は自由に bound を選んでよい
（これは、デフォルトの bound として、実装側が fixnum
の範囲で何かとても大きな値を選択できるためにである）。
このハッシュ関数は equal? に対して許容可能である。
引き数 string が文字列でなければならないことを除いて hash と同じである。
string の大文字・小文字の別がハッシュ値に影響を与えないことを除けば、 string-hash と同じである。
eq? に対して許容可能であることが保証されていることを除けば
hash と同じである。この関数を提供するのは、
hash よりも極めて効率よく実装されているかもしれないからである。
実装側ではこの関数を組み込みで提供することが好ましい。
この実装はハッシュテーブル型の明瞭さのために SRFI 9 を、 エラー通知のために SRFI 23 を使っている。 それ以外の部分は、純粋な R5RS である。
(define *default-bound* (- (expt 2 29) 3))
(define (%string-hash s ch-conv bound)
(let ((hash 31)
(len (string-length s)))
(do ((index 0 (+ index 1)))
((>= index len) (modulo hash bound))
(set! hash (modulo (+ (* 37 hash)
(char->integer (ch-conv (string-ref s index))))
*default-bound*)))))
(define (string-hash s . maybe-bound)
(let ((bound (if (null? maybe-bound) *default-bound* (car maybe-bound))))
(%string-hash s (lambda (x) x) bound)))
(define (string-ci-hash s . maybe-bound)
(let ((bound (if (null? maybe-bound) *default-bound* (car maybe-bound))))
(%string-hash s char-downcase bound)))
(define (symbol-hash s . maybe-bound)
(let ((bound (if (null? maybe-bound) *default-bound* (car maybe-bound))))
(%string-hash (symbol->string s) (lambda (x) x) bound)))
(define (hash obj . maybe-bound)
(let ((bound (if (null? maybe-bound) *default-bound* (car maybe-bound))))
(cond ((integer? obj) (modulo obj bound))
((string? obj) (string-hash obj bound))
((symbol? obj) (symbol-hash obj bound))
((real? obj) (modulo (+ (numerator obj) (denominator obj)) bound))
((number? obj)
(modulo (+ (hash (real-part obj)) (* 3 (hash (imag-part obj))))
bound))
((char? obj) (modulo (char->integer obj) bound))
((vector? obj) (vector-hash obj bound))
((pair? obj) (modulo (+ (hash (car obj)) (* 3 (hash (cdr obj))))
bound))
((null? obj) 0)
((not obj) 0)
((procedure? obj) (error "hash: procedures cannot be hashed" obj))
(else 1))))
(define hash-by-identity hash)
(define (vector-hash v bound)
(let ((hashvalue 571)
(len (vector-length v)))
(do ((index 0 (+ index 1)))
((>= index len) (modulo hashvalue bound))
(set! hashvalue (modulo (+ (* 257 hashvalue) (hash (vector-ref v index)))
*default-bound*)))))
(define %make-hash-node cons)
(define %hash-node-set-value! set-cdr!)
(define %hash-node-key car)
(define %hash-node-value cdr)
(define-record-type <srfi-hash-table>
(%make-hash-table size hash compare associate entries)
hash-table?
(size hash-table-size hash-table-set-size!)
(hash hash-table-hash-function)
(compare hash-table-equivalence-function)
(associate hash-table-association-function)
(entries hash-table-entries hash-table-set-entries!))
(define *default-table-size* 64)
(define (appropriate-hash-function-for comparison)
(or (and (eq? comparison eq?) hash-by-identity)
(and (eq? comparison string=?) string-hash)
(and (eq? comparison string-ci=?) string-ci-hash)
hash))
(define (make-hash-table . args)
(let* ((comparison (if (null? args) equal? (car args)))
(hash
(if (or (null? args) (null? (cdr args)))
(appropriate-hash-function-for comparison) (cadr args)))
(size
(if (or (null? args) (null? (cdr args)) (null? (cddr args)))
*default-table-size* (caddr args)))
(association
(or (and (eq? comparison eq?) assq)
(and (eq? comparison eqv?) assv)
(and (eq? comparison equal?) assoc)
(letrec
((associate
(lambda (val alist)
(cond ((null? alist) #f)
((comparison val (caar alist)) (car alist))
(else (associate val (cdr alist)))))))
associate))))
(%make-hash-table 0 hash comparison association (make-vector size '()))))
(define (make-hash-table-maker comp hash)
(lambda args (apply make-hash-table (cons comp (cons hash args)))))
(define make-symbol-hash-table
(make-hash-table-maker eq? symbol-hash))
(define make-string-hash-table
(make-hash-table-maker string=? string-hash))
(define make-string-ci-hash-table
(make-hash-table-maker string-ci=? string-ci-hash))
(define make-integer-hash-table
(make-hash-table-maker = modulo))
(define (%hash-table-hash hash-table key)
((hash-table-hash-function hash-table)
key (vector-length (hash-table-entries hash-table))))
(define (%hash-table-find entries associate hash key)
(associate key (vector-ref entries hash)))
(define (%hash-table-add! entries hash key value)
(vector-set! entries hash
(cons (%make-hash-node key value)
(vector-ref entries hash))))
(define (%hash-table-delete! entries compare hash key)
(let ((entrylist (vector-ref entries hash)))
(cond ((null? entrylist) #f)
((compare key (caar entrylist))
(vector-set! entries hash (cdr entrylist)) #t)
(else
(let loop ((current (cdr entrylist)) (previous entrylist))
(cond ((null? current) #f)
((compare key (caar current))
(set-cdr! previous (cdr current)) #t)
(else (loop (cdr current) current))))))))
(define (%hash-table-walk proc entries)
(do ((index (- (vector-length entries) 1) (- index 1)))
((< index 0)) (for-each proc (vector-ref entries index))))
(define (%hash-table-maybe-resize! hash-table)
(let* ((old-entries (hash-table-entries hash-table))
(hash-length (vector-length old-entries)))
(if (> (hash-table-size hash-table) hash-length)
(let* ((new-length (* 2 hash-length))
(new-entries (make-vector new-length '()))
(hash (hash-table-hash-function hash-table)))
(%hash-table-walk
(lambda (node)
(%hash-table-add! new-entries
(hash (%hash-node-key node) new-length)
(%hash-node-key node) (%hash-node-value node)))
old-entries)
(hash-table-set-entries! hash-table new-entries)))))
(define (hash-table-ref hash-table key . maybe-default)
(cond ((%hash-table-find (hash-table-entries hash-table)
(hash-table-association-function hash-table)
(%hash-table-hash hash-table key) key)
=> %hash-node-value)
((null? maybe-default)
(error "hash-table-ref: no value associated with" key))
(else ((car maybe-default)))))
(define (hash-table-ref/default hash-table key default)
(hash-table-ref hash-table key (lambda () default)))
(define (hash-table-set! hash-table key value)
(let ((hash (%hash-table-hash hash-table key))
(entries (hash-table-entries hash-table)))
(cond ((%hash-table-find entries
(hash-table-association-function hash-table)
hash key)
=> (lambda (node) (%hash-node-set-value! node value)))
(else (%hash-table-add! entries hash key value)
(hash-table-set-size! hash-table
(+ 1 (hash-table-size hash-table)))
(%hash-table-maybe-resize! hash-table)))))
(define (hash-table-update! hash-table key function . maybe-default)
(let ((hash (%hash-table-hash hash-table key))
(entries (hash-table-entries hash-table)))
(cond ((%hash-table-find entries
(hash-table-association-function hash-table)
hash key)
=> (lambda (node)
(%hash-node-set-value!
node (function (%hash-node-value node)))))
((null? maybe-default)
(error "hash-table-update!: no value exists for key" key))
(else (%hash-table-add! entries hash key
(function ((car maybe-default))))
(hash-table-set-size! hash-table
(+ 1 (hash-table-size hash-table)))
(%hash-table-maybe-resize! hash-table)))))
(define (hash-table-update!/default hash-table key function default)
(hash-table-update! hash-table key function (lambda () default)))
(define (hash-table-delete! hash-table key)
(if (%hash-table-delete! (hash-table-entries hash-table)
(hash-table-equivalence-function hash-table)
(%hash-table-hash hash-table key) key)
(hash-table-set-size! hash-table (- (hash-table-size hash-table) 1))))
(define (hash-table-exists? hash-table key)
(and (%hash-table-find (hash-table-entries hash-table)
(hash-table-association-function hash-table)
(%hash-table-hash hash-table key) key) #t))
(define (hash-table-walk hash-table proc)
(%hash-table-walk
(lambda (node) (proc (%hash-node-key node) (%hash-node-value node)))
(hash-table-entries hash-table)))
(define (hash-table-fold hash-table f acc)
(hash-table-walk hash-table
(lambda (key value) (set! acc (f key value acc))))
acc)
(define (alist->hash-table alist . args)
(let* ((comparison (if (null? args) equal? (car args)))
(hash
(if (or (null? args) (null? (cdr args)))
(appropriate-hash-function-for comparison) (cadr args)))
(size
(if (or (null? args) (null? (cdr args)) (null? (cddr args)))
(max *default-table-size* (* 2 (length alist))) (caddr args)))
(hash-table (make-hash-table comparison hash size)))
(for-each
(lambda (elem)
(hash-table-update!/default
hash-table (car elem) (lambda (x) x) (cdr elem)))
alist)
hash-table))
(define (hash-table->alist hash-table)
(hash-table-fold hash-table
(lambda (key val acc) (cons (cons key val) acc)) '()))
(define (hash-table-copy hash-table)
(let ((new (make-hash-table (hash-table-equivalence-function hash-table)
(hash-table-hash-function hash-table)
(max *default-table-size*
(* 2 (hash-table-size hash-table))))))
(hash-table-walk hash-table
(lambda (key value) (hash-table-set! new key value)))
new))
(define (hash-table-merge! hash-table1 hash-table2)
(hash-table-walk
hash-table2
(lambda (key value) (hash-table-set! hash-table1 key value)))
hash-table1)
(define (hash-table-keys hash-table)
(hash-table-fold hash-table (lambda (key val acc) (cons key acc)) '()))
(define (hash-table-values hash-table)
(hash-table-fold hash-table (lambda (key val acc) (cons val acc)) '()))
Copyright © Panu Kalliokoski(2005). All Rights Reserved.
Permission is hereby granted, free of charge, to any person obtaining a
copy of this software and associated documentation files (the
Software
), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED AS IS
, WITHOUT WARRANTY OF ANY KIND, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.