短いハッシュの作り方

特に言語には関係がないのでこのカテゴリに。

md5やsha1でハッシュを作ると、32桁か40桁で大文字小文字の区別がないものとなります。

以下のような短いハッシュはどのように作るのでしょうか。

http://am6.jp/asRleJ
http://twitpic.com/12zs0a
http://bit.ly/axe7hu

No.4 ベストアンサー 回答者： mtaka2 回答日時： 2010/02/14 20:45

いくらでも方法はあるので、質問者さんが挙げられているサイトが実際にどうやっているかはわかりませんが、

6文字程度の文字列では、「衝突しないハッシュ関数」を作るのは非常に困難であり、「衝突が発生する」ことがあるのを前提にして設計しないとといけません。
こういう場合、「ハッシュテーブル」におけるハッシュの取り扱いが参考になるでしょう。
ハッシュテーブルにおけるハッシュ関数は、名前が同じ「ハッシュ」でも、取り扱い方はmd5やsha1などとは異なります。

ハッシュテーブル用のハッシュ関数にはいろいろありますが、
中でもKnuth のアルゴリズムが有名です。
そういったハッシュ関数を使って最大値[62^6]のハッシュを生成し、それを
62進数に6桁に変換して、それを文字列化すればいいでしょう。

Knuth のハッシュ関数: http://d.hatena.ne.jp/yamanetoshi/20090517/p1
ハッシュが衝突した場合の処理: http://tortoise1.math.ryukoku.ac.jp/~takataka/cp …

(62^6は32bitより大きいですから、64bit整数で計算する必要がありますので要注意)

以上が文字列から短いハッシュを生成する方法の定番ですが、
短縮URLのようなシステムの場合、そもそも「ハッシュ関数」を使う必要すらないです。
そういうシステムでは、「URL→短縮文字列」および「短縮文字列→URL」の変換を、データベースに登録して行いますから、そもそも「URLから短縮文字列が算出できる」必要はどこにもありません。

乱数で適当なランダム文字列を生成し、それがデータベースに登録されていなければ採用、
DBに登録済みだったら、登録されていない文字列が出来るまでランダム生成を繰り返し、
で、出来た文字列と、元のURLの組をデータベースに登録
でOKです。

あるいは、もっと単純に、登録順に振られた番号から、それをそのまま62進変換するだけ、という方法でも実現できます。
(回答3の方法ですね)

この回答への補足

ご回答ありがとうございます。

> 乱数で適当なランダム文字列を生成し、それがデータベースに登録されていなければ採用、
DBに登録済みだったら、登録されていない文字列が出来るまでランダム生成を繰り返し

最大値（≒桁数）と増加割合の問題だとは思いますが、ある程度の登録が発生した後（例えば最大値の半分とか）では「DBに登録済みだったら、登録されていない文字列が出来るまでランダム生成を繰り返し」のコストが勿体無いのではないかと考えておりました。

ハッシュを使用しつつ、衝突時には回避策を取るのがバランスが良さそうですね。

> あるいは、もっと単純に、登録順に振られた番号から、それをそのまま62進変換するだけ、という方法でも実現できます。

用途によりますが、類推が出来ない方が良い場合が多いと思いますので、連番以外の方法を知りたいと思っていました。

いくつかご回答を頂いてみると、6桁のハッシュというのは言語共通などで実装された一般的な関数などではなく、みな独自実装されているという事のようですね。

特に最近、短縮URLに限らず、6桁程度のハッシュに見える値を見かける事が多かったためにこのような質問をさせて頂きました。

補足日時：2010/02/14 21:13

No.6 回答者： osamuy 回答日時： 2010/02/15 01:12

＞DBのカウンタ値を元に「短いURLを生成」という処理は、つまりはハッシュと同じではないでしょうか。

ハッシュ関数は、入力が一緒なら返値は常に同じですが、
カウンタはそうじゃないです。同じURLでも異なる値を返しても問題ないからです。
カウンタであれば、
・計算が楽(+1すればよい。というかたいていのDBMSはオートインクリメントをサポートしてる)。
・衝突しない。
・元のURLを導くのが楽(バイナリサーチあるいは、配列添え字アクセス)。
――というメリットがあります（実際には、カウントするデータベースが1つだけだとスケールしないだろうから、負荷分散のための名前空間的なものを含んでるでしょうが）。

参考URL：http://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83% …

この回答への補足

回答ありがとうございます。

> カウンタであれば、
> ・計算が楽
> ・衝突しない。

そうなのですが、他のURLが類推できない方が望ましいため、連番をそのまま使う事ができないという事です。

補足日時：2010/02/28 10:20

No.5 回答者： notnot 回答日時： 2010/02/14 22:00

#1です。

＞41bitというのはどのような計算でしょうか。

すいません。何故か間違えて62の7乗を計算してました。

＞MD5よりもだいぶ範囲が狭まる状況で適当に切り出してしまうと、さらに衝突可能性を高めるなどの問題が考えられますでしょうか。

どういうハッシュ関数を作るにせよ、短ければ短いほど衝突する可能性が高まるのは当然ですよね。衝突したら、タイムスタンプやプロセス番号を加えるなどして、衝突しなくなるまで繰り返す。認証や検証のためのハッシュと違って、あくまで、まんべんなく散らばったキーの作成のため(他のキーを推測されにくくするため)なので、最初に衝突しても問題ありません。

他の方が書いているように、ハッシュである必要すらなく、乱数でもいいですよね。ただ、高トラフィックの場合、マルチタスクでキーを発番するということを考えると、ハッシュの方が楽な気がします。疑似乱数だと前回値の保存が面倒。ハードウェアの乱数発生器を使うと却って時間がかかったり。

No.3 回答者： osamuy 回答日時： 2010/02/14 14:50

> axe7hu

この手の短いURLは、一方向ハッシュ関数を使ってないのでは。
単にひとつカウンタを持っていて、入力されたURLにそのときのカウンタの値をデータベースに登録。紐付けたカウンタ値を元に短いURLを生成して返す――というだけのような。

この回答への補足

> 単にひとつカウンタを持っていて、入力されたURLにそのときのカウンタの値をデータベースに登録。紐付けたカウンタ値を元に短いURLを生成して返す――というだけのような。

DBのカウンタ値を元に「短いURLを生成」という処理は、つまりはハッシュと同じではないでしょうか。

DBのカウンタ値を元にするか、入力値を元にするかという違いだけな気がします。

補足日時：2010/02/14 18:39

No.2 回答者： kmee 回答日時： 2010/02/14 11:54

MD5等は

(1)入力(文字列等)のハッシュ(値)を求める
(2)求めたハッシュ値を一定の法則で文字列にして人間が扱いやすいようにする
という2段階で処理されています。

(1)はハッシュ関数と呼ばれるもので
・入力の特徴をなんらかの値で表わす(ハッシュ値)
・入力が違う時は値も違うことが望ましい
というものです。
MD5の場合は、入力からMD5独自の計算方法で128bitの整数を求めます。
プログラム中では、この値のまま使用することも多いです。

(2)は(1)の値を1対1に相互変換できる文字列にするもので、MD5,SHA1等は単純に16進数文字列にしています。
例えば、MD5(128bit)を 0～9a～zの36種の文字を使って36進数 で表現すれば
36^24 < 2^128 < 36^25
なので25文字で表現できます。0～9A～Za～zの62進数なら22文字です。

前置きが長くなりしたが、例にあるような短いハッシュの作り方です
・(2)で使う文字の種類と文字列の長さを決める。
例示されたものは、0～9A～Za～zの62種で6文字と予想されます。
・↑でハッシュ値の範囲が解る( 0 ～ (文字種^文字数)-1 )ので、ハッシュ値がその範囲になるようなハッシュ関数を作る。
例示されたものは、62種6文字とするなら0～(62^6)-1までの値になるように計算しています。
2^35<62^6<2^36なので、コンピュータで扱いやすいように35bitや32bitの値にしているかもしれません。

難しいのはこのハッシュ関数で、これが正解、というものがありません。
MD5とSHA1とでも違います。

この回答への補足

回答ありがとうございます。

> 難しいのはこのハッシュ関数で、これが正解、というものがありません。
> MD5とSHA1とでも違います。

長さ（範囲）や表現に使用する文字種を指定可能なハッシュ関数などがあるのかと思ったのですが、特に無いという事ですね。

補足日時：2010/02/14 18:39

No.1 回答者： notnot 回答日時： 2010/02/14 11:34

独自のハッシュ関数を作ればどうにでも出来ます。

英大文字＋小文字＋数字で、6文字とすると、62進数(26+26+10)で6桁なので、約41ビットに縮めればいいことがわかります。

手抜きをするなら、MD5アルゴリズムで128ビットにして、その中の末尾なり先頭なり途中なりの41ビットを取りだして文字化すればいい。

この回答への補足

回答ありがとうございます。

> 独自のハッシュ関数を作ればどうにでも出来ます。

一般的な一般的はハッシュy関数は無いという事ですね。

> 英大文字＋小文字＋数字で、6文字とすると、62進数(26+26+10)で6桁なので、約41ビットに縮めればいいことがわかります。

41bitというのはどのような計算でしょうか。
35bit < 62^6 < 36bit という計算とは違いますか?

> 手抜きをするなら、MD5アルゴリズムで128ビットにして、その中の末尾なり先頭なり途中なりの41ビットを取りだして文字化すればいい。

MD5よりもだいぶ範囲が狭まる状況で適当に切り出してしまうと、さらに衝突可能性を高めるなどの問題が考えられますでしょうか。

補足日時：2010/02/14 18:12