cygport の動作を追ってみているうちに bash がかなりいろんなことができることに気がついたので、勉強のついでに文字列をキーとする hashtable とか実装してみた。
# hashcode <文字列> # return 文字列のハッシュ値 function hashcode() { local hex local dec=0 local i=0 hex=$(echo -n $1 | md5sum) hex=${hex:0:16} while [ $i -le 16 ]; do case ${hex:${i}:1} in [0-9]) let dec="${dec} * 16 + ${hex:${i}:1}";; a) let dec="${dec} * 16 + 10" ;; b) let dec="${dec} * 16 + 11" ;; c) let dec="${dec} * 16 + 12" ;; d) let dec="${dec} * 16 + 13" ;; e) let dec="${dec} * 16 + 14" ;; f) let dec="${dec} * 16 + 15" ;; esac let i="$i + 1" done # 負の値の場合は符号を反転する if [ ${dec} -lt 0 ]; then let dec="- ${dec}" fi echo ${dec} }
前準備として、文字列から一意な整数値を生成する関数 hashcode を実装する。
とりあえず md5sum で文字列を (ほぼ) 一意な 128 bit に変換し、それの先頭の 64 bit を使用するようにしている。ちゃんとソースを読んだわけではないが、雰囲気から察するに bash 内の整数は符号つき 8 byte っぽいからである。
求めた整数値は 16 進表現されているので、それを 10 進整数値に変換する。*1
最後に結果が負だったら、符号を変えて、正にしておく。
ここまでできたら、ほぼ完成。
あとは配列の index に hashcode で求めた整数値を使用するだけ。
# hashtable_put <ハッシュテーブル名> <キー> <値> # return なし function hashtable_put() { eval $1'['$(hashcode $2)']='$3 } # hashtable_get <ハッシュテーブル名> <キー> # return キーに関連付けられた値 function hashtable_get() { eval 'echo ${'$1'['$(hashcode $2)']}' }
hashcode が負の値を返さないようにしたのは配列の index に利用するためである。bash は可変長配列ながらも、途中に空の要素があっても OK っぽいので、このようにした。
ちなみにキーが衝突した場合の考慮はしていないことに注意。
hashtable が実装できると、データ構造を少しはまともに表現できるようになるため、そこそこプログラミングの幅が広がると思う。
あとはなんかほど良いサイズのネタがあれば、これを使って「bash で実装しますた」とふざけたことをやってみようと思う。
*1:ここ以降の処理はもうちょっとスマートな方法があるかもしれない。