<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 個の数字を並べたとき、その数字が全部の並べ方の中で何番目に小さいか」を求めることによって解こうとしている。
ハッシュという言葉からハッシュキーのようなものを想像して混乱してしまった。