<a href="http://www.ic-net.or.jp/home/takaken/nt/slide/hash.html">最小完全ハッシュ関数の作り方</a> を JavaScript で

ActionScript/Flex ネタが続いているので、たまには JavaScript ネタを。

はてブ経由で知った 最小完全ハッシュ関数の作り方 が面白そうだったのだけど、「最小完全ハッシュ関数」が何か分からないまま読み進めたら、やっぱり話が分からなくなってしまった。

分からないまま JavaScript に移植。

/* 順列型の最小完全ハッシュ関数 */
function ChangeNumber(arr)
{
    var work = arr.concat();
    var hash = 0;

    // 階乗値テーブル作成
    var FACTOR = [1];
    for(var i=0; i < arr.length-1; i++){
        FACTOR.unshift(FACTOR[0] * (i+1));
    }

    for(var i=0; i < arr.length-1; i++) {
        hash += work[i] * FACTOR[i];
        for (j=i+1; j < arr.length-1; j++)
            if (work[i] < work[j]) work[j]--;
    }
    return hash;
}

で、呼び出してみる。

>>> ChangeNumber([0,1,2,3]);
0 // 0,1,2,3 の並べ方の中で一番小さい並べ方なので 0
>>> ChangeNumber([0,1,3,2]);
1 // 0,1,2,3 の並べ方の中で2番目に小さい並べ方なので 1
>>> ChangeNumber([0,2,1,3]);
2 // 3番目に小さいので2
>>> ChangeNumber([0,2,3,1]);
3 // 4番目に小さいので3
>>> ChangeNumber([0,3,1,2]);
4 // 5番目に小さいので4

これでやっとわかった。

最小完全ハッシュ関数は「N個のデータが入力されるときに、入力された値を 0 から N - 1 に変換するハッシュ関数」ということらしい。変換結果の集合が最小限に収まる、ということだ。

で、「順列型の最小完全ハッシュ関数」というのは「0〜N-1 までの N 個の数字を順列として並べたとき、それぞれに 0〜(N!-1) までの番号を割り当てる」という問題になるわけだ。

それを、このページは「0〜N-1 までの N 個の数字を並べたとき、その数字が全部の並べ方の中で何番目に小さいか」を求めることによって解こうとしている。

ハッシュという言葉からハッシュキーのようなものを想像して混乱してしまった。

学んだこと

アルゴリズムの挙動は頭で考えるよりも、実際に手を動かしたほうが理解しやすい。

特に、JS+Firebug は手軽に試せるからうってつけ。

コンソールで右下の ^ ボタンを押して「Larger Command Line」にして関数定義しておいて、1行コマンドラインにして、ばしばし実験できる。分からない変数があったら、console.log しちゃえばよい。

Firebug さまさま。

© nitoyon 2002-2012. All rights reserved.