@blog.justoneplanet.info

■実装

var a =  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19];

/**
 * hash
 * ハッシュ関数
 * 解説用に衝突しやすい関数を使用
 * @param {int} x
 */
var hash = function(x){
    return x % 5;// tableのサイズを5とした（=メモリに応じたサイズ）
}

/**
 * setTable
 * 要素のハッシュ値をキーにした配列に変換
 * @param {Array} ary
 */
var setTable = function(ary){
    var table = [];
    for(var i = 0; i < a.length; i++){
        var key = hash(a[i]);
        if(!table[key]){// 衝突した場合
            table[key] = [];// 通常は連結リストを使用するが簡略化のため配列を使用
            table[key].push(a[i]);// （要素の追加・削除の用途が多いので）
        }
        else{
            table[key].push(a[i]);
        }
    }
    return table;
}

/**
 * search
 * 探索用関数
 * @param {Array} table
 * @param {int} elm
 */
var search = function(table, elm){
    var key = hash(elm);// 要素のハッシュ値を求めてハッシュテーブルから探索する
    if(table[key]){
        for(var i = 0; i < table[key].length; i++){
            if(table[key][i] === elm){
                return true;
            }
        }
        return false;
    }
    else{
        return false;
    }
};

var table = setTable(a);
console.log(JSON.stringify(table));// [[0,5,10,15],[1,6,11,16],[2,7,12,17],[3,8,13,18],[4,9,14,19]]
console.log(search(table, 6));// true
console.log(search(table, 39));// false

■特性

• 最良時と平均時の計算コストはO(1)
• 最悪時は全ての要素のハッシュ値が衝突した場合で線形時間の探索が必要になりO(n)

■ポイント

• ハッシュ関数には性能が良く衝突が少ないものを使う
• 衝突は起こるものとして考える

■参考

文字列のハッシュ値の計算として以下のようなものもあるらしい。

var key = function(str){
    var hash = 0;
    for(var i = 0; i < str.length; i++){
        hash += Math.pow(31, str.length - i - 1) * str[i].charCodeAt(0);
    }
    return hash;
}

しかし上述の関数でも20万語を通すと衝突が発生し、最大で7単語が衝突する。