ハッシュテーブルを作ってみた。

Scheme 30分プログラム

30分プログラム、その698。データ構造を作ってみたシリーズ、ハッシュテーブルを作ってみた。
「ハッシュテーブルをハッシュと略すのは、ウィキペディアをウィキと略すのと同じだ」で同じみのハッシュテーブルです。

「組込みのhashなんていらないぜ。自分でハッシュ関数を書いてやる!」と意気込んで始めるも、最後はassoc-set!に逃げてしまいました。

使い方

(define table (make-hash-table 42))

(update-hash-table table "foo" 0)
(update-hash-table table "bar" 1)

(find-hash-table table "foo") ;; => 0
(find-hash-table table "bar") ;; => 1

ソースコード

#! /opt/local/bin/gosh
;; -*- mode:scheme; coding:utf-8 -*-
;;
;; hash-table.scm -
;;
;; Copyright(C) 2009 by mzp
;; Author: MIZUNO Hiroki / mzpppp at gmail dot com
;; http://howdyworld.org
;;
;; Timestamp: 2009/11/22 22:21:53
;;
;; This program is free software; you can redistribute it and/or
;; modify it under MIT Lincence.
;;

(use srfi-13)
(use util.list)
(use gauche.array)

(define (string-hash s)
  (string-fold (lambda (x y) (+ (* 31 (char->integer x)) y))
	       0
	       s))

(define-class <my-hash-table> () (size data))

(define (make-hash-table size)
  (let ([t (make <my-hash-table>)]
	[data (make-array (shape 0 size) '())])
    (slot-set! t 'size size)
    (slot-set! t 'data data)
    t))

(define (update-hash-table table key value)
  (let ([index (modulo (string-hash key) (slot-ref table 'size))]
	[data  (slot-ref table 'data)])
    (array-set! data
		index
		(assoc-set! (array-ref data index) key value))))

(define (find-hash-table table key)
  (assoc-ref
   (array-ref (slot-ref table 'data)
	      (modulo (string-hash key) (slot-ref table 'size)))
   key))

;; example
(define table (make-hash-table 42))
(update-hash-table table "foo" 0)
(update-hash-table table "bar" 1)
(d table)

(find-hash-table table "foo") ;; => 0
(find-hash-table table "bar") ;; => 1

参考