bash hacks (1)

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:ここ以降の処理はもうちょっとスマートな方法があるかもしれない。