ハッシュ作ってみた

グラフ理論で使うデータ構造にリストを使うと検索コストが高いので、ハッシュを使いたい。

SRFI 69: Basic hash tablesを眺めてみたら、ハッシュの実装例が載ってたので、簡単に写経してみた。


SRFI-69の実装例では、ベクタ + alistの二次元構造。alistをハッシュテーブルに分割することによって検索速度の向上を図ると。ハッシュはハッシュでもO(1)では無くO(n/テーブルサイズ)くらい。テーブルサイズを大きくすればまぁまぁ早い感じ。

(define *default-bound* (- (expt 2 29) 3))
(define *table-size* 10)

(define (make-hash)
  (make-vector *table-size* '()))

(define (get-hash key)
  (letrec ((iter (lambda (l)
                   (if (null? l)
                       31
                       (modulo (+ (char->integer (car l))
                                  (* 37 (iter (cdr l))))
                               *default-bound*)))))
    (modulo (iter (string->list (symbol->string key)))
            *table-size*)))

(define (hash-value hash key)
  (let ((a (assq key (vector-ref hash (get-hash key)))))
    (and a (cdr a))))

(define (hash-set! hash key value)
  (let ((index (get-hash key)))
    (hash-delete! hash key)
    (vector-set! hash index
                 (cons (cons key value)
                       (vector-ref hash index)))))

(define (hash-delete! hash key)
  (letrec ((index (get-hash key))
           (iter (lambda (l)
                   (cond ((null? l) '())
                         ((eq? (caar l) key) (cdr l))
                         (else
                           (cons (car l) (iter (cdr l))))))))
    (vector-set! hash index (iter (vector-ref hash index)))))

テスト。

(define my-hash (make-hash))

(hash-set! my-hash 'hello "Hello, Hash World!!")
(hash-set! my-hash 'hi "Hi, Hash.")

(hash-value my-hash 'hello) ; Hello, Hash World!!
(hash-value my-hash 'hi) ; Hi, Hash.

(hash-delete! my-hash 'hello) 

(hash-value my-hash 'hello) ; #f

案外簡単に作れたけど、自作はあんまり・・・

ぬはぁ、そうか

全然早くないじゃないかと思ってたら、ここからがハッシュの凄いところで、

「再配置」

テーブルサイズが許容範囲を超えたら、テーブルサイズを増やして再配置してやれば、約O(1)をキープすることが出来るのか。

かなり改造が必要だけど、実装してみるか。

テーブルの再配置を実装

テーブルサイズが2個になっているので、2個を超えたら倍のサイズのテーブルを用意して、元のデータをコピーしながら再配置していくことにする。

(define *default-bound* (- (expt 2 29) 3))
(define *table-size* 2)

(define (make-hash)
  (let ((size 0)
        (table (make-vector *table-size* '())))
    (lambda (m)
      (case m
            ('table table)
            ('table-set! (lambda (t)
                           (set! size 0)
                           (set! table t)))
            ('size size)
            ('inc! (set! size (+ size 1)))
            ('dec! (set! size (- size 1)))
            ('length (vector-length table))))))

(define (get-hash key len)
  (letrec ((iter (lambda (l)
                   (if (null? l)
                       31
                       (modulo (+ (char->integer (car l))
                                  (* 37 (iter (cdr l))))
                               *default-bound*)))))
    (modulo (iter (string->list (symbol->string key)))
            len)))

(define (hash-value hash key)
  (let ((a (assq key (vector-ref (hash 'table) (get-hash key (hash 'length))))))
    (and a (cdr a))))

(define (hash-set! hash key value)
  (let ((index (get-hash key (hash 'length)))
        (table (hash 'table)))
    (if (hash-delete! hash key)
        (hash 'dec!))
    (vector-set! table index (cons (cons key value)
                                    (vector-ref table index)))
    (hash 'inc!)
    (if (> (hash 'size) (hash 'length))
        (hash-resize! hash))))

(define (hash-delete! hash key)
  (letrec ((index (get-hash key (hash 'length)))
           (table (hash 'table))
           (iter (lambda (l)
                   (cond ((null? l) #f)
                         ((eq? (caar l) key) (cdr l))
                         (else
                           (let ((res (iter (cdr l))))
                             (and res (cons (car l) res))))))))
    (let ((res (iter (vector-ref table index))))
      (and res (vector-set! table index res) (hash 'dec!)))))

(define (%hash-fold f seed table)
  (vector-fold
    (lambda (i acc v)
      (fold
        (lambda (a acd)
          (f (car a) (cdr a) acd))
        acc
        v))
    seed
    table))

(define (hash-fold f seed hash)
  (%hash-fold f seed (hash 'table)))

(define (hash-resize! hash)
  (let* ((size (* 2 (hash 'length)))
          (new-table (make-vector size '()))
          (old-table (hash 'table)))
     ((hash 'table-set!) new-table)
     (%hash-fold
       (lambda (key value acc)
         (hash-set! hash key value))
       #f
       old-table)))

srfi-43のvector-foldに戸惑った。

テスト。

(define my-hash (make-hash))

(hash-set! my-hash 'hello "Hello, Hash World!!")
(hash-set! my-hash 'hi "hi, Hash.")

(my-hash 'table)
; #(((hi . hi, Hash.)) ((hello . Hello, Hash World!!)))

(hash-set! my-hash 'resize "Hash Sugeeeeeeeeeeeee!!") ; ← ここら辺で再配置してる。
(hash-set! my-hash 'hoge "hoge hoge")

(my-hash 'table)
; #(((resize . Hash Sugeeeeeeeeeeeee!!) (hi . hi, Hash.)) ()
;   ((hoge . hoge hoge)) ((hello . Hello, Hash World!!)))

検索はほぼO(1)となった。


ハッシュスゲー。

問題点がいろいろ

ハッシュの場合、検索のコストは低いが、挿入のコストがやたら高い。

  • ハッシュ関数の精度、速度。
  • 再配置のコスト
  • 衝突問題
    • Schemeの場合、簡単にalistが使えるので問題ないけど、alistの検索には、ハッシュが不可欠な訳で・・・そうなると、配列の空いている場所を探す必要が出てくる。しかし、この空いている場所を探すというのが結構大変な作業になるっぽい。

挿入のコストをいかにして下げるか。というのがハッシュの問題点らしい。


勉強になった。