ハッシュ表を使って
K&R; 6.6 Table Lookup では、自己参照的構造体となる連結リストを要素に持つハッシュ表〔hash table〕を使った事例が紹介されています。
【K&R, p.144】"An array element points to the beginning of a linked list of blocks describing names that have that hash value." とあるように「ハッシュ表は、連結リストを要素とする配列」で表現できます。そして、ハッシュ関数によって得られる値が一様なら高速なアクセスが期待され、リストの線形探索へと帰着します。また、連結リストを二分木に変更すると、探索の効率をさらに改善できます。
ハッシュ値
----------------------------------------------<< K&R, p.144 >>----
/* hash: form hash value for string s */
unsigned hash(char *s)
{
unsigned hashval;
for (hashval = 0; *s != '\0'; s++)
hashval = *s + 31 * hashval;
return hashval % HASHSIZE;
}
Ｃ言語版の関数 hash は、文字列 s に対する、ハッシュ値を計算します。
class Htable:
hashsize = 5 # = 101
def hash(self, s):
hashval = reduce(lambda acc, e: ord(e)+31*acc, s, 0)
return hashval % self.hashsize
メソッド hash は、文字列 s から求めたハッシュ値をリターン値とします。組み込み関数 reduce を使って、各文字の ASCII コード ord(e) を累積した値 hashval をもとに、文字列 s のハッシュ値を決定します。
《付記》Smalltalk では、inject:into: を用いるのが定番です。ブロッククロージャーを指定できるので、reduce より柔軟な表現が可能です。Groovy にも、同様の inject が規定されています。OCL には、同様の iterate が規定されています。Ruby での表現を参考にするのも一興です。♪ひよ子
ハッシュ探索
----------------------------------------------<< K&R, p.145 >>----
/* lookup: look for s in hashtable */
struct nlist *lookup(char *s)
{
struct nlist *np;
for (np = hashtab[hash(s)]; np != NULL; np = np->next)
if (strcmp(s, np->name) == 0)
return np; /* found */
return NULL; /* not found */
}
Ｃ言語版の関数 lookup は、文字列 s を含む、記号表の各要素（連結リスト）np を探索します。ただし、文字列 s が見つからないなら、NULL をリターン値とします。
class Htable:
def lookup(self, s):
np = self.hashtab[self.hash(s)]
while np:
if s == np.name: return np
np = np.next
return None
メソッド lookup は、文字列 s を含むリスト項目をリターン値とします。前述したメソッド hash から得られるハッシュ値を使って、記号表 self. Htable を検索します。ただし、文字列 s が見つからないなら、None をリターン値とします。
《付記》ここでは、while/for に象徴される、伝統的なスタイルを踏襲しています。まだ「for と別れる方法」を紹介していないので、ここでは必要悪として残しています。より洗練された実現方法は、別の記事で紹介しました。♪ひよ子
項目の登録
----------------------------------------------<< K&R, p.145 >>----
/* install: put (name, defn) in hashtab */
struct nlist *install(char *name, char *defn)
{
struct nlist *np;
unsigned hashval;
if )((np = lookup(name))( == NULL) { /* not found */
np = (struct nlist *) malloc(sizeof(*np));
if (np == NULL || (np->name = strdup(name)) == NULL)
return NULL;
hashval = hash(name);
np->next = hashtab[hashval];
hashtab[hashval] = np;
} else /* already there */
free((void *) np->defn); /* free previous defn */
if )((np->defn = strdup(defn))( == NULL)
return NULL;
return np;
}
Ｃ言語版の関数 install は、連結リストの各要素 np に、名前 name/置換テキスト defn を登録します。
class Htable:
def install(self, name, defn):
np = self.lookup(name)
if not np:
np = Nlist()
np.name = name
hashval = self.hash(name)
np.next = self.hashtab[hashval]
self.hashtab[hashval] = np
np.defn = defn
return np
メソッド install は、名前 name/置換テキスト defn を、登録/更新した後のリスト項目 np をリターン値とします。記憶領域を確保して初期設定を行う作業は、クラス Nlist に委ねます。Python に限らず、ガーベジコレクションの支援があると、記憶管理を扱うコードが混在しないので、コードの見通しが良くなります。すると、プログラマーは、どのようにするか how ではなく、何をしたいか what に専念できます。
《ひよ子のきもち♪2007/12/04》
連結リスト
----------------------------------------------<< K&R, p.144 >>----
struct nlist { /* table entry: */
struct nlist *next; /* next entry in chain */
char *name; /* defined name */
char *defn: /* replacement text */
};#define HASHSIZE 101
static struct nlist *hashtab[HASHSIZE]; /* pointer table */
構造体 nlist は、記号表 hashtab を構成する要素（連結リスト）を規定します。
class Nlist: # table entry
def __init__(self, next=None, name="", defn=""):
self.next = next # next entry in chain
self.name = name # defined name
self.defn = defn # replacement text
クラス Nlist は、構造体 nlist に相当します。記号表の各要素には、名前 name と置換テキスト defn とともに、次の要素 next を保持します。
